代码之家 › 专栏 › 技术社区 › Jay Conrod

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

yacc grammar ocaml parsing

10

Jay Conrod · 技术社区 · 17 年前

我试图在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的求反,后跟application)还是“a-b”(减法)。减法是正确的。我如何解决有利于该规则的冲突?

2 回复 | 直到 17 年前

1

8

James A. Rosen 17 年前

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

分裂 expr 进入 simple_expr 和 expr_with_prefix
只允许 简单表达式 或 (expr_with_prefix)

第一步将reduce/reduce冲突转换为shift/reduce冲突,但括号解决了这一问题。

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

2

0

Chris Dodd 14 年前

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