用微型Lemon语法解决解析冲突

Question

我正在努力学习Lemon parser generator的基础知识，但我很快就学会了。

这里有一个很小的语法：

%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 ;