parsing - 解析器错误恢复可以由语法自动引导吗？

Question

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

我使用紫龙书来帮助我进行设计，从中我了解到解析器中有四种错误恢复方法:

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

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

解析器不能只将当前产生式可以简化为同步标记的所有非终结符中的符号视为同步标记，而不是选择同步标记吗？我还没有真正弄清楚它的工作效果如何 - 我想象解析器处于正在进行的产品链中，但当然这不是自下而上解析器的工作方式。尝试找到可行状态时会产生太多不相关的错误吗？它会尝试将解析器恢复到无效状态吗？有没有一种好方法可以用有效的错误操作预先填充解析器表，以便实际的解析程序在遇到错误时不必推理下一步该去哪里？

Answer 1

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

这并不是说自动化程序还没有被尝试过。 解析理论(Sippu & Soisalon-Soininen)中有一个很长的章节。 (不幸的是，this article 是付费的，但如果您有 ACM 成员(member)资格或可以访问好的图书馆，您可能可以找到它。)

总体而言，yacc 策略已被证明“并不糟糕”，甚至“足够好”。有一种众所周知的方法可以让它变得更好，那就是收集非常糟糕的语法错误消息(或失败的错误恢复)，将它们跟踪到它们发生时的事件状态(这很容易做到)，并附加一个到该精确状态和前瞻标记的错误恢复过程。例如，参见Russ Cox's approach .