Bison 消除了可空非终端之间的 reduce/reduce 冲突？

Question

我正在使用 Bison（据我所知，他们默认使用 LL(1) 解析）。

我的语法是这样说的：

function_decl: ID '(' params ')' ':' TYPE ... // body may go here
function_call: ID '(' arguments ')'

params: ID ':' TYPE
     | params ',' ID ':' TYPE
     | %empty

arguments: ID
    | arguments ',' ID
    | %empty

现在，bison 警告说 reduce/reduce 冲突，因为 params 和 arguments 都可以为空（在零参数的情况下 function()).

我的问题是，如何消除（而不是抑制）此冲突？

虽然有人建议使用不同的解析技术，但我想自己弄清楚是否可行（我应该这样做）或者我应该忽略它。

Answer 1

如果您忽略该警告，您将得到一个无法识别没有参数的函数调用的解析器。所以这可能不是一个好主意。

您说得对，冲突是 params 和 arguments 都产生空字符串的结果。因为解析器在读取func()中的)时只能向前看一个符号a，所以它需要决定是否减少一个空的params（这将迫使它继续function_decl) 或一个空的 arguments（它将提交给 function_call）。但是在读取下一个令牌之前无法知道。

最简单的解决方案是避免空缩减，尽管它会使语法稍微冗长。在下文中，params 和 arguments 都不会产生空字符串，function_decl 和 function_call 的额外产生式用于识别这些情况。

function_decl: ID '(' params ')' ':' TYPE ... // body may go here
function_decl: ID '(' ')' ':' TYPE ... 
function_call: ID '(' arguments ')'
function_call: ID '(' ')'

params: ID ':' TYPE
     | params ',' ID ':' TYPE

arguments: ID
    | arguments ',' ID

这是有效的，因为它让解析器推迟调用和声明之间的决定。 LR 解析器可以推迟决策，直到它必须减少；它可以同时打开多个制作，但必须在结束时减少一个制作。

请注意，即使没有冲突，您的原始语法也不正确。如所写，它允许 arguments（或 params）以任意数量的逗号开头。您的意图不是允许 %empty 作为替代的基本情况，而是作为替代的完整扩展。可选逗号分隔列表的正确语法需要两个非终结符：

arguments
    : %empty
    | argument_list
argument_list
    : argument
    | argument_list ',' argument

Bison 消除了可空非终端之间的 reduce/reduce 冲突？

Bison eliminate reduce/reduce conflict among nullable non-terminals?

parsing

nullable

rules

bison

reduce-reduce-conflict