ch5自顶向下语法分析(张素琴).ppt

* 七、预测分析的错误恢复 1、发现错误 ①栈顶的终结符与当前输入符不匹配 ②非终结符A位于栈顶，面临的输入符为a，但分析表M的M[A,a]为空 2、“应急”恢复策略 跳过输入串中的一些符号直至遇到“同步符号”为止。 * 3、同步符号的选择 ①把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续 ②把FIRST(A)中的符号加到A的同步符号集，当FIRST(A)中的符号在输入中出现时，可根据A恢复分析 * ③可以把表示语句开始的一些关键字加入到同步记号集中 ④如果栈顶的终结符不能被匹配，就可以弹出该终结符，此时相当于把所有的符号都看作同步符号 用synch 表示由相应非终结符的FOLLOW集得到的同步符号，则前面的预测分析表变为： * FOLLOW(F)=FIRST（E’} ∪FIRST(T’) ={+,),*, ε} FOLLOW(T’)=FOLLOW(T) =FIRST(E’) ∪FOLLW(E) ={+,), # } FOLLOW(T)=FIRST(E’) ∪FOLLOW(E) ={+,), #} FOLLOW(E’)=FOLLOW(E)={), #} * 非终结符 输入符号 E E’ T T’ F id * ( ) # + E→TE’ E→TE’ E’→+TE’ E’ → ε E’ → ε T→FT’ T→FT’ T’ → ε T’ → ε T’ → ε T’ →*FT’ F→(E) F→id 不含错误处理的分析表 * 非终结符 输入符号 E E’ T T’ F id * ( ) # + E→TE’ E→TE’ E’→+TE’ E’ → ε E’ → ε T→FT’ T→FT’ T’ → ε T’ → ε T’ → ε T’ →*FT’ F→(E) F→id 加入错误处理的分析表 synch synch synch synch synch synch synch synch synch * 5.6 典型例题与解答 学p96-99，然后做小测验题。 * 小测验： ?1. 已知文法G[S]： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM 判断G是否是LL(1)文法，如果是，构造LL(1)分析表。 2. 对文法G［S］ S→a|∧|(T) T→T,S|S （1）给出(a,(a,a)) 和(((a,a), ∧,(a)),a)的最左推导。 （2）对文法G进行改写，改写后的文法G’是否LL(1)? 若是，给出它的LL(1)预测分析表，并描述对输入串(a,a)#的分析过程。 * 3. 对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。 (1) A→aABe|a B→Bb|d (3) S→Aa|b A→SB B→ab * * * * 在此处还没有要求文法的类型 * 因此下面就具体地讲解如何解决这两个问题 * * FIRST(aA)={a} FIRST(bA)={b} FIRST(cA)={c} FIRST(ε)={ε} FOLLOW(A)=FOLLOW(B)={#,d} * * 例1：对于文法G[E] E→TE’ E’ → +TE’|ε T →FT’ T’→*FT’| ε F→(E)|id 求每个非终结符的 FIRST和FOLLOW集 解：FIRST(F)={(,id} FIRST(T’)={*, ε} FIRST(T )= FIRST(F) = {(,id} FIRST(E’)={+, ε} FIRST(E)=FIRST(T) ={(,id} * FOLLOW(F)= FIRST（T’) ∪FOLLOW(T’) ={+,),*, #} FOLLOW(E)={), #} E是识别符号 FOLLOW(E’)=FOLLOW(E)={), #} FOLLOW(T’)=FOLLOW(T) =FIRST(E’) ∪FOLLW(E) ={+,), # }　 求FOLLOW(E)，要看E在哪条规则右部出现 E→TE’ E’ → +TE