我正在尝试解析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  }
| ID
    { ExprId  }
| expr MINUS expr
    { ExprSub(, ) }
| MINUS expr
    { ExprNeg  }
| expr expr %prec APPLY
    { ExprApply(, ) };

问题在于，当我们获得类似" a b"的表达式时，解析器不知道该将其简化为" a(-b)"(b的否定，后跟应用程序)还是" a b"(减法)。减法减法是正确的。我如何解决冲突以支持该规则？

解决方案

回答

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

• 将expr分为simple_expr和expr_with_prefix
• 在APPLY中仅允许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