解决 yacc/ocamlyacc 中的减少/减少冲突
题
我正在尝试解析 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”(减法)。减法减少是正确的。我如何解决冲突以支持该规则?
解决方案
不幸的是,我能想到的唯一答案就是增加语法的复杂性。
- 分裂
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
其他提示
好吧,这个最简单的答案就是忽略它并让默认的归约/归约解析来处理它——归约语法中首先出现的规则。在这种情况下,这意味着减少 expr MINUS expr
优先于 MINUS expr
, ,这正是您想要的。看到后 a-b
, ,您希望将其解析为二进制减号,而不是一元减号然后应用。
不隶属于 StackOverflow