解决yacc/ocamlyacc中的reduce/reduce冲突

Question

我正在尝试解析ocamlyacc中的语法(与常规yacc几乎相同)，它支持无运算符的函数应用程序(如Ocaml或Haskell)，以及二元运算符和一元运算符的普通分类。我得到了一个与'-‘运算符的reduce/reduce冲突，它既可以用于减法，也可以用于否定。下面是我使用的语法示例：

%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

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

在APPLY expr_with_prefix

• allow 中，

1. 将expr拆分为simple_expr和simple_expr或(expr_with_prefix)

第一步是将reduce/reduce冲突转换为shift/reduce冲突，但括号可以解决这一问题。

你用'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

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