如何解决reduce reduce冲突：

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选项。

第二种选择是在词法分析器中添加lookahead --在本例中，在返回')'标记之前，查看下一个标记是否为'{'，然后返回一个特殊标记，告诉您即将结束的是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
           ;