首页 / 知识

关于解析：解决yacc / ocamlyacc中的减少/减少冲突

2023-04-13 00:37:00

关于解析：解决yacc / ocamlyacc中的减少/减少冲突

Resolving reduce/reduce conflict in yacc/ocamlyacc

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
%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"( 减法)。 减法减法是正确的。 我如何解决冲突以支持该规则？

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

  • 将expr分为simple_expr和expr_with_prefix
  • 在APPLY中仅允许simple_expr或(expr_with_prefix)

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

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    expr := INT
          | parenthesized_expr
          | expr MINUS expr

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

    applied_expr := expr expr

    expr_with_prefix := MINUS expr

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

    冲突语法运算符应用程序

    最新内容

    相关内容

    热门文章

    推荐文章

    标签云

    猜你喜欢