2

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

至于 ECMAScript 2018 规范（https://www.ecma-international.org/publications/files/ECMA-ST/Ecma-262.pdf，第 11.9 章），分号实际上不是可选的，而是在解析。在规范中，指出：

当从左到右解析源文本时，遇到任何语法生成都不允许的标记（称为违规标记）时，如果一个或多个以下条件为真：

  • 违规标记与前一个标记至少有一个 LineTerminator[...]

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

  • error使用特殊令牌检测错误；
  • 告诉词法分析器在操作期间发生了语法错误；如果在当前标记之前遇到换行符，则词法分析器将在下一次yylex调用时返回一个新的分号标记；在随后的调用中，当语法错误发生时，它将返回先前是有问题的令牌。

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

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一个，并且先前的有效指令丢失了，使得分号插入无用。

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

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

4

1 回答 1

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需要能够推断出这不是“真正的”错误，这意味着它必须深入yyparse's 的胆量。（我确信这是可能的，但我不知道该怎么做，而且在我看来这并不值得推荐。）

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

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

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

证明该算法有效更棘手，因为理论上它可能是在某些上下文中A可以遵循的情况，但在当前上下文中是不可能的，而在当前上下文中是可能的。在这种情况下，您可能会错过可能的分号插入。我没有详细查看最近的 JS 版本，但很久以前，当我写一个 JS 词法分析器时，我成功地证明了不存在这样的情况。BA ; B

注意：由于问题是在评论中提出的，我会稍微挥手，尽管我真的不建议采用这种方法。

如果不深入了解野牛的胆量，就真的不可能“解除”一个令牌，包括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(); }

这对于“错误中止”处理来说已经足够了，但是如果你想进行错误恢复，你需要做更多的黑客行为。

正如我所说，我真的不建议走这条路。即使它有效，最终结果也不会很漂亮（如果您没有考虑过，您仍然可能会发现您认为有效的代码在实际用户输入上失败了。）

于 2018-09-26T17:41:25.900 回答