bison - 如何解决减少减少冲突 :

Question

以下(简化的)Bison 语法会产生 reduce reduce 冲突:

expr
    :    '(' expr ')'
    |    ID
    |    fn
    ;

arg_list
    :    ID
    |    arg_list ID
    ;

fn
    :    '(' ')' fnbody
    |    '(' arg_list ')' fnbody
    ;

fnbody
    :    '{' '}'
    ;

我看到了问题——只有一个前瞻标记，无法判断 (an_id 是 '(' expr ')' 还是 fn。但是我该如何解决呢？

Answer 1

好吧，最简单的答案是在解析器中使用更多的前瞻性——要么使用类似 btyacc 的东西, 或者使用 bison 的 %glr-parser 选项。

第二种选择是在词法分析器中添加先行——在这种情况下，在返回 ')' 标记之前，查看下一个标记是否是 '{' 并返回一个特殊标记，告诉您这是一个您将要结束的 arg_list 而不是带括号的表达式，或者只是将两者作为单个标记返回并适当修改您的语法。

第三种选择是分解语法。这并不总是那么容易，并且可能会增加语法的大小。基本思想是识别冲突的规则并将它们组合成一个可以被解析器识别的单一规则，并推迟选择最终构造是什么，直到您看到足够多为止。

对于这个例子，您为冲突的情况添加了一个新规则:

expr_or_fnhead:  '(' ID ')'  ;

可以是表达式或 fn 的开头，然后修改其他规则以使用它。 fn 规则变为:

fn :  '(' ')' fnbody               /* 0 arg function */
   |  expr_or_fnhead fnbody        /* 1 arg function */
   |  '(' ID arg_list ')' fnbody   /* 2+ arg function */
   ;

expr 规则更复杂:

expr       : ID
           | non_ID_expr
           ;
non_ID_expr: '(' non_ID_expr ')'
           | expr_or_fnhead
           | fn
           ;