缩小/减少语法

冲突让我们想象一下我希望能够解析这样的值（每行是一个单独的例子）：缩小/减少语法

x 
(x) 
((((x)))) 
x = x 
(((x))) = x 
(x) = ((x))

我写这个YACC语法：

%% 
Line: Binding | Expr 
Binding: Pattern '=' Expr 
Expr: Id | '(' Expr ')' 
Pattern: Id | '(' Pattern ')' 
Id: 'x'

但我得到一个减少/减少冲突：

$ bison example.y 
example.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]

任何提示，如何解决呢？我正在使用GNU野牛3.0.2

来源

2014-09-05 tokland

你的语法不是LR(k)任何k。所以你要么修复语法，要么使用GLR parser。

假设输入开头：

(((((((((((((x

到这里，是没有问题的，因为每一个字符已转移到分析器栈。

但现在呢？在下一步中，必须减少x，并且向前看)。如果将来某处有=，则x是Pattern。否则，它是一个Expr。

您可以修复由语法：

摆脱Pattern，改变Binding到Expr | Expr '=' Expr;
摆脱Expr所有的定义，并与Expr: Pattern

替换它们

第二种选择可能更好在l因为很可能在您想象（或正在开发）的完整语法中，Pattern是Expr的子集，而不是与Expr相同。将Expr分解为Pattern的单位生产，非模式替代将允许您使用LALR(1)解析器解析语法（如果语法的其余部分符合）。

或者您可以使用GLR语法，如上所述。

来源

2014-09-05 15:14:51 rici

谢谢，现在很清楚。在真正的语法模式和表达式中相似但不相同（它们在AST中产生不同的节点）。在野牛中启用GLR解析器的确解决了这个问题（我想性能不会很好，但我不在乎这是否简化了语法）。 – tokland 2014-09-08 10:16:33

减少/减少冲突常常意味着语法中存在一个基本问题。

解决的第一步是获取输出文件（bison -v example.y产生example.output）。野牛2.3说（部分）：

state 7 

    4 Expr: Id . 
    6 Pattern: Id . 

    '='  reduce using rule 6 (Pattern) 
    ')'  reduce using rule 4 (Expr) 
    ')'  [reduce using rule 6 (Pattern)] 
    $default reduce using rule 4 (Expr)

冲突是明确的;在语法读取x（并将其减少到Id）和)之后，它不知道是将表达式减少为Expr还是将其作为Pattern。这提出了一个问题。

我想你应该重写语法而不Expr之一，Pattern：

%% 
Line: Binding | Expr 
Binding: Expr '=' Expr 
Expr: Id | '(' Expr ')' 
Id: 'x'

来源

2014-09-05 15:10:56

谢谢！这确实解决了冲突，但我应该在问题中注意到，真实语法中的模式和表达是相似的，但不完全相同。 – tokland 2014-09-08 10:12:39

缩小/减少语法

回答

相关问题