Converting a grammar to LALR/yacc

Factual Questions
1

I’ve been trying to find a yacc-compatible grammar for C99. Incredibly, I can’t find one online. This best I could find was this, which is very close to what I need. The main problem that I’m running into is rules like the following:

postfix_expression : postfix_expression ‘(’ argument_expression_list? ‘)’ ;

My parser generator(it isn’t yacc, but it’s quite close) can’t handle the ? operator. I tried the following:

optional_argument_expression_list : argument_expression_list | ;
postfix_expression : postfix_expression ‘(’ optional_argument_expression_list ‘)’ ;

But that doesn’t seem to have worked – I get a whole bunch of warnings telling me that such-and-such a production is never reduced.

Can anyone either give me a hint on how to deal with this? Or, better yet, link me to a yacc grammar for C99? Even better, how about a grammar for gcc99(ie C99 + the gcc extensions).

2

Well, I solved my problem. I forgot to declare my start symbol. :smack:

I’m getting a lot of shift/reduce conflicts, though. I’m wondering about rules like:

postfix-expression : postfix-expression[ expression ];

Is this LALR? I have a vague memory that says it, but it’s been a long time since I did language theory.

3

I have a vague memory that says it isn’t…

4

Yes, yacc can certainly handle grammar like that. Shift/reduce conflicts are usually nothing to worry about; test the parser to make sure it works correctly, then you can use the %expect directive to make yacc suppress the warning message if it finds exactly the expected number of conflicts.

The canonical example of a harmless shift/reduce conflict is if/else statements:


if-stmt
: IF condition THEN statement
| IF condition THEN statement ELSE statement

Once the parser has read the first four tokens in “if x then y else z”, it can either reduce by rule 1 (and immediately fail when it tries to make ELSE the beginning of a new statement), or shift and continue with rule 2. The default is to shift, which is usually what you want.