parsinglemon

How do I fix this parsing conflict?

I have a small grammar written in lemon that is causing a parsing conflict.

This is the part of the grammar that is causing the conflict:

selection_statement ::= KWD_IF LPAREN expression RPAREN statement.
selection_statement ::= KWD_IF LPAREN expression RPAREN statement KWD_ELSE statement.

I have seen this answer but it only works for bison/yacc I can't figure out how to replicate it in lemon.

What is the best way to resolve this parsing conflict?

Thanks in advance.

Solution

  • Lemon implements precedence rules in a way that is similar but not quite identical to Bison, and that feature can be used to resolve the "dangling else" shift/reduce conflict which you've encountered, as it is usually applied in bison.

    There are two main differences between Lemon and Bison precedence declarations:

    1. Bison provides %precedence as an alternative to %left, %right and %nonassoc. However, %nonassoc can generally be used anywhere where %precedence would be more appropriate.

    2. In Bison, you can explicitly declare the precedence of a production using %prec TERMINAL. In Lemon, you do the same thing by placing [TERMINAL] after the production. (This is explained in the precedence rules section of the manual, linked above.)

    Also, Bison allows you to use double-quoted strings for terminals, a feature not available in Lemon.

    Putting that together, you can adapt the Bison solution to Lemon as follows:

    /* LEMON (non-terminals abbreviated) */             /* Bison (from linked answer) */
%nonassoc KWD_IF                                    %nonassoc "then"
%nonassoc KWD_ELSE                                  %nonassoc "else"
%%                                                  %%
sel: KWD_IF LPAREN exp RPAREN stm. [KWD_ELSE]       stm: "if" "(" exp ")" stm            %prec "then"
   | KWD_IF LPAREN exp RPAREN stm KWD_ELSE stm.        | "if" "(" exp ")" stm "else" stm

    It is also possible to make the grammar unambiguous, but it's somewhat more work. There's an example of how to do that in the linked Wikipedia entry on dangling else.