1、第5章 自上而下語法分析,編譯原理 陳炬樺 ,51 消除左遞歸方法,為了避免無限循環(huán)，自上而下分析法的文法不應(yīng)含有左遞歸。有則消除。 文法的左遞歸性 直接左遞歸：UUx | y 間接左遞歸：U Ux 例：G22A： A B B X | BA X Xa | Xb | a | b,用擴(kuò)展的BNF表示法消除左遞歸, 零次或多次， mn次 零次或一次，可選項。 ( ) 描述提取公因子。 例：G標(biāo)識符： | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 a|b|c|e|f|g|h|i|j|k|m|n|o|p|q|r|s|t|u|v|w|x|y|z 顯然標(biāo)識符產(chǎn)生式有左遞

2、歸，可改寫為 | ,直接改寫法,UUx | y = UyU, U xU | UUx1 | Ux2 | Uxm | y1 | y2 yn = UU(x1 | x2 | xm) | (y1 | y2 yn) = U (y1 | y2 yn)U U (x1 | x2 | xm)U | ,直接改寫法舉例,例：G22A： A B B X | BA X Xa | Xb | a | b 改寫為： G22A： A B B XB B AB| X aX | bX X aX | bX | ,消除左遞歸算法, 將VN符號整理成序 Uk，k=1,n for i:=1 to n do begin j:=i+1 to n

3、do 替換 UiUj中的Uj 消除Ui產(chǎn)生式中的直接左遞歸 end 化簡，刪除多余產(chǎn)生式,消除左遞歸算法舉例,例5.4 設(shè)文法 ABcd B Ce | f C Ab | c 變換： B Ce | f = B Abe | ce | f ABcd = A Abecd | cecd | fcd 消除左遞歸 A cecdA | fcdA Abecd A| B Abe | ce | f C Ab | c 刪除多余產(chǎn)生式,LL(k)文法,最左推導(dǎo) 從左到右掃描輸入串 向前查看K（1）個符號，選擇產(chǎn)生式 本課程只討論LL(1),LL(1)文法的判斷條件,(VNVT)* FIRST()=a | a，aVT，(

4、VNVT)* UVN FOLLOW(U)= b | S xUby,bVT,x,y (VNVT)* 定義5.1 文法G是LL(1)： U x1 | x2 | xn 如果 FIRST(xi)FIRST(xj)= 當(dāng)FIRST(xi)時，F(xiàn)IRST(xi)FOLLOW(U)=,集合FIRST、FOLLOW的構(gòu)造,FIRST()的構(gòu)造 VT，F(xiàn)IRST()= VN，a，a FIRST()； ，F(xiàn)IRST() VN，XY， FIRST(X)- FIRST()， 若X ，則FIRST(Y)- FIRST(),集合FIRST、FOLLOW的構(gòu)造,FOLLOW（U）的構(gòu)造 U是開始符號，則# FOLLOW(U

5、) AxUy， 則FIRST(y)- FOLLOW（U） AxUy，y , (包括AxU) 則FOLLOW(A) FOLLOW(U),構(gòu)造FIRST、FOLLOW舉例,例G27S SA ABA AiBA| BCB B+CB| C)A*|(,構(gòu)造分析表的算法, MU,a=U，aFIRST()； MU,b=U，bFOLLOW（U）； MU,b=Error ，空白處；,例G27S SA ABA AiBA| BCB B+CB| C)A*|(,符號串(i(分析過程,5.4 遞歸下降分析程序及其設(shè)計,給每個非終結(jié)符設(shè)計一個相應(yīng)的子程序。 int fS()return fA(); int fA()if fB

6、() return fA(); else return Error; int fA() read(ch); if (ch= =i) if fB() return fA(); else return Error; else return OK; int fC()read(ch); if(ch= =) if fA() read(ch); return (ch= =*); else return Error; else return (ch= =() ,例G27S SA ABA AiBA| BCB B+CB| C)A*|(,例：已知文法GS： SeT | RT TDR | RdR | Da | bd 計算每個非終結(jié)符的FIRST、FOLLOW集。 構(gòu)造GS的LL(1)分析表。,例： 已知文法GS： SeT | RT TDR | RdR | Da | bd LL(1)分析表,已知文法GA： AAB | B BBC | C CD | D D（A）| i 消除左遞歸，計算每個非終結(jié)符的FIRST、FOLLOW集。 構(gòu)造GS的LL(1)分析表。,解： ABA ABA | BCB BC