« 上一篇下一篇 »

LR语法分析中的错误恢复

LR语法分析器在查询语法分析动作表并发现一个报错条目时,它就检测到了一个语法错误。在查询GOTO表时不会发现语法错误。如果当前已扫描的输入部分不可能存在正确的后续符号串,LR语法分析器就会立刻报错。规范LR语法分析器不会做任何多余的归约动作,会立刻报告错误。SLR和LALR语法分析器可能会在报错之前执行几次归约动作,但是它们决不会把一个错误的输人符号移人到栈中。

在LR语法分析过程中,我们可以按照如下方式实现恐慌模式的错误恢复策略。我们从栈顶向下扫描,直到发现某个状态s,它有一个对应于某个非终结符号A的GOTO目标。然后我们丢弃零个或多个输人符号,直到发现一个可能合法地跟在A之后的符号a为止。之后语法分析器将GOTO(s, A)压人栈中,继续进行正常的语法分析。在实践中可能会选择多个这样的非终结符号A。通常这些非终结符号代表了主要的程序段,比如表达式、语句或块。比如,如果A是非终结符号stmt,a就可能是分号或者。其中,标记了一个语句序列的结束。

这个错误恢复方法试图消除包含语法错误的短语。语法分析器确定一个从A推导出的串中包含错误。这个串的一部分已经被处理,并形成了桟顶部的一个状态序列。这个串的其余部分还在输人中,语法分析器则在输人中査找可以合法地跟在A后面的符号,从而试图跳过这个串的其余部分。通过从栈中删除状态,跳过一部分输入,并将GOTO(s,A)压人栈中,语法分析器假装它巳经找到了A的一个实例,并继续进行正常的语法分析。

实现短语层次错误恢复的方法如下:检查LR语法分析表中的每个报错条目,并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误。然后构造出适当的恢复过程,通常会根据各个报错条目来确定适当的修改方法,修改栈顶状态和/或第一个输入符号。

在为一个LR语法分析器设计专门的错误处理例程时,我们可以在表的动作字段的每个空条目中填写一个指向错误处理例程的指针。该例程将执行编译器设计者所选定的恢复动作。这些动作包括在栈和/或输人中删除或插人符号,也包含替换输人符号或将输人符号换位。我们必须谨慎地做出选择,避免LR语法分析器陷人无限循环。一个安全的策略是保证最终至少有一个输人符号被删除或移人,并且如果到达输人结束位置时要保证栈会缩小。应该避免从栈中弹出一个和某非终结符号对应的状态,因为这样的修改相当于从栈中消除了一个已经被成功分析的语言构造。

« 上一篇下一篇 »