第五章

自頂向下語法分析方法學習目標:掌握：LL(1)文法判別，預測分析法，遞歸子程序結構方法了解：LL（1）文法了解：不確定自頂向下分析第1頁語法分析作用是識別由詞法分析給出單詞序列是否是給定文法正確句子分類:語法分析自頂向下分析自底向上分析確定不確定算法優先分析（第六章）LR分析（第七章）自頂向下基本思想: 從文法開始符出發企圖推導出與輸入單詞串完全相匹配句子.第2頁5.1 確定自頂向下分析思想5.2 LL(1)文法判別5.3 一些非LL(1)文法到LL(1)文法等價變換5.4 不確定自頂向下分析思想5.5 確定自頂向下分析方法第3頁5.1確定自頂向下分析思想1確定分析條件2開始符號集FIRST(α)定義3后跟符號集FOLLOW(A)定義4選擇集合SELECT(A→α)定義5LL(1)文法定義第4頁1確定分析條件 從文法開始符出發，如能依據當前輸入符號（單詞符號）唯一地確定選取哪個產生式進行推導，則分析是確定。第5頁例1設有文法G1[S]: S→pA|qB A→cAd|a B→dB|b 若輸入串W=pccadd。自頂向下推導過程為:SSApcAdcAda=>pA=>pcAd=>pccAdd=>pccaddG1[S]有以下特點：(1)每個產生式右部由終止符開頭;(2)同一非終止符不一樣產生式右部由不一樣終止符開頭。對于這種文法，在推導過程能夠依據當前輸入符號唯一確定選哪個產生式往下推導，即分析過程是確定。第6頁例2：設有文法G2[S]為:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>Ap該例說明，當(1)產生式右部以終止符或非終止符開頭（無空產生式）；(2)同一非終止符不一樣產生式右部由不一樣符號開頭。對于這種文法，在推導過程選取哪個產生式不直觀，關鍵是判斷產生式右部推出開始符號（集），分析過程可能是確定若輸入串W=ccap,自頂向下推導過程為：第7頁例3：設有文法G3[S]S→aA|dA→bAS|ε若輸入串W=abd，自頂向下推導過程為：AaSbSAεd=>abd

S=>abAS=>abS文法特點是:包含空產生式對于空產生式左部非終止符，關鍵是判斷該非終止符后跟符號（集），分析過程可能是確定。=>aA第8頁要進行確定自頂向下分析，文法要滿足一定限制——即文法是LL(1)文法。先研究三個定義

開始符號集FIRST 后跟符號集FOLLOW 選擇集合SELECT第9頁2開始符號集FIRST(α)定義定義:設G=(VN,VT,P,S)是上下文無關文法，

(VNVT)*

FIRST()={aVT|*a......} 若*ε

則要求ε∈FIRST()

直觀上說文法符號串

開始符號集是由推導出開頭終止符（包含ε）組成。第10頁例文法G2[S]:S→ApS→BqA→aA→cAB→bB→dBFIRST(Ap)={a,c}FIRST(Bq)={b,d}FIRST(a)={a}FIRST(cA)={c}FIRST(b)=FIRST(dB)=e98fn1z因為同一非終止符兩個產生式右部推導出來開始符號集不相交，所以可依據當前輸入符屬于哪個產生式右部開始符號集而決定選哪個產生式進行推導，能夠進行確定自頂向下分析第11頁3后跟符號集FOLLOW(A)定義定義 設G=(VT,VN,P,S)是上下文無關文法，A∈VN， FOLLOW(A)={a|S=>*…Aa…，a∈VT}， 若有S=>*…A，則要求#∈FOLLOW(A) （注：#輸入串#，‘#’做為輸入串結束符）

直觀上說,非終止符A后跟符號集是由句型中緊跟A后那些終止符（包含#）組成。第12頁例文法G3[S]: S→aA|d A→bAS|ε由S=>*S

得#∈FOLLOW(S)由S=>aA=>abAS=>abbASS=>abbASaA…=>abbASd

