Using first-set in recursive descent parser

1
votes

I'm writing a recursive descent parser for C in C++. I don't know how to choose the right production in the following case:

statement: labeled-statement | compound-statement | expression-statement | selection-statement | iteration-statement | jump-statement

I read about the "first"-set which compares the lookahead-token/char with possible terminals which comes first in the productions. Currently I'm stuck at using a first-set in a recursive descent parser, because I only have a function and nothing else, no object for each rule or anything else with which I can identify a rule/production.

1
c++cparsing
Something up with your shift key? - Lightness Races in Orbit
No, sry. Next time i'll use it :) - dcast
Thanks! It just keeps the place looking tidy, and it's a small courtesy to those who are going to be helping you out. - Lightness Races in Orbit
For C, you won't succeed with pure recursive descent (LL(1)) parsing. You need to be able to distinguish certain types in orer to parse this way. See this answer as to why: stackoverflow.com/questions/243383/… - Ira Baxter

1 Answers

2
votes

Your grammar is invalid for recursive descent parsers because it's ambiguous on the left side:

  • labeled-statement starts with an identifier
  • compound-statement starts with a { (this is fine)
  • expression-statement starts with an identifier or a number (or ()

Can stop here, you have a clash between labeled statement and expression statement. You need to transform your grammer to get rid of left-side ambiguities (through temporary grammar nodes to contain the common parts so when you branch you can determine which branch to go to using only the look-ahead).