编译原理：第四章语法分析-自上而下分析.pptVIP

对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止： 1. 对于文法的开始符号S，置＃于FOLLOW(S)中； 2. 若A→?B?是一个产生式，则把FIRST(?)\{?}加至FOLLOW(B)中； 3. 若A→?B是一个产生式，或A??B?是一个产生式而? ? (即??FIRST(?))， 则把FOLLOW(A)加至FOLLOW(B)中。 例4.6 对于文法G(E) E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i 构造每个非终结符的FIRST和FOLLOW集合： FIRST(E) ={(,i} FIRST(E?)={+, ?} FIRST(T) ={(,i} FIRST(T?)={*, ?} FIRST(F) ={(,i} FOLLOW(E) ={),#} FOLLOW(E?)={),#} FOLLOW(T) ={+,),#} FOLLOW(T?)={+,),#} FOLLOW(F) ={*,+,),#} 在对文法G的每个非终结符A及其任意候选?都构造出FIRST(?)和FOLLOW(A)之后，现在可以用它们来构造G的分析表M[A，a]。 1. 对文法G的每个产生式A→?执行第2步和第3步； 2. 对每个终结符a ?FIRST(?)，把A→?加至M[A，a]中； 3. 若??FIRST(?)，则对任何b?FOLLOW(A)把A→?加至M[A，b]中。 4. 把所有无定义的M[A，a]标上“出错标志”。 FIRST(E) ={(,i} FIRST(E?)={+, ?} FIRST(T) ={(,i} FIRST(T?)={*, ?} FIRST(F) ={(,i} FOLLOW(E) ={),#} FOLLOW(E?)={),#} FOLLOW(T) ={+,),#} FOLLOW(T?)={+,),#} FOLLOW(F) ={*,+,),#} E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i 如果G是左递归或二义的，那么，M至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表M。 可以证明，一个文法G的预测分析表M不含多重定义入口，当且仅当该文法为LL(1)的。 作业 P81—1，2 P82—3(选作2个) 对应的递归下降子程序为: E→TE? | BC PROCEDURE E； BEGIN IF SYM ?FIRST(TE’) THEN T；E? ELSE IF SYM ?FIRST(BC) THEN B; C ELSE ERROR END； E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | I 对应的递归下降子程序为: PROCEDURE E； BEGIN T；E? END； PROCEDURE T； BEGIN F；T? END E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | I 对应的递归下降子程序为: PROCEDURE E?； IF SYM=‘+’ THEN BEGIN ADVANCE； T；E? END ELSE IF SYM‘#’ AND SYM’)’ THEN ERROR E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | I 对应的递归下降子程序为: PROCEDURE T?； IF SYM=‘*’ THEN BEGIN ADVANCE； F；T? END ELSE IF SYM‘#’ AND SYM’)’ AND SYM’+’ THEN ERROR E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i 对应的递归下降子程序为: