解决yacc/ocamlyacc中减少/减少冲突的问题

Question

我正在尝试解析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 $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

不幸的是,我能提出的唯一答案意味着增加语法的复杂性.

1. 拆分expr成simple_expr和expr_with_prefix
2. 仅允许simple_expr或(expr_with_prefix)在APPLY中

第一步将减少/减少冲突转变为转换/减少冲突,但括号解决了这个问题.

你会遇到与'ab 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