bison/yacc 中的特定错误恢复

Question

我正在阅读 Kenneth Louden 的 "Compiler Construction, Principles and Practice" 一本书，并试图了解 Yacc 中的错误恢复。

作者正在使用以下语法给出示例：

%{
#include <stdio.h>
#include <ctype.h>

int yylex();
int yyerror();
%}

%%

command : exp { printf("%d\n", ); }
        ; /* allows printing of the result */

exp : exp '+' term { $$ =  + ; }
    | exp '-' term { $$ =  - ; }
    | term { $$ = ; }
    ;

term : term '*' factor { $$ =  * ; }
     | factor { $$ = ; }
     ;

factor : NUMBER { $$ = ; }
       | '(' exp ')' { $$ = ; }
       ;

%%

int main() {
  return yyparse();
}

int yylex() {
  int c;

  /* eliminate blanks*/
  while((c = getchar()) == ' ');

  if (isdigit(c)) {
    ungetc(c, stdin);
    scanf("%d\n", &yylval);
    return (NUMBER);
  }

  /* makes the parse stop */
  if (c == '\n') return 0;

  return (c);
}

int yyerror(char * s) {
  fprintf(stderr, "%s\n", s);
  return 0;
} /* allows for printing of an error message */

产生以下状态table（以后称为table 5.11）

减少的数字对应于以下作品：

(1) command : exp.
(2) exp : exp + term.
(3) exp : exp - term.
(4) exp : term.
(5) term : term * factor.
(6) term : factor.
(7) factor : NUMBER.
(8) factor : ( exp ).

然后劳登博士举了下面的例子：

Consider what would hapen if an error production were added to the yacc definition
factor : NUMBER {$$ = ;}
       | '(' exp ')' {$$=;}
       | error {$$ = 0;}
       ;
Consider first erroneous input 2++3 as in the previous example (We continue to use Table 5.11, although the additional error production results in a slightly different table.) As before the parser will reach the following point:
parsing stack         input
[=14=] exp 2 + 7          +3$
Now the error production for factor will provide that error is a legal lookahead in state 7 and error will be immediately shifted onto the stack and reduced to factor, causing the value 0 to be returned. Now the parser has reached the following point:
parsing stack                 input
[=15=] exp 2 + 7 factor 4         +3$
This is a normal situation, and the parser will continue to execute normally to the end. The effect is to interpret the input as 2+0+3 - the 0 between the two + symbols is there because that is where the error pseudotoken is inserted, and by the action for the error production, error is viewed as equivalent to a factor with value 0.

我的问题很简单：

他怎么通过查看语法知道为了从这个特定错误 (2++3) 中恢复，他需要向 [= 添加一个 error 伪标记16=]生产？有简单的方法吗？或者唯一的方法是用状态 table 计算出多个例子，并认识到这个特定的错误会发生在这个给定的状态，因此如果我添加一个 error 一些特定产品的伪令牌错误将被修复。

感谢任何帮助。

Answer 1

在那个简单的语法中，错误产生的选项很少，所有这些选项都将允许解析继续。

在这种情况下，选择派生树底部的那个是有道理的，但这不是通用的启发式方法。将错误产生式放在派生树的顶部更为有用，它们可用于重新同步解析。例如，假设我们修改了语法以允许多个表达式，每个表达式在其自己的行中：（这将需要修改 yylex 以便它在看到 \n 时不会伪造 EOF） :

program: %empty
       | program '\n'
       | program exp '\n'  { printf("%g\n", ); }

现在，如果我们只想忽略错误并继续解析，我们可以添加一个重新同步错误生成：

       | program error '\n'

上面的 '\n' 终端将导致标记被跳过，直到可以换行以减少错误产生，以便解析可以继续下一行。

不过，并非所有语言都那么容易重新同步。类 C 语言中的语句不一定由 ; 终止，并且如果错误是例如丢失的 }，那么像上面那样天真地尝试重新同步会导致一定程度的混乱。但是，它将允许解析以某种方式继续，这可能就足够了。

根据我的经验，正确生成错误通常需要大量的反复试验；它更像是一门艺术而不是一门科学。尝试大量错误输入并分析错误恢复会有所帮助。

错误生成的意义在于从错误中恢复。生成良好的错误消息是一个无关但同样具有挑战性的问题。当解析器尝试错误恢复时，错误消息已经发送到 yyerror。（当然，该函数可以忽略错误消息并将其留给错误生产来打印错误，但没有明显的理由这样做。）

产生良好错误消息的一种可能策略是对解析器堆栈和先行标记进行某种 table 查找（或计算）。实际上，这就是 bison 的内置扩展错误处理所做的，并且通常会产生相当合理的结果，因此这是一个很好的起点。已经探索了替代策略。一个很好的参考是 Clinton Jeffrey 2003 年的论文 Generating LR Syntax Error Messages from Examples; you might also check out Russ Cox's explanation，其中介绍了他如何将这一想法应用于 Go 编译器。

bison/yacc 中的特定错误恢复

specific error recovery in bison/yacc

parsing

yacc