野牛消除减少/减少可空的非终端之间的冲突？

Question

我正在使用Bison（AFAIK，他们使用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