解决 yacc/ocamlyacc 中的减少/减少冲突

Question

我正在尝试解析 ocamlyacc 中的语法（与常规 yacc 几乎相同），它支持没有运算符的函数应用程序（如 Ocaml 或 Haskell 中），以及二元和一元运算符的正常分类。我遇到了与“-”运算符的归约/归约冲突，该运算符可用于减法和求反。这是我正在使用的语法示例：

%token <int> INT
%token <string> ID
%token MINUS

%start expr
%type <expr> expr

%nonassoc INT ID
%left MINUS
%left APPLY

%%

expr: INT
    { ExprInt $1 }
| ID
    { ExprId $1 }
| expr MINUS expr
    { ExprSub($1, $3) }
| MINUS expr
    { ExprNeg $2 }
| expr expr %prec APPLY
    { ExprApply($1, $2) };

问题是，当你得到像“a - b”这样的表达式时，解析器不知道是否应该将其简化为“a (-b)”（b 的否定，后跟应用程序）或“a - b”（减法）。减法减少是正确的。我如何解决冲突以支持该规则？

Answer 1

不幸的是，我能想到的唯一答案就是增加语法的复杂性。

1. 分裂 expr 进入 simple_expr 和 expr_with_prefix
2. 只允许 simple_expr 或者 (expr_with_prefix) 在申请中

第一步将您的归约/归约冲突转变为移位/归约冲突，但括号解决了这个问题。

对于“a b c”，您也会遇到同样的问题：是吗 a(b(c)) 或者 (a(b))(c)？你也需要中断 applied_expression 并要求 (applied_expression) 在语法中。

我认为这会做到这一点，但我不确定：

expr := INT
      | parenthesized_expr
      | expr MINUS expr

parenthesized_expr := ( expr )
                    | ( applied_expr )
                    | ( expr_with_prefix )

applied_expr := expr expr

expr_with_prefix := MINUS expr

Answer 2

好吧，这个最简单的答案就是忽略它并让默认的归约/归约解析来处理它——归约语法中首先出现的规则。在这种情况下，这意味着减少 expr MINUS expr 优先于 MINUS expr, ，这正是您想要的。看到后 a-b, ，您希望将其解析为二进制减号，而不是一元减号然后应用。