首页 文章

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

提问于
浏览 次
10

我正在尝试解析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”（减法） . 减法减少是正确的 . 如何解决有利于该规则的冲突？

parsing ocaml grammar yacc

2 回答

  • 8

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

    • 将 expr 拆分为 simple_expr 和 expr_with_prefix

    • 仅在APPLY中允许 simple_expr 或 (expr_with_prefix)

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

    你're going to have the same problem with ' 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
    回复于
  • 0

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

    回复于

相关问题