Bison reduce/reduce lambda 表达式和带括号的标识符之间的冲突

Question

我正在尝试编写自己的编程语言，我有以下简化语法：

...

%%

prog: stmtlist | %empty;

block: "{" stmtlist "}";

stmtlist: stmtlist ";" stmt | stmt;
decllist: decllist "," decl | decl;
exprlist: exprlist "," expr | expr;

stmt: stmt_decl;

stmt_decl
    : "let" decllist "=" exprlist
    | "let" decllist
    ;

decl: IDENTIFIER ":" IDENTIFIER | IDENTIFIER;

expr: expr_function;

expr_function
    : "(" decllist ")" "->" expr_function
    | "(" decllist ")" "->" block
    | "("          ")" "->" expr_function
    | "("          ")" "->" block
    | expr_additive
    ;

expr_additive
    : expr_additive "+" expr_primary
    | expr_additive "-" expr_primary
    | expr_primary
    ;

expr_primary: INTVAL | FLTVAL | IDENTIFIER | "(" expr ")";

%%

...

但是，当我尝试生成 C++ 解析器时，我遇到了一个 reduce/reduce 冲突。

$ bison -v -Werror -l --defines=parser.hh -o parser.cc parser.yy
parser.yy: error: 1 reduce/reduce conflict [-Werror=conflicts-rr]
parser.yy: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples

这里是生成的 parser.output 文件的相关部分：

State 27 conflicts: 1 reduce/reduce

...

State 27

   13 decl: "identifier" • ":" "identifier"
   14     | "identifier" •
   26 expr_primary: "identifier" •

    ":"  shift, and go to state 11

    "+"       reduce using rule 26 (expr_primary)
    "-"       reduce using rule 26 (expr_primary)
    ")"       reduce using rule 14 (decl)
    ")"       [reduce using rule 26 (expr_primary)]
    $default  reduce using rule 14 (decl)

这里是反例的屏幕截图，显示问题是 lambda 表达式和带括号的标识符之间存在歧义。

在我的语言中，我希望能够支持以下语法。我想我理解这个问题，但我很难解决 reduce/reduce 冲突。

let x = 1

let foo = (x)           // `foo` is the same type as `x`
let bar = (y) -> y + 1  // `bar` is a function

有人可以告诉我我需要做什么才能让它正常工作，或者给我指出一些可以帮助我解决问题的资源吗？

Answer 1

还真不是模棱两可。据我所知，你的语言是明确的。但是，当仅限于单个先行标记时，语法不是确定性的。

非常有用的反例生成器确实描述了问题。当解析器在 let foo = (x) 中看到 ) 时，它必须决定 x 是 decl 还是 expr_primary。一旦看到第二个标记，答案就会显而易见；如果 ) 后跟 ->，则括号包含 decl_list；否则，括号包含 expr。所以没有歧义。但这不一定对你有帮助:-)

LALR(2) 文法——这就是你所拥有的——是一个长期存在的问题，解决它们的三个基本策略是：

使用 GLR 解析器。这当然是最简单的策略；它所需要的只是将 %glr-parser 添加到您的解析器声明中。（如果您的语义类型与 C 不兼容，您可能还需要更新您的 bison 版本并可能指定不同的解析器框架，具体取决于您的 bison 版本。）GLR 解析器可以解析任何明确的语法，而不管前瞻性有多少必需的。额外的灵活性是有代价的，但在使用 GLR 解析 LALR(2) 语法的情况下，成本几乎可以忽略不计。

请注意，即使您请求 GLR 解析器，Bison 仍会报告冲突，前提是您希望了解它。但它不再重要，因为 GLR 解析器可以同时处理多个可能的解析，只要语法（最终）是明确的。 Bison 很可能必须报告冲突，因为冲突可能是歧义的结果，在这种情况下您需要做一些事情。您可以使用 %expect-rr 声明来禁止报告。

没有算法可以判断任意文法是否有歧义。 Bison 尽最大努力提供反例报告，但它并不总是有效，而且它当然也不总是表示有歧义。但是如果语法恰好没有歧义，GLR 解析器就可以工作。

