用于自动分号插入的 Bison 错误恢复

Question

我正在尝试编写用于解析 JavaScript 文件的 Bison C++ 解析器，但我不知道如何使分号成为可选的。

关于 ECMAScript 2018 规范（https://www.ecma-international.org/publications/files/ECMA-ST/Ecma-262.pdf，第 11.9 章），分号实际上不是可选的，而是在解析过程中自动插入的。在规范中，声明：

When, as the source text is parsed from left to right, a token (called the offending token) is encountered that is not allowed by any production of the grammar, then a semicolon is automatically inserted before the offending token if one or more of the following conditions is true:

The offending token is separated from the previous token by at least one LineTerminator[...]

据此，我试图以这种天真的方式解决这个问题：

检测错误，使用error特殊标记；
告诉词法分析器在操作过程中发生了语法错误；如果在当前标记之前遇到换行符，词法分析器将在下一个 yylex 调用时 return 一个新的分号标记；在随后的调用中，它将 return 之前出现语法错误时有问题的标记。

我的解析器的一个非常简化的结构如下所示：

program:
   stmt_list END
;

stmt_list:
    %empty
 |  stmt_list stmt
 |  stmt_list error  { /* error detected; tell the lexer about the syntax error */ }
;

stmt:
    value SEMICOLON
|   [other types of statements...]
;

value:
    NUMBER
|   STRING
;

但是这样做，如果文件包含有效的 JavaScript 语句但没有终止分号，而是换行符，当遇到违规标记时，解析器会将语句的其余部分缩减为error 特殊令牌。当我告诉词法分析器语法错误时，解析器已经将 error 标记减少为 stmt_list 并且之前的有效指令丢失，使得分号插入无用。

显然我不想让我的解析器丢弃有效语句并转到下一个。

我怎样才能做到这一点？这是正确的方法还是我遗漏了什么？

Answer 1

我不认为这种方法可行。

请注意，您必须在进行任何减少之前检测到错误。所以对于语句末尾的分号插入，需要将错误产生式添加到stmt，而不是stmt_list。所以你最终会得到这样的结果：

stmt_list
     :  %empty
     |  stmt_list stmt

stmt: value ';'   { handle_value_stmt(); }
    | value error { handle_value_stmt(); }
    | [other types of statements...]

那不插入分号；它只是假装插入了分号。（如果无法插入分号，则会触发另一个错误。）

但是因为不涉及词法分析器，不管是不是行尾少分号都会出现，太热情了。所以理想的解决方案是以某种方式告诉词法分析器生成一个分号标记作为下一个标记。但是在检测到错误的那一刻，词法分析器已经产生了先行标记，并且解析器知道先行标记是什么。它将使用其记录的先行标记来继续解析。

还有一个问题是此时如何与词法分析器进行通信，因为中间规则操作在错误恢复算法中表现不佳。理论上，您可以使用 yyerror 将被调用的事实来报告错误，但这意味着 yyerror 需要能够推断出这不是 "real" 错误，这意味着它将不得不深入 yyparse 的胆量。（我敢肯定这是可能的，但我不知道该怎么做，而且在我看来也不值得推荐。）

现在，理论上可以告诉解析器丢弃先行标记，并告诉词法分析器生成一个分号，然后重复它刚刚发送的标记。因此，如果您足够顽固，那么通过将 hack 叠加到 hack 上，您几乎不可能完成这项工作。但是你最终会得到一些很难维护、验证和测试的东西。（并确保它适用于所有极端情况也将是一个挑战。）

这还没有考虑其他可以插入分号的情况。

我对 ASI 的方法是通过找出可能的连续标记对来简单地分析语法。（这很容易做到；您只需要构造 FIRST 和 LAST 集合，然后通读所有查看连续符号的产生式。）那么如果输入由标记 A 后跟一个或多个换行符后跟标记 B 组成，并且它在语法中 A 后面不可能有 B，那么这是分号插入的候选。分号插入可能会失败，但这会产生语法错误，因此您不会得到误报。（您可能必须修复语法错误消息，但此时您至少知道您已经插入了一个分号。）

证明该算法有效比较棘手，因为理论上 A 在某些上下文中可以跟在 B 之后，但在当前上下文中这是不可能的，而A ; B 在当前上下文中是可能的。在那种情况下，您可能会错过可能的分号插入。我没有详细查看最近的 JS 版本，但很久以前，当我编写一个 JS 词法分析器时，我设法令自己满意地证明不存在这种情况。

注意：由于问题是在评论中提出的，我会添加一点挥手，虽然我真的不建议遵循这种方法。

如果不深入研究野牛的内脏，就真的不可能 "unshift" 令牌，包括 error 令牌（或多或少是真正的令牌）。到 error 标记被移动时，解析实际上已提交给错误生成。所以如果你想取消错误，你必须接受这个事实并解决它。

在移动 error 标记后，解析器将跳过标记，直到遇到可移动标记。因此，如果您设法将自动分号插入到令牌流中，则可以将该令牌用作守卫：

    stmt: value ';'       { handle_value_stmt(); }
        | value error ';' { handle_value_stmt(); }

但是，您可能没有设法插入自动分号，在这种情况下您确实需要报告语法错误（并可能尝试重新同步）。上面的规则只会默默地将标记丢弃到下一个分号，这肯定是错误的。所以第一个近似值是你的 ASI 插入器总是插入一些东西，它可以在错误产生中用作保护：

    stmt: value ';'       { handle_value_stmt(); }
        | value error ';' { handle_value_stmt(); }
        | value error NO_ASI { handle_real_error(); }

这对于 "abort on error" 处理来说已经足够了，但是如果你想进行错误恢复，你需要做更多的 hackery。

正如我所说，我真的不建议走这条路。最终结果不会很好，即使它有效（而且你仍然可能会发现你认为有效的代码在实际用户输入时失败，如果你没有考虑的话。）

用于自动分号插入的 Bison 错误恢复

Bison error recovery for automatic semicolon insertion

javascript

c++

bison

error-recovery