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

Question

以下（简化的）Bison 语法会产生减少减少冲突：

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

arg_list
    :    ID
    |    arg_list ID
    ;

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

fnbody
    :    '{' '}'
    ;

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

Answer 1

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

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

第三个选择是考虑语法。这并不总是那么容易，并且可能会破坏语法的大小。基本思想是识别冲突的规则并将它们组合成一个可以被解析器识别的规则，并推迟选择最终构造是什么，直到你看够了。

对于此示例，您为冲突案例添加新规则：

expr_or_fnhead:  '(' ID ')'  ;

这可能是一个表达式或 a 的开头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
           ;