Conflict in grammar YACC/Bison

Question

I have a YACC grammar for parsing expressions in C. These are some of it's fragments:

Expr: Expr COMMA Expr 
     | Assignment


Assignment: IDENTIFIER
            | Assignment COMMA Assignment

Function Call: IDENTIFIER PARENOPEN Expr PARENOPEN

What I basically want to be able to is to parse function calls of the form a(p,q,r) and check if the number and type of the the passed arguments matches that specified in the function definition such that they reduce to Expr at the level of identifier itself.

What ends up happening is that p,q,r are reduced to Assignment instead of Expr COMMA Expr. This is problematic since I need to run some semantic rules that can only be run using Expr COMMA Expr. Also it is not possible to remove the rule Assignment COMMA Assignment since it is critical for certain reductions. Is there any way that I can hardcode into YACC what needs to be done in such a case?

Chris Dodd Chris Dodd · Accepted Answer · 2013-04-15T20:53:59

The problem is that the grammar as written is ambiguous. As you've noticed, when parsing an input p,q it can be parsed as Expr COMMA Expr where each Expr reduces from Assignment (which reduces from IDENTIFIER), or it can be parsed as Assignment COMMA Assignment which then reduces to a single Expr.

Which do you want? If you ALWAYS want one or the other, just delete the one you never want as it can never come up. If you sometimes want one and sometimes want the other, you need to say HOW YOU KNOW WHICH in any given case. If it based on context, then you need to refactor you grammar differently so you can differentiate the contexts, probably by making Expr and Assignment completely independent.

In addition, you have the stand left-vs-right recursive ambiguity. When you have p,q,r do you want it parsed as (Expr , Expr) , Expr or Expr , (Expr , Expr)? Again you need to decide which you want under what conditions and set things up appropriately.

Conflict in grammar YACC/Bison

1 Answers