解决yacc/ocamlyacc中的减少/减少冲突 [英] Resolving reduce/reduce conflict in yacc/ocamlyacc

问题描述

我正在尝试解析ocamlyacc(与常规yacc几乎相同)中的语法，该语法支持不带运算符的功能应用程序(例如Ocaml或Haskell)，以及二进制和一元运算符的常规分类.我与'-'运算符发生了减少/减少冲突，该操作符可用于减法和负运算.这是我正在使用的语法示例:

I'm trying to parse a grammar in ocamlyacc (pretty much the same as regular yacc) which supports function application with no operators (like in Ocaml or Haskell), and the normal assortment of binary and unary operators. I'm getting a reduce/reduce conflict with the '-' operator, which can be used both for subtraction and negation. Here is a sample of the grammar I'm using:

%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"(减法).减法减法是正确的.我如何解决冲突以支持该规则?

The problem is that when you get an expression like "a - b" the parser doesn't know whether this should be reduced as "a (-b)" (negation of b, followed by application) or "a - b" (subtraction). The subtraction reduction is correct. How do I resolve the conflict in favor of that rule?

推荐答案

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

Unfortunately, the only answer I can come up with means increasing the complexity of the grammar.

1. 将expr拆分为simple_expr和expr_with_prefix
2. 在申请中仅允许simple_expr或(expr_with_prefix)

1. split expr into simple_expr and expr_with_prefix
2. allow only simple_expr or (expr_with_prefix) in an APPLY

第一步将您的减少/减少冲突转变为转移/减少冲突，但是括号可以解决该问题.

The first step turns your reduce/reduce conflict into a shift/reduce conflict, but the parentheses resolve that.

您将对'a b c'遇到相同的问题:是a(b(c))还是(a(b))(c)?您还需要分解语法中的applied_expression和必需的(applied_expression).

You're going to have the same problem with 'a b c': is it a(b(c)) or (a(b))(c)? You'll need to also break off applied_expression and required (applied_expression) in the grammar.

我认为这可以做到，但是我不确定:

I think this will do it, but I'm not sure:

expr := INT
      | parenthesized_expr
      | expr MINUS expr

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

applied_expr := expr expr

expr_with_prefix := MINUS expr

这篇关于解决yacc/ocamlyacc中的减少/减少冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！