用微小的Lemon语法解决解析冲突

Question

我正在尝试学习Lemon解析器生成器的基础知识,但我很快就陷入了困境.

这是一个很小的语法:

%right PLUS_PLUS.
%left DOT.

program ::= expr.

member_expr ::= expr DOT IDENTIFIER.

lhs_expr ::= member_expr.

expr ::= lhs_expr.
expr ::= PLUS_PLUS lhs_expr.

它导致1个解析冲突:

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

然而,如果我重写最后一条规则如下:

expr ::= PLUS_PLUS expr DOT IDENTIFIER.

然后它不会导致冲突.但我不认为这是正确的方法.

如果有人能解释什么是正确的方式,为什么,我会很感激.

Answer 1

所以你写了一个含糊不清的语法,它接受:

 ++ x . y

有两种解释:

 [++ x ] . y

和

 ++ [x . y]

[]只是我向分组展示的方式.

Lemon是一个L(AL)R解析器,这样的解析器根本不处理歧义(多种解释).报告的reduce-reduce冲突是解析器到达中间点时发生的事情; 它将"++ x"分组为"[++ x]".还是"++ [x.]"？两种选择都是有效的,不能安全地选择.

如果您坚持使用Lemon(或其他LALR解析器生成器),则必须通过更改语法来解决问题.[你可以使用GLR解析器生成器; 它会接受并给你两个解析.但是你所做的就是将解决歧义的问题推到解析后的短语.由于您不想要歧义,如果可以的话,您可以在解析期间避免使用歧义.在这种情况下,我认为你可以.]

我想你正在尝试构建一个类似C语言的语言.所以你想要这样的东西:

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 ;