对于 GLR 解析器，歧义被报告为运行时间错误。这可能并不理想，但由于无法提前告知，这是您能做的最好的事情。其他 GLR 解析器生成器将 return 两种（或所有）可能的解析，您可以使用自定义歧义解析器对 Bison 进行解析，但在实际应用中，您通常希望语法是明确的。如果 Bison 报告冲突，您应该使用相关输入测试解析器并确保它不会因歧义消息而失败。
更改语法，使其成为 LALR(1)。这总是可能的，因为每个 LR(k) 语言都有一个 LALR(1) 文法。甚至有一个（相当）简单的算法可以用来将 LALR(k) 文法转换为 LALR(1) 文法，前提是 k 具有已知值。不幸的是，该算法会产生大量语法，这些语法变得极难维护。（我想如果 bison 带有自动重写器就没问题，但事实并非如此。）所以你最好尝试手动重新调整语法，这并不太糟糕，因为只有一个冲突需要两个先行标记，您已经知道它是什么了。

解决方案的大致轮廓如下：

问题是解析器在看到下一个标记之前无法判断 ( IDENTIFIER ) 是什么。所以我们需要做的就是让解析器不必对该特定 IDENTIFIER 执行单位缩减。为此，我们可以创建一个冗余的非终端并添加使用它的产品：
```
parenthesized_id: "(" IDENTIFIER ")"
expr_primary: parenthesized_id
expr_function: parenthesized_id "->" block
             | parenthesized_id "->" expr_function
```
这是最简单的部分，从某种意义上说，这就是所需要的（至少在本例中）。如果将这些规则添加到语法中，bison 将报告您现在有两个 shift-reduce 冲突和一个 reduce-reduce 冲突，但这有点误导，因为 reduce-reduce 冲突与其中一个 shift-减少冲突，并涉及相同的潜在减少。我们希望在冲突状态下解析器不执行任何可能的归约，而是更愿意移动 ) 以便稍后归约 parenthesized_id。这就是 bison（或 yacc，就此而言）默认会做的事情；在没有任何优先声明的情况下，它解决了有利于转移的冲突，因为转移通常是正确的答案。但它仍然报告冲突；如果你想抑制警告，你可以添加一个稍微有点老套的优先声明，它做同样的事情（如果这两种操作都可能的话，更喜欢移动 ")" 来减少以 IDENTIFIER 结尾的生产）：
```
%precedence IDENTIFIER
%precedence ")"
```
如果你真的想要，你可以想出如何重写括号的规则，使得 expr_function 和 expr_term 都不能产生 "(" IDENTIFIER ")"，从而证明（至少对于this LALR(2) grammar) 有一个 LALR(1) grammar 覆盖了相同的语言。这不是很漂亮，但它肯定是可行的。您可以在 this answer from 2013.
中看到一个与您的语法非常相似的示例
使用此解决方案，您可以生成一个您知道没有歧义的解析器。但是您仍然应该进行测试，以确保冲突解决（或复杂的附加规则）确实解析了您感兴趣的语言。
最后是老派版本（实际上被各种bison/yacc语法解析器用来处理生产规则中分号的可选性引起的冲突）：摆脱通过在词法分析器中组合两个标记 来实现双标记前瞻。换句话说，添加到你的词法分析器中：

[)][[:space:]]*-> return CLOSE_ARROW;

然后通过将 ')' 替换为 CLOSE_ARROW 来更改 lambda 语法的各种产生式。如所写，该模式不允许用户在右括号和箭头之间添加注释，但这应该不是什么大问题。（bison 词法分析器使用更复杂的策略，在这种情况下总是缓冲 ) 并继续扫描；如果结果是下一个标记被 returned（即既不是空格也不是comment) 是 ->，那么组合的标记可以 returned；否则，两个标记（) 和后面的任何标记）需要单独 returned。

Bison reduce/reduce lambda 表达式和带括号的标识符之间的冲突

Bison reduce/reduce conflict between lambda expression and parenthesized identifier

grammar

bison

reduce-reduce-conflict

ambiguous-grammar