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

问题描述：

我想解析一个在ocamlyacc中的语法（几乎与常规的yacc相同），它支持没有运算符的函数应用程序（如Ocaml或Haskell）以及正常的分类二元和一元运算符。我得到了与' - '运算符的减少/减少冲突，可用于减法和否定。下面是语法的样品我使用：解决在yacc/ocamlyacc中减少/减少冲突

%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”的分析器不知道这是否应该降低为“（ - b）“（否定b，后面是申请）或”a - b“（减法）。减法减少是正确的。我如何解决冲突，支持该规则？

答

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

分裂expr成simple_expr和expr_with_prefix
只允许在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

`％left APPLY` /`％prec APPLY`解决了`a b c` - 它的左联合（所以它的（a b）c）和较低优先级的含糊性。问题在于，优先规则不适用于表现为减少/减少冲突的歧义。 – 2011-10-06 17:59:03

答

好吧，这简单的答案是，只是忽略它，让默认的减少/降低分辨率处理它 - 减少规则这在语法中首先出现。在这种情况下，这意味着减少expr MINUS expr而不是MINUS expr，这正是你想要的。在看到a-b之后，您想要将其解析为二进制减号，而不是一元减号，然后应用。

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

相关推荐