FOLLOW(S)={#,a,d}由S=>*aA得#∈FOLLOW(A)

由S=>*abAS=>*abAaA得a∈FOLLOW(A) …=>*abAd

得d∈FOLLOW(A)

FOLLOW(A)={#,a,d}第13頁說明：對于非終止符A兩個產生式A→bAS和A→ε，當輸入符號∈FIRST(bAS)=時，選A→bAS推導，當輸入符號∈FOLLOW(A)={#,a,d}時，選A→ε推導。因為FIRST(bAS)∩FOLLOW(A)=ф，所以可進行確定自頂向下分析。第14頁4選擇集合SELECT(A→α)定義定義 對給定上下文無關文法產生式A→α，A∈VN，α∈V*，若α≠>*ε,則SELECT(A→α)=FIRST(α)若α=>*ε,則SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)

第15頁解釋 當A面對應輸入符a，在自頂向下分析中應選擇這么產生式A→進行推導：First()中包含a； 另外若可能導出空串，A自動取得匹配，輸入符a有可能與A后一個符號匹配，所以當a應屬于Follow(A)時，選擇產生式A→也是能夠。

直觀上說某產生式A→α選擇集合是指碰到哪些輸入符號（包含#）時選取該產生式向下推導。第16頁例G3[S]:S→aAS→dA→bASA→εSELECT(S→aA)=FIRST(aA)={a}SELECT(S→d)=FIRST(d)=yem4qp6SELECT(A→bAS)=FIRST(bAS)=SELECT(A→ε)=FOLLOW(A)={#,a,d}若α≠>*ε,則SELECT(A→α)=FIRST(α)若α=>*ε,則SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)第17頁說明： 同一非終止符不一樣產生式A→α與A→β，若SELECT(A→α)∩SELECT(A→β)=Φ，則一定能夠進行確定自頂向下分析第18頁5LL(1)文法定義定義: 一個上下文無關文法是LL(1)文法充分必要條件是，對每個非終止符A兩個不一樣產生式A→α與A→β，滿足SELECT(A→α)∩SELECT(A→β)=Φ。

LL(1)文法含義是：第一個L表示從左到右掃描輸入串第二個L表示分析過程用最左推導1表明只需向前看一個符號便能夠決定選哪個產生式進行推導，類似地LL(k)文法需要向前看K個符號才能夠確定選取哪個產生式。第19頁例有文法G[S]為： S→aAS S→b A→bA A→εSELECT(S→aAS)={a}SELECT(S→b)=SELECT(A→bA)=SELECT(A→ε)=Follow(A)={a,b}因為SELECT(A→bA)∩SELECT(A→ε)=≠Φ，所以文法G[S]不是LL(1)文法，當A遇輸入符b時，不能確定選A→bA還是A→ε去推導。第20頁5.2LL(1)文法判別要判別一個上下文無關文法是否是LL(1)文法分為五步：1.

求能推出ε非終止符集2.

計算每個產生式右部αFIRST(α)集3.

計算每個非終止符AFOLLOW(A)集4.

計算每個產生式A→αSELECT(A→α)集5.

按LL(1)文法定義判別第21頁1.

求出能推出ε非終止符集算法: 用S表示能推出ε非終止符集第一步令S={Aj|Aj→ε

產生式集}對每個產生式p:Ap→X1....Xn，若X1....XnS，則

S:=S{Ap}重復第二步循環，直至S收斂（不再改變）為止。第22頁例G[S]： S→AB|bC A→b|ε B→aD|ε C→AD|b D→aS|c{A,B,S}第一次{A,B}初值{A,B,S}收斂第二次非終止符集S能推出ε非終止符集為{A,B,S}第23頁2.

計算每個產生式右部αFIRST(α)集首先對每一文法符號X(XVTVN)，求FIRST(X)算法:對每個aVT

：First(a)={a}對每個AVN

：若

A*ε

則

First(A):={ε} 不然

First(A):={}對每個產生式

A→X1…Xj…Xn

做： First(A)=First(A)SectionFirst(X1…Xj…Xn)第24頁其中SectionFirst(X1…Xj…Xn) =(First(X1)-{ε})(First(X2)-{ε})…(First(Xj)-{ε})First(Xj+1)

Xj+1是產生式右部中第一個不能推出ε符號若X1≠>*ε

則SectionFirst(X1…Xj…Xn)=First(X1)若X1…Xn全可推出ε 則SectionFirst(X1…Xn)=FIRST(X1)∪…∪FIRST(Xn)重復3直到每個符號FIRST集合都不再增大為止。第25頁例G[S]：S→AB|bC A→b|ε B→aD|ε C→AD|b D→aS|cbaacbac

εaεbεbaFirst集(3)baacbεaεbεbFirst集(2)ba

εεεFirst集(1)ABCDabSabεεεFirst集(0)已求出能推出ε非終止符集為{A,B,S}bbabacaac第26頁利用求出每個文法符號FIRST集求符號串FIRST集設α=X1X2…Xn當X1不能=>*ε

，則FIRST(α)=FIRST(X1)若對任何j(1≤j＜n）都有ε∈FIRST(Xj),

則FIRST(α) =(FIRST(X1)-{ε})∪…∪(FIRST(Xj)-{ε}) ∪FIRST(Xj+1)若對全部i(1≤i≤n)，都有ε∈FIRST(Xi)，

則

FIRST(α)=FIRST(X1)∪…∪FIRST(Xn)第27頁例G[S] S→AB|bC A→b|ε B→aD|ε C→AD|b D→aS|c已求出非終止符First集合以下:First(S)={a,b,ε}First(A)={b,ε}First(B)={a,ε}First(C)={a,b,c}First(D)={a,c}產生式右部符號串開始符集合為:S→AB FIRST(AB)=FIRST(A)∪FIRST(B)∪{ε}={a,b,ε}S→bC FIRST(bC)=A→ε FIRST(ε)={ε}A→b FIRST(b)=C→AD FIRST(AD)=(FIRST(A)-{ε})∪FIRST(D)={b,a,c}D→aS FIRST(aS)={a}第28頁3．計算每個非終止符AFOLLOW(A)集1.對全部AVN令Follow(A)={};對開始符S，令Follow(S)={#}因為S=>*S，顯然#∈FOLLOW(S)2.對每條產生式A→xBy，考查產生式右部每一非終止符B，x,y∈V*，假如y不能推出ε Follow(B)=Follow(B)First(y)不然

Follow(B)=Follow(B)(First(y)-{ε})Follow(A)3.重復2，直至對全部AVN，Follow(A)收斂為止。若a∈FOLLOW(A),則表明S=>*…Aa…，因為A→xBy，且y=>*ε,則有S=>*…Aa…=>…xBya=>…xBa…，即S=>*…xBa…,所以a∈FOLLOW(B)第29頁例G[S]：[1]S→AB[2]S→bC[3]A→b[4]A→ε[5]B→aD[6]B→ε[7]C→AD[8]C→b[9]D→aS[10]D→c已求出非終止符First集合以下:First(S)={a,b,ε} First(A)={b,ε}First(B)={a,ε} First(C)={a,b,c}First(D)={a,c}#D#C#Ba#A###a#c＃＃＃SFollow集(2)Follow集(1)Follow集(0)c第30頁4．計算每個產生式A→αSELECT(A→α)集按定義計算SELECT(A→α)：若α≠>*ε，則 SELECT(A→α)=FIRST(α)若α=>*ε，則 SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)第31頁例G[S]： S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c是否=>*

εFirst集Follow集S是{a,b,ε}{#}A是{b,ε}{a,c,#}B是{a,ε}{#}C否{a,b,c}{#}D否{a,c}{#}部分產生式select集合SELECT(S→AB)=(FIRST(AB)-{ε})∪FOLLOW(S)={b,a,#}SELECT(S→bC)=FIRST(bC)=SELECT(A→ε)=(FIRST(ε)-{ε}）∪FOLLOW(A)={a,c,#}SELECT(A→b)=FIRST(b)=SELECT(B→aD)=FIRST(aD)={a}SELECT(C→AD)=FIRST(AD)={b,a,c}第32頁5.

按LL(1)文法定義判別產生式select集以下:SELECT(S→AB)={b,a,#} SELECT(S→bC)==SELECT(A→ε)={a,c,#} SELECT(A→b)=SELECT(B→ε)={#} SELECT(B→aD)={a}SELECT(C→AD)={b,a,c} SELECT(C→b)=SELECT(D→aS)={a} SELECT(D→c)={c}因為 SELECT(S→AB)∩SELECT(S→bC)=≠ф SELECT(C→AD)∩SELECT(C→b)=≠ф所以文法G[S]不是LL(1)文法第33頁5.3一些非LL(1)文法到LL(1)文法等價變換非LL(1)文法含有左公共因子文法 若文法中含有形如：A→αβ|αr產生式，稱文法含有左公共因子。 顯然, SELECT(A→αβ)∩SELECT(A→αr)≠ф,文法不是LL(1)文法第34頁含有左遞歸文法 文法中只要含有以下形式產生式（含有a或含有b或二者皆有）則稱文法含有左遞歸：A→AβA→Bβ B→Aα 在a)中含有左遞歸產生式，稱為直接左遞歸； 在b)中即使沒有含左遞歸產生式， 但A=>Bβ=>Aαβ即A=>+A…,稱為間接左遞歸第35頁以直接左遞歸為例，若有以下產生式

A→A

|

A→其中和為任意語法符號串。不難證實有下面關系式：

Select(A→A))First(A)First() Select(A→

))First()故A→A和A→

Select集相交，不是LL(1)文法。第36頁對非LL(1)文法進行等價變換提取左公共因子消除左遞歸

注意：變換后文法不一定是LL(1)文法，文法不含左遞歸和左公共因子只是LL(1)文法必要條件。第37頁1提取左公共因子將產生式A→αβ|αr等價變換為: A→α(β|r)， 將括號內用一新引入非終止符A’表示,得A→αA’，A’→β|r普通形式：若A→αβ1|αβ2|…|αβn, 提取左公共因子后變為A→αA’， A’→β1|β2|…|βn

若在βi中仍含有左公共因子,可再次提取.第38頁例 文法G1： S→aSb|aS|ε

提左因子得:S→aS(b|ε)|ε

引進新非終止符得:

S→aSS’|ε S’→b|ε第39頁2.

消除左遞歸消除直接左遞歸文法G:S→Sa|b 可改寫成 S→bS’ S’→aS’|ε普通情形: 含直接左遞歸文法G： A→Aα1|Aα2|…|Aαm|β1|β2|…|βn 消除左遞歸后改寫成：

A→β1A’|β2A’|…|βnA’

A’→α1A’|α2A’|…|αmA’|ε

第40頁消除間接左遞歸將間接左遞歸變成直接左遞歸，再消除算法步驟：把文法全部非終止符按任一次序排列， 如：A1，A2，…，An從A1開始，按以下次序處理Ai。首先，消除左部為Ai產生式直接左遞歸然后，若左部為Ai產生式右部為非終止符Aj(j<i)開頭，即Ai→Aj…，則用左部為Aj全部產生式右部分別代替Ai→Aj…中Aj最終，得到左部為Ai產生式若有直接左遞歸，則消除之

去掉無用產生式。第41頁例文法G：(1)S→Qc|c (2)Q→Rb|b(3)R→Sa|a將非終止符排序：R，Q，S對R：產生式(3)不含直接左遞歸，所以保持不變

對Q：把(3)代入(2)得(2’)Q→Sab|ab|b，無直接左遞歸

對S：把(2’)代入(1)得(1’)S→Sabc|abc|bc|c，有直接左遞歸，消除直接左遞歸得

S→abcS’|bcS’|cS’ S’→abcS’|ε 處理結果為：R→Sa|a Q→Sab|ab|b S→abcS’|bcS’|cS’ S’→abcS’|ε因為Q，R是不可抵達非終止符，其產生式應刪除。最終得文法G’：S→abcS’|bcS’|cS’S’→abcS’|ε第42頁示例說明：當非終止符次序為R，Q，S，消除左遞歸最終止果為：

S→abcS’|bcS’|cS’S’→abcS’|ε若非終止符次序為S，Q，R，則消除左遞歸最終止果為：

S→Qc|cQ→Rb|bR→bcaR’|caR’|aR’R’→bcaR’|ε結論：當非終止符排序不一樣時，結果產生式形式不一樣，但它們是等價。第43頁5.4不確定自頂向下分析思想不確定自頂向下分析也稱帶回溯自頂向下分析定義： 不確定是指某個非終止符有多條產生式，而面臨當前輸入符無法唯一確定選取哪條產生式進行推導，只好逐一試探。當分析不成功時，則推翻分析退回到適當位置重新試探其余候選可能推導，直到把全部可能推導序列都試完仍不成功，才能確認輸入串不是該文法句子。第44頁例1 設有文法S→xAyA→ab|a，對輸入串w=xay，推導樹為SxAySxAybaSxAy回溯aSxAy因為A兩條產生式：A→ab和A→a右部First集交集不為空，從而引發回溯第45頁例2 文法G：S→aAS S→b A→bAS A→ε 輸入串w=ab，推導樹為:SaAS回溯S

aASSaASSbASaASεb因為A產生式A→ε右部能=>*ε，且Follow(A)∩First(bAS)=≠ф

，從而引發回溯第46頁例3 文法G：S→Sa S→b輸入串w=baa，推導樹為:SSabSbSSa回溯回溯SSaSaSSaSab因為文法含有左遞歸而引發回溯第47頁5.5確定自頂向下分析方法確定自頂向下分析方法有：遞歸子程序法(recursive-descentparser)預測分析法(predictiveparser)兩種方法都要求文法是LL(1)文法。第48頁5.5.1遞歸子程序法實現思想： 對文法中每個非終止符編寫一個遞歸過程，識別由該非終止符推出串。當非終止符有多條產生式時，按當前輸入符屬于哪條產生式SELECT集可唯一確定選擇哪個產生式進行匹配。當識別到終止符時，與當前輸入符號匹配，并讀取下一輸入符；當識別到非終止符時，則調用該非終止符對應過程。第49頁例算術表示式文法G

E→E+T│T T→T*F│F F→(E)│i1）消除左遞歸得G':E→TE' E'→+TE'│εT→FT' T'→*FT'│εF→(E)│i 2）求出G’選擇集合SELECT(E→TE')={(,i}SELECT(E'→+TE')={+}SELECT(E'→ε)={),#}SELECT(T→FT')={(,i}SELECT(T'→*FT')={*}SELECT(T'→ε)={+,),#}SELECT(F→(E))={(}SELECT(F→i)={i}G’是LL(1)文法1

判斷是否能夠應用遞歸子程序法第50頁表示式正規式E=T(+T)*轉換成正則文法E→TB，B→(+T)*，即B→(+T)*εB→(+T)B，B→ε，即B→(+T)B│ε

與E→E+T│T消除左遞歸所得E→TE‘ E’→+TE‘│ε一致表示式項＋－項＋－原產生式變換后產生式規則1A→xyA→xBB→y規則2A→x*yA→xAA→y規則3A→x|yA→xA→y第51頁2

結構文法G'遞歸下降分析器定義： 當一個文法滿足LL(1)條件時，就為它結構一個不帶回溯自頂向下分析程序，這個分析程序由一組遞歸過程組成，每個過程對應文法一個非終止符。這么一個分析程序稱為遞歸下降分析器。第52頁組成： 遞歸下降分析器由一個主程序MAIN和每個非終止符對應一個遞歸過程組成。 用到一些子過程：過程GETNEXT負責讀入下一個TOKEN字過程ERROR負責匯報語法錯誤 約定：變量TOKEN存放已讀入TOKEN字過程進入時變量TOKEN存放了一個待匹配TOKEN字退出過程時，變量TOKEN中仍存放著一個待匹配TOKEN字。第53頁非終止符對應分析子程序結構方法對于每個非終止符U，編寫一個對應子程序P(U);對于產生式U→x1|x2|…|xn，x1,...xn都≠ε關于U子程序P(U)按以下方法結構：

ifTOKENinfirst(x1)thenp(x1)elseifTOKENinfirst(x2)thenp(x2)else…….ifTOKENinfirst(xn)thenp(xn)elseERROR第54頁假如U還有空產生式U→ε,則算法中語句：

ifTOKENinfirst(xn)thenp(xn)elseERROR改寫為

ifTOKENinfirst(xn)thenp(xn)elseifTOKENnotinfollow(U)thenERROR對于符號串x=y1y2…yn；p(x)含義為：

beginp(y1);p(y2);…;p(yn)end 假如yi∈VN，則P(yi)就代表調用yi子程序；yi∈VT，則P(yi)為形以下述語句一段程序

ifTOKEN=yithenGETNEXT(TOKEN)elseERROR第55頁(1)programMAIN;/*主程序,匹配E→E#*/

beginGETNEXT(TOKEN);E(TOKEN);/*轉匹配E→TE'*/ifTOKEN≠'#'thenERRORend.結構文法G’： E→TE' E'→+TE'│εT→FT' T'→*FT'│ε F→(E)│i 遞歸下降分析器(2)procedureE(TOKEN); /*匹配E→TE'*/beginT(TOKEN); /*轉匹配T→FT'*/E’(TOKEN)/*轉匹配E'→+TE'│ε*/end;

第56頁(3)procedureE’(TOKEN);/*匹配E'→+TE'│ε*/beginifTOKEN=’+’then/*選擇產生式E'→+TE'*/beginGETNEXT(TOKEN);

/*匹配’+’,讀下一個TOKEN字*/

T(TOKEN);/*轉匹配T→FT'*/E’(TOKEN)/*轉匹配E'→+TE'│ε*/end else/*E→ε對應語句*/ ifTOKEN≠’)’andTOKEN≠’#’thenERROR

/*結構方法3，求follow(E’)=follow(E)={’)’,’#’}*/

end;第57頁(5)procedureT'(TOKEN);/*匹配T'→*FT'│ε*/beginifTOKEN='*'then/*選擇產生式T'→*FT'*/beginGETNEXT(TOKEN);/*匹配'*'，讀下一TOKEN字*/

F(TOKEN);/*轉匹配F→(E)│i*/T'(TOKEN)/*轉匹配T'→*FT'│ε*/end else/*T‘→ε對應語句*/ifTOKEN≠'+'andTOKEN≠')'andTOKEN≠'#'thenERRORend;/*follow(T’)=follow(T)=first(E’)+follow(E’)={’+’,’)’,’#’}*/

(4)procedureT(TOKEN);/*匹配T→FT'*/beginF(TOKEN);/*轉匹配F→(E)│i*/T’(TOKEN)/*轉匹配T'→*FT'│ε*/end;第58頁(6)procedureF(TOKEN);/*匹配F→(E)│i*/beginifTOKEN='('then/*選擇產生式F→(E)*/beginGETNEXT(TOKEN);/*匹配'('，讀下一TOKEN字*/

E(TOKEN);/*轉匹配E→TE'*/

ifTOKEN=')'thenGETNEXT(TOKEN)

/*匹配')',讀下一TOKEN字*/

elseERRORendelse /*選擇產生式F→i

*/ ifTOKEN=‘i’thenGETNEXT(TOKEN) elseERRORend;第59頁特點：優點：簡單直觀、易于結構缺點： 對文法要求高，必須滿足LL(1)文法； 遞歸調用多，速度慢，占用空間多實用性：許多高級語言，如Pascal、c等編譯系統經常采取此方法。第60頁5.5.2預測分析方法一個預測分析器由三個部分組成：預測分析程序：控制分析過程進行。分析棧：存放從文法開始符號出發自頂向下推導過程中等候匹配文法符號。開始時放入‘#’和文法開始符，結束時棧應是空。預測分析表：是一張二維表，元素M[A,a]內容是當非終止符A面臨輸入符號a（終止符或句子括號＃）