错误恢复目标定位

• 尽可能地使用户的源程序，通过一遍编译检查，发现所有错误，并为用户提供错误解决办法。

关于几种LR(1)错误恢复方式的可行性分析

紧急方式恢复———基于舍去部分输入的恢复方式

• 算法概述

  1. 从栈顶开始退栈，可能弹出0个或若⼲个状态，直到出现状态S为⽌，根据S在goto⼦表中可以找到⼀个⾮终结符号A，即它有关于A的的的转移；
  2. 抛弃0个或若干个输入符号，直到找到符号a为止，a属于FOLLOW(A)，即a可以合法地跟在A的后面；
  3. 分析器把状态goto[S,A]压入栈，继续进行语法分析。

• 本质：忽略掉关于非终结符S之后的规约错误。

• Exemplify：

  program example(input,output);
    const PI = 3.141592654
    var r, d, c : real;
    begin
        read(r);
        d := 2 * r;
        c :=  PI * d;
        write(c);
    end.
  

  • 这里的错误存在于"const_declaration->id = const_value"，"const_declarations->const const_declaration ;"规约之前，此刻状态与符号栈内容为：
    错误发生时分析栈状态

  • 如果我们选择状态4为S，状态4的分析行如下：
    分析表-1
    分析表-2

  • 后续的部分输入：

    1	2	3	4	5	6	7	8	9	10	..
    var var	r id	, ,	d id	, ,	c id	: :	real real	; ;	begin begin	..

• 如果选择非终结符A尾const_declaration，那么分号';'属于其FOLLOW集，退栈至状态4和符号;，同时抛弃掉输入栈中的1~8符号，之后goto[4,const_declaration]=7，状态压栈7，符号压栈const_declaration，此时符号状态栈为：

  State Stack	7	4	2	0
  Symbol Stack	const_declaration	;	program_head	-

• 输入栈变为：

  1	2	3	4	5	..
  ; ;	begin begin	read read	( (	r r	..

• 缺陷与限制：一旦出现错误，局部代码的分析会被舍去，舍去的分析部分大小取决于状态S的选择；同时错误的数量与位置也会影响检错结果，如上例中，若var r, d, c : real后也无分号;，那么从var开始到end的检测都会被忽略。

• 可行性评估：针对某些错误恢复，具有一定的逻辑性，可定义一个特定的恢复状态S的集合来实现，尽可能的降低错误发生时被舍去部分的大小；但是本方法对于多种错误同时发生时的检测，存在一定的局限性。

短语级恢复

• 算法概述
  1. 对剩余输入作局部纠正，用可以使分析器继续分析的串来代替剩余输入的前缀；
  2. 尽量避免从分析栈中弹出与非终结符有关的状态，因为归约出的非终结符都是分析成功的。
• 本质：通过手动分析分析表中的一些空白错误表项，编写错误类型的解决方案，当发生错误时，根据错误的输入查找已知的错误类型进行解决。
• 可行性评估：错误恢复能力强，但是需要手动编写错误类型及其解决方案，对于分析表中状态较多的情况下，可行性方面存在绝对的局限性。

Burke-Fisher方法

• References:
  • Michael Burke, Gerald A. Fisher Jr., A PRACTICAL METHOD FOR SYNTACTIC ERROR DIAGNOSIS AND RECOVERY, Courant Institute New York University, 251 Mercer Street, New York, New York 10012, 1982
  • Mariza A. S. Bigonha, Roberto S. Bigonha, A Powerful LR(1) Error Recovery Mechanism in the Compiler Implementation System Environment
• 算法概述：
  • Primary Recovery Phase（首次恢复）：通过尝试插入，替换，删除三种策略，找到使得分析程序得以继续执行的恢复方法。恢复方法的选取，取决于该恢复方法能否支持分析栈继续向后识别输入栈中的步数达到MINCHECK，即最短分析距离；
  • Secondary Recovery Phase（第二次恢复）：建立在第一次恢复失败的情况下，通过舍去一部分分析栈中的状态和符号，以达到错误恢复的目的，类似于上述紧急恢复方式；
  • Scope Recovery（作用域恢复）。

• 分析栈结构：
  PS: 错误发生时的符号与状态栈.
  

  PE: 草稿栈，用于尝试不同策略的错误恢复.
  分析栈结构
• Exemplify：
  • Pascal code:

    program example(input,output);
    const PI = 3.141592654
    var r, d, c : real;
    begin
        read(r);
        d := 2 * r;
        c :=  PI * d;
        write(c);
    end.
    

  • Parse Stack of State and Symbol when error occurred:
    错误发生时分析栈状态
  • Primary Recovery:
    • Insertion:
      当前符号（current-token）是 var，发现无移进或者规约动作，则将current-token送回input-buffer中，使用PS保存当前分析栈，检查38号状态的所有可行动作，每次尝试插入一种可行的终结符，即如下图中38号状态仅有终结符;存在下一步的动作，故尝试插入;于var之前，在PE中继续进行分析，若能达到MINCHECK，则通过测试，视为一种可行的恢复方式。
      分析表-3
    • Substitution:
      同理，操作当前的input-buffer和PS，不同的是将var替换为;，进行分析，但是在此种情况下，替换并非可行的策略，因为其无法达到MINCHECK；但对于如下情况却可适用：

    program example(input,output);
    const PI = 3.141592654;
    var r, d, c : real;
    begin
        read(r);
        c :=  PI * 2 r r;       // 替换为 c :=  PI * 2 + r; 或者 c :=  PI * 2 * r; 等等...
        write(c);
    end.
    

    • Deletion:
      针对var的删除策略也是无效的，但是可有效应对如下情况：

    program example(input,output);
    const PI = 3.141592654
    var r, d, c : real;
    begin
        read(r);
        if r > 0 then then c :=  PI * 2 * r // 删除then后，恢复为 if r > 0 then c :=  PI * 2 * r;
                else c := 0;
        write(c);
    end.
    

• 可行性分析：算法逻辑性强，针对的问题分析较为全面，可行性较强。
• 可试用包含该错误恢复方法的 LR1-Parser 项目进行测试和理解，其中包含YAML格式的Pascal-S 相关语法规则文件和CSV格式的LR(1)分析表文件。