parser-generator - 在一个小的柠檬语法中解决解析冲突

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 ;