抽象语法错误对于人类来说通常很容易修复，但不适用于一般的解析器，也不适用于特定的LR解析器。传统的“恐慌模式”错误恢复，虽然易于实现且适用于任何语法，但通常会导致一系列错误，从而淹没了原始错误。更先进的错误恢复技术受到这个问题的影响较小，但几乎没有实际用途，因为它们的典型性能被认为很差，其最坏情况是无界的，并且它们报告的修复是随意的。在本文中，我们介绍了CPCT+算法，以及该算法的一个实现，以解决这些问题。首先，CPCT+报告给定位置的完整的最低成本维修序列集，允许程序员选择最适合他们意图的序列。其次，在一个包含200,000个实际无效JAVA程序的语料库上，CPCT+能够在0.5s的超时时间内修复98.37%±0.017%的文件。最后，CPCT+使用完整的最低成本修复序列集来减少级联错误问题，其中错误恢复不正确会导致进一步识别虚假语法错误。在整个测试语料库中，CPCT+向用户报告435,812±473个错误位置，与死机模式报告的981,628±0个错误位置相比，大大减少了级联错误问题。
编程是一项卑微的工作，它要求我们承认，在追求完美程序的过程中，我们会犯下数不清的错误。最麻烦的是语义错误，我们打算让程序做一件事，但它却做了另一件事。不那么麻烦，但通常也同样令人恼火的是语法错误，这些错误通常是对编译器所要求的严格语法的微小偏差。语法错误是如此普遍，以至于现代编译器中的解析器被设计来应对我们犯下的几个错误：它们不是在第一个语法错误时停止，而是试图从它中恢复。这允许他们报告，而我们可以修复OneGo中的所有语法错误。
当错误恢复运行良好时，这是一种有用的工作效率提升。不幸的是，大多数当前错误恢复方法都过于简单化。最常见的语法中立的错误恢复方法是那些被描述为“恐慌模式”(例如，[13，p.348])的算法，它们跳过输入，直到解析器找到它能够解析的东西。THSIDA的一种更特定于语法的变体是跳过输入，直到达到预定的同步标记(例如，Java中的‘；’)[8，p.P3]，或者尝试插入单个同步标记。这样的策略通常是不成功的，会导致一系列虚假的语法错误(例如，请参见图1)。程序员很快就知道，只有文件中第一个错误的位置--而不是报告的修复，或者后续错误的位置--才能被认为是准确的。
在第2列和第9行解析错误代码。修复错误序列发现：第2行：第1行：第1行：第2行：删除第2行：第3行：第3行：第3行：第3行：第3行：第3行：第2行：第2行：第2行：第2行：第9行。
C..。JAVA：2：t error：‘；’is expecedinginging.xmy.cn；=1^.c.。JAVA：2：错误：！<；标识符>；预期为INT_xOY；_INT_INT_OX_Y；_^。
可以为特定语言手工创建错误恢复算法。它们通常可以更好地从错误中恢复，但创建起来很有挑战性。例如，Eclipse IDE中的Java错误恢复方法有5KLoC长，这使得它只比Berkeley Yacc的现代版本(一个完整的解析系统)稍小一点！毫不奇怪，现实世界中很少有解析器包含有效的手写错误恢复算法。
我们中的大多数人都非常习惯于这些权衡(廉价的通用算法和糟糕的恢复，昂贵的手写算法和合理的恢复)，以至于我们认为它们是不可避免的。然而，在更高级的通用错误恢复算法方面还有很长的工作要做。可能最早的这样的算法是Aho和Peterson[1]，它在遇到错误时动态创建另一种(可能有歧义的)语法，从而使解析器恢复。这个算法在编程语言界已经失宠，可能是因为它的实现复杂，而且很难向用户解释使用了什么恢复。一个更简单的算法家族，它们的根源可以追溯到Fischer等人[11]，而是试图找到允许解析器恢复的单个最小成本的令牌插入和删除修复序列。与幼稚的方法相比，这个家族中的算法在从错误中恢复方面要好得多，并且能够以人类可以轻松复制的方式传达它们找到的修复结果。然而，这样的算法几乎没有实际用途，因为它们的典型性能被认为是糟糕的，并且它们的最坏情况是无界的[17，第14页]。我们还添加了进一步的投诉：这类问题只向用户报告单一的维修顺序。一般说来，尤其是非句法丰富的语言，有多个合理的修复序列
我们在20万个真实的、语法错误的Java程序的语料库上验证CPCT+(第296节)。cpct+能够在0.5s超时内恢复98.37%±0.017%的文件，而且报告的错误位置不到传统死机模式算法的一半：换句话说，cpct+大大减少了级联错误问题。我们还首次展示了-据我们所知-高级错误恢复可以自然地添加到Yacc-esqq系统中，允许用户在错误恢复应用于输入时做出细粒度的决定(第7节)。我们认为，这表明像CPCT+这样的算法已经做好了广泛使用的准备，无论是它们自己，还是作为多阶段恢复系统的一部分。
我们所知道的唯一具有类似“可接受时间”概念的工作是[6]，他们将其定义为每个文件用于错误恢复的总时间，阈值为1秒。我们使用这个定义有一个改变：由于许多编译器能够在不到1秒的时间内完全执行，我们觉得更严格的阈值更合适：我们使用0.5秒，因为我们认为即使是要求最高的用户也会容忍这样的延迟。我们强烈证实了这一假说。
完整的最低成本修复序列集使程序员更有可能看到与其原始意图相匹配的修复序列(示例见图1；附录A包含Java、Lua和PHP的更多示例)。它还打开了一个新的机会。以前的错误恢复算法找到单个修复序列，将其应用于输入，然后继续解析。虽然该修复序列可能是一个合理的局部选择，但它可能会在以后导致级联错误。因为我们有最小成本维修序列的完整集合，所以我们可以从该集合中选择一个引起较少级联错误的维修序列。因此，我们根据修复序列允许解析成功地继续进行的程度来对修复序列进行排名(直到阈值-解析整个文件通常成本太高)，并从得到最远的子集中选择(注意，这样做所需的时间包括在0.5s超时中)。因此，我们还检验了第二个假设：
根据最小成本修复序列的完整集合允许分析在多大程度上局部继续来排序减少了全局级联错误问题。
我们也有力地验证了这一假设。为此，我们将“正常”CPCT+与简单的变体CPCT+rev进行比较，CPCT+rev颠倒了排名过程，总是从性能最差的最低成本修复序列中进行选择。CPCT+rev在Fischer等人中对以前方法的最坏情况进行了建模。家族，该家族非确定性地选择单个最小CostrePair序列。cpct+rev导致报告的错误增加31.93%±0.289%(即它实质上加剧了级联错误问题)。
本文的结构如下。我们描述了Corchuelo等人。算法(第4节)，填充原始描述中缺失的细节并更正其定义。然后我们将算法扩展到CPCT+(第5节)。最后，我们在20万个真实的、语法错误的Java程序的语料库上验证了CPCT+，并将其与Panic模式和Corchuelo等人的实现进行了比较。(第(6)条)。为了强调我们的算法是语法中立的，我们在附录A中展示了不同语法上的错误恢复示例。
在本文中，我们假设对解析机制有较高的理解，但在本节中，我们提供了一些定义，并简要回顾了理解本文其余部分所需的相关低级细节。虽然我们为本文创建的解析工具是用Rust编写的，但我们意识到这仍然是一种陌生的语言，因此许多读者都使用Python给出算法，我们希望Python是最熟悉的。
虽然有很多种解析方法，但Fischer等人。错误恢复算法系列设计用于LR(K)解析器[16]。LR解析仍然是使用最广泛的解析方法之一，因为Yacc[14]及其后代(包括我们为本文创建的Rust解析工具)无处不在。我们在本文中始终使用Yacc语法，这样就可以很容易地在与Yacc兼容的解析工具中测试示例。
类似Yacc的工具接受上下文无关文法(Context-Free Grammar，CFG)并从中生成解析器。CFG有一个或多个规则；每个规则都有一个名称和一个或多个结果(通常称为“备选方案”)；每个结果包含一个或多个符号；一个符号引用令牌类型或语法规则。一个规则被指定为启动规则。产生的解析器接受令牌流作为输入，每个令牌流都有一个类型(例如，int)和一个值(例如，7123)-我们假设存在一个类似lex的工具，它可以将字符串拆分成令牌流。严格地说，解析是确定一个令牌流相对于底层语法是否正确的行为。由于这本身很少有用，类似Yacc的工具允许语法指定“语义操作”，当语法中的一个结果成功匹配时将执行这些操作。除非另有说明，否则我们假设语义动作构建了一棵解析树，将令牌排序为非终端节点(可以有子节点)和终端节点(不能有子节点)的树。
CFG首先被转换成状态图，这是一个状态机，其中每个节点包含一个或多个项(描述该点的有效解析状态)，边用终端或非终端重新标记。由于即使在现代机器上，一个规范的(即未合并的)LR状态图可能需要几秒钟的时间来构建，并且需要存储惊人数量的内存，因此我们使用[21]的算法将兼容状态1合并在一起。这一效果非常显著，将我们稍后使用的Java语法从8908个状态减少到1148个状态。然后，状态图被转换为每个状态有一行的状态表。对于每个终端，每行都有明显的空操作(SHIFT、RECEPT或ACCEPT)，对于每个非终端，GOTO状态可能是空的。图2显示了示例语法、其状态图和statetable。
Statetable允许我们定义一个简单、高效的解析过程。我们首先定义两个与statetable相关的函数：action(s，t)返回状态s的操作，如果不存在这样的操作，则返回标记t或ERROR；以及GOTO(s，N)返回状态s和非终端N的GOTO状态，或者如果不存在这样的GOTO状态，则返回ERROR。然后，我们为具有两个简化规则的(解析堆栈，令牌列表)对定义简化关系→LR，如图3所示。完整LR解析→*LR重复应用这两个→LR规则，直到两者都不适用，这意味着动作(sn，t0)要么是接受(即输入已经被完全解析)；要么是错误(即在终端t0检测到错误)。完整分析需要([0]，[t 0…)的起始对。t n，$])，其中状态0预期表示进入状态图的入口点，t 0…。tn是输入令牌序列，“$”是特殊的文件结束(EOF)令牌。
当解析器尚未完成但没有明显的方式继续解析时(即，当动作(sn，t0)=错误时)，错误恢复算法由解析器调用。因此，错误恢复算法使用解析堆栈和剩余输入的序列(我们将其表示为标记列表)来调用：它们可以修改解析堆栈和输入中的一个或两个，以使解析回到正轨。因此，算法之间的区别在于它们取消了哪些修改(例如，修改解析堆栈；删除输入；插入输入)，以及它们如何执行这些修改。
最简单的语法中立的错误恢复算法被广泛称为“恐慌模式”算法(这一系列算法的起源似乎迷失在时间中)。虽然这个家族中有几个成员用于LL分析，但只有一种基本方法可以为LR分析创建语法中立的恐慌模式算法。我们取自Holub[13，p.348]2的公式，算法的工作原理是从解析堆栈中弹出元素，看看堆栈的较早部分是否能够解析下一个输入符号。如果堆栈中没有元素能够分析NextInput符号，则跳过下一个输入符号，恢复堆栈，并重复该过程。在最坏的情况下，该算法保证在EOF令牌处找到匹配。图4显示了该算法的一个更正式的版本。
1 def to Holub(pstack，1个toks)：1个npstack=1个pstack，而tlen(Toks)n>；1个0：3个npstack=1个pstack。copy()和4个命令，同时删除(Npstack)命令和(Npstack)命令0：10：5；如果不执行操作(npstack[-1]，t toks[0])，则返回错误：如果不执行操作(npstack[-1]，n toks[0])，则返回错误：{6}命令返回命令(npstack，n toks)：7：0返回npstack。(npstack[-1]，n toks[0])=1错误：npstack[-1]，t toks[0])。POP()-8个参数，DELL-TOKS[0]-9个参数，无返回。
该算法的优点是简单、快速。例如，考虑图2中的语法和输入‘2++3’。解析器在第二个‘+’令牌上遇到错误，留下解析堆栈[0，2，7]和剩余的输入‘+3’。错误恢复算法现在启动。它首先尝试行动
已经有很多尝试创建比死机模式更好的LR错误恢复算法，其中最多的是我们称之为Fischer等人的那些错误恢复算法。家庭。事实上，这个算法家族的成员太多了，一张纸无法涵盖。因此，我们从最近的一个开始-Corchuelo等人[5]。我们首先解释原始算法(第4.1节)，尽管我们使用了与原始算法不同的符号，填补了几个缺失的细节，并提供了一个更正式的定义。然后，我们进行两个正确性修复，以确保算法总是找到最小成本的修复序列(第4.2节)。由于原始版本几乎没有给出算法如何最好地实现的细节，因此我们然后解释我们的快速实现方法(第4.3节)。
直观地说，Corchuelo等人。算法从错误状态开始，并试图找到一个最小成本修复序列，该序列包括：插入T(“插入类型T的令牌”)、删除(“删除当前偏移处的令牌”)或移位(“解析当前偏移处的令牌”)。该算法完成：如果其达到接受状态或移位“足够”的标记(N次移位，在Corchuelo等人中设置为3)，则成功；或者如果修复序列包含太多删除或插入修复(在Corchuelo等人中分别设置为3和4)，则不成功。或者跨越“太多”的输入(总共N个，在Corchuelo等人中设置为10)。修复序列用尾班修复修剪报告给用户。例如，将[插入x，移位y，删除z，移位a，移位b，移位c]报告为[插入x，移位y，删除z]。
为了找到修复序列，该算法保持配置的广度优先队列，每个配置代表不同的搜索状态；查询被放入队列的配置的邻居；当找到成功的配置时终止搜索。配置的成本是其维修顺序中维修成本的总和。根据定义，配置的邻居具有相同或更高的成本。
1 def/corchuelotal(pstack，1toks)：2def_todo=1[[(pstack，1toks，[])]]3def cur_cst=4def，而3cur_cst<；CLEN(TODO)：如果TODO(TODO[cur_cst])==0：6%.cur_cst[cur_cst]，则将继续进行5：00-8：00；如果继续，将继续进行8：00-7：00[cur_cst].[cur_cst](Cur_Cst)：如果继续，将继续进行8：00。POP()-9小时，如果不执行操作(n[0][-1]，nn[1][0])n==t接受\cr_n_n_Shift(n[2])：n\cr_n_n_Shift(n[2])：n\cr_n=n\cr_n_n(n[2])：n_cr_star(n[1])n-cr_len(n[1])n==nN_TOTAL：*13个月后，将继续为All_cr_star(n[0]中的nbr_r_star(n[0])中的所有NBR用户提供14个月的时间间隔，请参见All_cr_star(n[0])。n[1])：如果Llen(n[2])>；*0日期和日期[2][-1]n[-1]n[-1]n==删除16个月的日期和nbr[2][-1]日期=n插入：*17个月的日期将继续执行18个月的日期.cst日期=10cur_cst日期+rprs_cst(nbr[2])和19个月的日期范围内的n_n(len(Todo)，*cst)的日期范围(len(TODO)，*cst)：(nbr[2])nbr[2]n=n删除nbr[2][-1]日期和nbr[2][-1]n==n插入：*17个月的日期将继续18个月。推送([])21个月，完成待办事项[cst]。追加((NBR[0]，NbR[1]，[\\]22个月后，将不会返回任何一个24：25 def的rrprs_cst(Rprs)：*26个月，如果不返回，则不会返回0个月；27个月，如果不返回，则不会返回28个月；如果r==n，则不会返回29个月的时间。(Rprs)：*28个月，如果r==n，则不会返回；如果r==n，则不会返回；如果r==n，则不会继续返回29个月。(rrprs_cst(Rprs)：*26个月，如果r==t，则不会返回，如果r==t，则继续执行29个月)。*c*+=*1：30*返回*c+31：32 def/all_cr_star(pstack，(TOKS)：将33个(#)穷尽地应用到→*CR关系中，将34个(pStack，#个TOKS)列表返回给由此产生的35个(#个堆栈，#个TOKS，/REPAGE)三倍数的列表(PSTACK，B TOKS，OR REPAIR)。
与原文一样，我们分两部分解释该方法。首先是一个新的缩减关系→CR，它定义了配置的邻居(图5)。第二个是利用→CR关系生成邻居的算法，并确定何时找到成功的配置或错误恢复是否失败(图6)。除了为了清晰而做了几处改变之外，最大的区别是数字6半正式地捕捉到了Corchuelo等人的东西。散文式解释(分布在多个主题中。
.