How do I fix this parsing conflict?

Question

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.

Answer 1

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.

Answer 2

The grammar as written is ambiguous and incorrect, because you don't actually want to allow selection statements without ELSE in front of another ELSE. The else in that case should bind to the inner selection statement.

You can fix it like this:

statement ::= open_sel
statement ::= closed_sel
statement ::= other

open_sel ::= KWD_IF LPAREN expression RPAREN open_sel
open_sel ::= KWD_IF LPAREN expression RPAREN other

closed_sel ::= KWD_IF LPAREN expression RPAREN closed_sel
closed_sel ::= KWD_IF LPAREN expression RPAREN closed_sel KWD_ELSE statement
closed_sel ::= KWD_IF LPAREN expression RPAREN other KWD_ELSE statement

it's complicated and fussy, and gets much worse if you have multiple kinds of statements like if...else, which is why people generally rely on default conflict resolution in the parser generator.

Authors of parser generator tools know this, so pretty much every parser generator has conflict resolution rules that make if...else work without refactoring the grammar like this.