7

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

我正在使用紫龙书来帮助我进行设计,我从中收集到的是解析器中有四种错误恢复方法:

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

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

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

4

1 回答 1

5

当你试图盲目地追随所有可用的作品时,很容易迷失在死胡同中。有些东西你知道你的语言,解析器生成器很难弄清楚。(例如,跳到下一个语句分隔符很可能允许解析恢复。)

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

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

于 2014-02-16T05:12:45.053 回答