语法分析器错误恢复可以自动引导吗？

Question

我正在编写一个LALR解析器生成器作为一个宠物项目。

我正在使用紫色的龙书来帮助我进行设计，并且从中收集的信息是解析器中有四种错误恢复方法：

• 紧急模式：开始转储输入符号，直到找到由编译器设计人员预先选择的符号
• 词组级恢复：将输入字符串修改为可以减少当前产量的内容
• 错误产生：通过将错误合并到语法中来预测错误
• 全局更正：短语级别恢复的版本更加复杂（据我所知）

其中两个需要修改输入字符串（我想避免），另外两个需要编译器设计人员预见错误并根据他们对语言的了解来设计错误恢复。但是解析器生成器也具有关于语言的知识，因此我很好奇是否有更好的方法可以从解析错误中恢复而无需预先选择同步标记或用错误产生物填充语法。

解析器不能只选择同步令牌，而不能仅选择当前生产可以减少为同步令牌的所有非终结符后面的符号？我还没有真正弄清楚它的效果如何-我将解析器形象化地放在了一系列正在进行中的产品中，但是，这当然不是自底向上解析器的工作方式。试图找到可行状态会产生太多无关的错误吗？它会尝试以无效状态恢复解析器吗？有没有一种很好的方法来用有效的错误操作预填充解析器表，以便实际的解析程序不必在遇到错误时就知道下一步应该去哪里？

Answer 1

当您试图盲目地关注所有可用的作品时，很容易迷失在死胡同中。有些关于您的语言的知识，解析器生成器很难弄清楚。（例如，跳到下一个语句分隔符很可能允许解析恢复。）

这并不是说没有尝试过自动化程序。Parsing Theory (Sippu & Soisalon-Soininen) 中有很长一段关于它的内容。（不幸的是，这篇文章是收费的，但如果你有 ACM 会员资格或访问一个好的图书馆，你可能会找到它。）

总体而言，yacc 策略已被证明“不可怕”，甚至“足够好”。有一种众所周知的改进方法，即收集非常糟糕的语法错误消息（或失败的错误恢复），将它们跟踪到发生时处于活动状态的状态（这很容易做到），并附加一个错误恢复过程到该精确状态和前瞻令牌。例如，参见Russ Cox 的方法。