Solving Parsing Conflicts in Tiny Lemon Grammar

Question

I am trying to learn the basics of the lemon parser generator , but I was quickly stuck.

Here's a tiny grammar:

%right PLUS_PLUS. %left DOT. program ::= expr. member_expr ::= expr DOT IDENTIFIER. lhs_expr ::= member_expr. expr ::= lhs_expr. expr ::= PLUS_PLUS lhs_expr. 

It causes 1 analysis of the conflict:

 State 3: (3) expr ::= lhs_expr * (4) expr ::= PLUS_PLUS lhs_expr * DOT reduce 3 expr ::= lhs_expr DOT reduce 4 ** Parsing conflict ** {default} reduce 4 expr ::= PLUS_PLUS lhs_expr 

Whereas if I rewrite the last rule as follows:

 expr ::= PLUS_PLUS expr DOT IDENTIFIER. 

Then it does not cause conflicts. But I do not think this is the right way.

I would appreciate it if someone could explain what is right and why.

Answer 1

So you wrote an ambiguous grammar that says:

  ++ x . y 

with two interpretations:

  [++ x ] . y 

and

  ++ [x . y] 

where [] is just my way of showing groups.

Lemon is an L (AL) R parser, and such parsers simply do not handle ambiguities (multiple interpretations). A decrease-decrease conflict is reported that occurs when the parser reaches this midpoint; it groups "++ x" as "[++ x]". or like "++ [x.]"? Both options are valid and cannot be safely selected.

If you stick with Lemon (or another LALR parser generator), you need to get rid of the problem by changing the grammar. You can use the GLR parser generator; he would agree and give you both analyzes. But all you did then was push the problem of resolving ambiguity into a phrase after parsing. Since you do not want ambiguity, you can avoid this during parsing if you can. In this case, I think you can.]

I think you are trying to create a C-like language. So you want something like this:

 primitive_target ::= IDENTIFIER ; primitive_target ::= IDENTIFIER '[' expr ']' ; access_path ::= primitive_target ; access_path ::= access_path '.' primitive_target ; lhs ::= access_path ; lhs ::= PLUS_PLUS access_path ; lhs ::= access_path PLUS_PLUS ; program ::= expr ; expr ::= term ; expr ::= expr '+' term ; term :::= '(' expr ')' ; term ::= lhs ; term ::= lhs '=' expr ; term ::= constant ;