1

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

...

%%

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 表达式和带括号的标识符之间的歧义。

野牛反例

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

let x = 1

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

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

4

1 回答 1

2

这并不是真正的模棱两可。据我所知，你的语言是明确的。但是，当限制为单个前瞻标记时，语法不是确定性的。

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

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

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

    请注意，即使您要求使用 GLR 解析器，Bison 仍会报告冲突，假设您想了解它。但这不再重要，因为 GLR 解析器可以同时处理多个可能的解析，只要语法（最终）是明确的。Bison 必须报告冲突，因为冲突可能是模棱两可的结果，在这种情况下你需要做点什么。您可以使用%expect-rr声明禁止报告。

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

    使用 GLR 解析器，歧义被报告为运行时错误。这可能并不理想，但由于无法提前告知，这是您能做的最好的事情。其他 GLR 解析器生成器将返回两个（或所有）可能的解析，您可以使用 Bison 使用自定义歧义解析器来执行此操作，但在实际应用中，您通常希望语法是明确的。如果 Bison 报告了冲突，您应该使用相关输入测试解析器，并确保它不会因歧义消息而失败。

  2. 更改语法，使其为 LALR(1)。这总是可能的，因为每种 LR(k) 语言都有一个 LALR(1) 语法。甚至有一个（相当）简单的算法可以用来将 LALR(k) 文法转换为 LALR(1) 文法，前提是它k具有已知值。不幸的是，该算法产生了大量的语法，这变得非常难以维护。（我想如果野牛带有自动重写器就可以了，但事实并非如此。）因此，您最好尝试手动重新调整语法，这并不太糟糕，因为只有一个冲突需要两个前瞻令牌，您已经知道它是什么。

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

    ( 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-reduce 冲突处于相同状态-减少冲突，并涉及相同的潜在减少。我们在冲突状态中想要的是让解析器不执行任何可能的归约，宁愿转移)以便以后归约parenthesized_id. 这就是 bison（或 yacc，就此而言）默认会做的事情；在没有任何优先声明的情况下，它解决了有利于转变的冲突，因为转变往往是正确的答案。但它仍然报告冲突；如果你想抑制警告，你可以添加一个稍微有点骇人听闻的优先级声明，它做同样的事情（如果这两种操作都是可能的，最好转向")"减少以 结尾的生产）：IDENTIFIER

    %precedence IDENTIFIER
%precedence ")"

    如果你真的想，你可以弄清楚如何重写括号的规则，这样既不expr_function也expr_term不能产生"(" IDENTIFIER ")"，从而证明（至少对于这个 LALR(2) 语法）有一个 LALR(1) 语法涵盖相同语言。这不漂亮，但它肯定是可行的。您可以在2013 的这个答案中看到一个与您的语法非常相似的示例。

    使用此解决方案，您可以生成一个您知道不模棱两可的解析器。但是您仍然应该进行测试，以确保冲突解决（或复杂的附加规则）实际上解析了您有兴趣解析的语言。

  3. 最后，还有老派的版本（实际被各种bison/yacc语法解析器用来处理产生式规则中分号的可选性所引起的冲突）：通过组合中的两个token来去掉两个token的lookahead词法分析器。换句话说，在您的词法分析器中添加如下内容：

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

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

于 2022-01-06T02:09:46.517 回答