How can I remove the function call ambiguity from a Lemon grammar?

Question

I have the following lemon grammar (simplified from the real grammar):

%right ASSIGN .
%nonassoc FN_CALL .

program ::= expression .
expression ::= expression ASSIGN expression .
expression ::= function_call . [FN_CALL]
expression ::= IDENTIFIER .


function_call ::= expression LPAREN RPAREN . [FN_CALL]

I'm not able to fix the shift-reduce conflict in the following state:

State 3:
      expression ::= expression * ASSIGN expression
  (1) expression ::= expression ASSIGN expression *
      function_call ::= expression * LPAREN RPAREN
                    ASSIGN shift  1
                    LPAREN shift  4
                    LPAREN reduce 1   ** Parsing conflict **
                 {default} reduce 1

My thought is that the problem was the ambiguity between a=(b(c)) and (a=b)(c), but I would have thought that giving the function call a higher precedence than assignment would fix it. Any ideas what could be the case?

Answer 1

First and biggest point: a shift-reduce conflict is rarely a real problem. As such, this may well be something you don't need (or even care) to fix.

Second point: unfortunately, it looks to me like you may have over-simplified your grammar. Just for example, the grammar (as you've posted it) looks like both a=(b(c)) and (a=b)(c) should be rejected outright (the only place you've specified an LPAREN, it has to be followed immediately by an RPAREN). What you've posted doesn't give us enough to guess about what's likely to be wrong with the real grammar.

Answer 2

Does this do what you want?

program ::= assignment .

assignment ::= expression ASSIGN assignment .
assignment ::= expression .

expression ::= expression LPAREN RPAREN .
expression ::= IDENTIFIER .

It lets you assign to function calls (which is unusual), but so did your original grammar. I realize this is just a part of a larger grammar.