第7讲3.3.6预测的错误恢复

1、温故知新温故知新3.3 自上而下分析3.3.6 预测分析的错误恢复预测分析的错误恢复编译器的错误概述编译器的错误概述 : 词法错误，如标识符、关键字或算符拼写错误词法错误，如标识符、关键字或算符拼写错误 语法错误，如算术表达式的括号不配对语法错误，如算术表达式的括号不配对 语义错误，如算符作用于不相容的运算对象语义错误，如算符作用于不相容的运算对象 逻辑错误，如无穷的递归调用逻辑错误，如无穷的递归调用3.3 自上而下分析分析器对错误处理的基本目标分析器对错误处理的基本目标 清楚而准确地报告错误的出现清楚而准确地报告错误的出现 迅速地从每个错误中恢复过来，以便诊断后迅速地从每个错误中恢复过来，以

2、便诊断后面的错误，并尽量少出现面的错误，并尽量少出现伪错误伪错误 它不应该使正确程序的处理速度降低太多它不应该使正确程序的处理速度降低太多 3.3 自上而下分析非递归预测分析在什么场合下发现错误非递归预测分析在什么场合下发现错误栈顶的终结符和下一个输入符号不匹配栈顶的终结符和下一个输入符号不匹配栈顶是非终结符栈顶是非终结符A，输入符号是，输入符号是a，而，而MA , a是是空白空白3.3 自上而下分析非递归预测分析：采用非递归预测分析：采用紧急方式的错误恢复紧急方式的错误恢复 发现错误时，分析器每次抛弃一个输入记发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定的号，直到输入记号

3、属于某个指定的同步同步记号记号集合为止。集合为止。同步同步词法分析器当前提供的记号流能构成的语词法分析器当前提供的记号流能构成的语法结构，正是语法分析器所期望的。法结构，正是语法分析器所期望的。3.3 自上而下分析同步记号集合的选择同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合。同步记号集合。if expr then（then是是expr的一个同步记号）的一个同步记号）3.3 自上而下分析同步记号集合的选择同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合。同步记号集合。把高层结

4、构的开始符号加到低层结构的同步记号把高层结构的开始符号加到低层结构的同步记号集合中。集合中。a := expr ; if （语句的开始符号作为表达式的同步符号，以（语句的开始符号作为表达式的同步符号，以免遗漏分号时忽略一大段程序。）免遗漏分号时忽略一大段程序。）3.3 自上而下分析同步记号集合的选择同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合。同步记号集合。把高层结构的开始符号加到低层结构的同步记号把高层结构的开始符号加到低层结构的同步记号集合中。集合中。把把FIRST(A)的终结符加入的终结符加入A的同步记号集合。的同步记号集合。

5、3.3 自上而下分析同步记号集合的选择同步记号集合的选择把把FOLLOW(A)的所有终结符放入非终结符的所有终结符放入非终结符A的的同步记号集合。同步记号集合。把高层结构的开始符号加到低层结构的同步记号把高层结构的开始符号加到低层结构的同步记号集合中。集合中。把把FIRST(A)的终结符加入的终结符加入A的同步记号集合。的同步记号集合。如果非终结符可以产生空串，若出错时栈顶是这如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用产生空串的产生式。样的非终结符，则可以使用产生空串的产生式。3.3 自上而下分析同步记号集合的选择同步记号集合的选择把把FOLLOW(A)的所有终结符放入

6、非终结符的所有终结符放入非终结符A的的同步记号集合。同步记号集合。把高层结构的开始符号加到低层结构的同步记号把高层结构的开始符号加到低层结构的同步记号集合中。集合中。把把FIRST(A)的终结符加入的终结符加入A的同步记号集合。的同步记号集合。如果非终结符可以产生空串，若出错时栈顶是这如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用产生空串的产生式。样的非终结符，则可以使用产生空串的产生式。如果终结符在栈顶而不能匹配，弹出此终结符。如果终结符在栈顶而不能匹配，弹出此终结符。 同步记号加到表同步记号加到表3.1的分析表上的分析表上非终非终结符结符输输 入入 符符 号号 id +

7、 * ( ) $E E TE E TE synch synchE E +TE E E T T FT synchT FT synch synchT T T * *FT T T F F id synch synchF (E) synch synch总结一下出错的三种情况：总结一下出错的三种情况：1 查表，表项是空白，栈顶不变，输入串指查表，表项是空白，栈顶不变，输入串指针后移；（相当于抛弃记号）针后移；（相当于抛弃记号）2 查表，表项是查表，表项是synch，弹栈，并且弹出的是，弹栈，并且弹出的是一个非终结符一个非终结符3 栈顶终结符和输入串终结符不匹配，弹栈，栈顶终结符和输入串终结符不匹配，弹栈

8、，将栈顶终结符弹出将栈顶终结符弹出栈输入输出$E+id*+id$出错，跳过（用户多输入了+）$Eid*+id$id属于first（E）$E Tid*+id$E T Fid*+id$E T idid*+id$E T *+id$E T F* *+id$E T F+id$出错：“”正好在F的同步记号集合中，无须跳过任何记号；F被弹出；（用户少输入了id）$E T +id$E +id$E T+id$E Tid$E T Fid$E T idid$E T $E $文法文法G: S-aSb | P P-bPc | bQc Q-Qa | a（1）它是）它是chomsky哪一型文法？哪一型文法？（2）它生成的语

9、言是什么？）它生成的语言是什么？（3）给出提取左因子、消除左递归之后的文法）给出提取左因子、消除左递归之后的文法G（4）求出文法）求出文法G每个非终结符的每个非终结符的First集和集和Follow集集（5）构建文法）构建文法G的的LL（1）预测分析表）预测分析表（6）文法）文法G是否是是否是LL（1）文法）文法（7）利用非递归预测分析程序，验证）利用非递归预测分析程序，验证abacb是否是是否是文法文法G描述的语言的句子描述的语言的句子文法文法G: S-aSb | P P-bPc | bQc Q-Qa | a（1）它是）它是chomsky哪一型文法？哪一型文法？答：它是答：它是2型文法，即上

10、下文无关文法。型文法，即上下文无关文法。（2）它生成的语言是什么？）它生成的语言是什么？答：答：aibjakcjbi | i=0; j,k=1文法文法G: S-aSb | P P-bPc | bQc Q-Qa | a（3）给出提取左因子、消除左递归之后的文法）给出提取左因子、消除左递归之后的文法答：答： S-aSb | P P-bP P-Pc | Qc Q-aQ Q-aQ | S-aSb | PP-bPP-Pc | QcQ-aQQ-aQ | First(S)=a,bFirst(P)=bFirst(P)=a,bFirst(Q)=aFirst(Q)=a, Follow(S)=$,bFollow(P)=$,b,cFollow(P)=$,b,cFollow(Q)=cFollow(Q)=c （4）求出每个非终结符的）求出每个非终结符的First集和集和Follow集集（5）构建）构建LL（1）预测分析表）预测分析表 输入符号输入符号非终结符非终结符abc$SS-aSbS-PPP-bPPP-QcP-PcQQ-aQQQ-aQQ-（6）文法）文法G是否是是否是LL（1）文法）文法答：构建出的答：构建出的LL（1）分析表不含有多重定）分析表不含有多重定义的条目，因此文法义的条目，因此文法G是是LL（1）文法。）文法。（7）利用非递归预测分析程序，验证）利用非递归预测分析