编译原理：第五章 自顶向下语法分析方法

1、2022/8/151第五章 自顶向下语法分析方法5.1 自顶向下分析的一般过程和问题5.2 递归下降分析法5.3 LL(1)文法及其分析程序 FIRST和FOLLOW集定义和计算 LL(1) 文法定义 LL(1)分析程序实现非LL(1)文法的改造2022/8/152句型的分析分析算法分类：自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的最左推导。自下而上分析法：从输入符号串开始，逐步进行归约（最右推导的逆过程），直至归约到文法的开始符号。2022/8/1535.1自上而下语法分析的一般过程从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的最左推导。文法

2、G：S cAd A ab |a 识别输入串w=cad试探：推导过程：S cAd cabdSSScAdcAd a b 回溯:试探推导过程：S cAd cad S c A d a2022/8/154自上而下语法分析的问题GS: SSa Sb L=ban | n1W=baaa S b S S a S a 2022/8/155左递归 关于非终结符P的规则直接左递归 若 P P | 、 V*且不以P开头间接左递归 若 P P SAa ASb Ab2022/8/156消除左递归消除直接左递归 形如：P P | 非， 不以P打头 改写为：P P P P| 2022/8/157消除左递归例:E E+T|T T

3、 T*F|F F (E)| i G E: (1) E TE (2) E +TE| (3) T FT (4) T *FT | (5) F (E)|i2022/8/158消除左递归一般情况：A A1|A2|Am|1|2| |n消除左递归后：A 1A|2 A | |n AA1 A|2 A|m A|2022/8/159消除间接左递归要求文法:1.无回路(A(A (A) 2.无空产生式（1） 以某种顺序将文法非终结符排列A1 ,A2 An（2） for i:=1 to n dobegin for j:=1 to i-1 do 用Ai-1| 2r| k r替代形如Ai- Ajr的规则,其中Aj- 1| 2

4、| k是关于Aj的全部产生式;消除Ai规则的直接左递归; end;（3）化简由2得到的文法2022/8/1510消除间接左递归例：文法 S Ac|c A Bb|b B Sa|a 2022/8/1511回溯问题例：S iEtS|iEtSeS|a Eb判断句子ibtaea提取左公因子：A 1|2变为： A A A 1 |2若A 1|2 |n|r变为： A A|r A 1 |2|n2022/8/1512例：S iEtS|iEtSeS|a Eb提取左公因子： S iEtSS|a S eS| E b2022/8/15135.2递归下降分析法递归下降分析器：在消除了左递归和提取左公因子后，可以构造一个不带

5、回溯的自上而下的分析程序。这个程序由一组递归过程组成，每个过程对应文法的一个非终结符。例：G E: (1) E TE (2) E +TE| (3) T FT (4) T *FT | (5) F (E)|i2022/8/1514Procedure E; Begin T;E End;Procedure T; Begin F;T End;Procedure F; IF sym=i then advance else IF sym=( then Begin advance; E IF sym=) then advance else ERROR End; else ERROR; Procedure E;

6、 IF sym=+ then Begin advance; T;E End;Procedure T; IF sym=* then Begin advance; F;T End;2022/8/15155.3非递归的预测分析方法（LL（1）一、总控程序 Input #总控程序预测分析表stack#S2022/8/1516分析算法BEGIN 首先把#然后把文法开始符号推入栈；把第一个输入符号读进a; FLAG：=TRUE；WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在中； IF X Vt THEN IF X=a THEN 把下一个输入符号读进a ELSE ERROR ELSE IF

7、 X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF X,a=X-X1X2.XK THEN 把XK，X K-1,.,X1一一推进栈 ELSEERROR END OF WHILE;STOP/*分析成功，过程完毕*END2022/8/1517 例：G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F i 对输入i+i*i的分析2022/8/1518FIRST集和FOLLOW集 设G=(VT,VN,S,P)是上下文无关文法FIRST（）=a| a,aVT, ,

8、V*FOLLOW（A）=aS Aa,a VT二、预测分析表M的构造 -LL (1)文法及其分析程序2022/8/1519计算FIRST集1.若XV,则FIRST(X)=X2.若XVN,且有产生式Xa，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中.3.若XY是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X Y1Y2YK 是一个产生式,Y1,Y2,Yi-1（ 1i k）都是非终结符,而且,当 2022/8/1520 Y1.Y(i-1) ,则把FIRST(Y1 j i-1)中所有非元素， FIRST(Yi)都加到FIRST(X

9、)中;特别是,若所有的FIRST(Yj , j=1,2,K)均含有,则把加到FRIST(X)中. 例： G E: (1) E TE (2) E +TE| (3) T FT (4) T *FT | (5) F (E)|i2022/8/1521计算FOLLOW集1.对于文法的开始符号S,置#于FOLLOW(S) 中;2.若B是一个产生式,则把 FIRST()加至FOLLOW(B)中;3.若B是一个产生式,或B是 一个产生式而 (即FIRST()）， 则把FOLLOW（A）加至FOLLOW（B）中例：GE（见上页）2022/8/1522予测分析表构造算法1.对文法G的每个产生式执行第二步 和第三步；2.对每个终结符aFIRST()，把加 至A,a中，3.若FIRST()，则对任何bFOLLOW(A) 把加至A,b中，4.把所有无定义的A,a标上“出错标志”。上例的预测分析表2022/8/1523三、LL（1）文法：一个文法G，若它的分析表M不含多重定义入口，则称为LL（1）文法。例：文法S iEtS|iEtSeS|a Eb不是LL（1）文法。一个LL（1）文法是无二义的。2022/8/1524 一个文法G是LL（1）的，当且仅当对于G的每一个非终结符的任何两个不同产生式，下面的条件成立：FI