第5章自頂向下語法分析方法完教材課程

第5章自頂向下語法分析方法2025/1/11第5章自頂向下語法分析方法Page2第五章

自頂向下語法分析方法學習目標:掌握：LL(1)文法的判別，預測分析法，遞歸子程序的構造方法理解：LL(1)文法了解：不確定的自頂向下分析2025/1/11Page3第5章自頂向下語法分析方法語法分析的作用是識別由詞法分析給出的單詞序列是否是給定文法的正確句子.分類:語法分析自頂向下分析（第五章）自底向上分析確定的不確定的算符優(yōu)先分析（第六章）LR分析（第七章）自頂向下的基本思想:

從文法的開始符出發(fā)企圖推導出與輸入的單詞串完全相匹配的句子。2025/1/11第5章自頂向下語法分析方法Page45.1 確定的自頂向下分析思想5.2 LL(1)文法的判別5.3 某些非LL(1)文法到LL(1)文法的等價變換5.4 不確定的自頂向下分析思想5.5 確定的自頂向下分析方法第五章自頂向下語法分析方法2025/1/11Page6第5章自頂向下語法分析方法1確定分析的條件

從文法的開始符出發(fā)，如能根據當前的輸入符號（單詞符號）唯一地確定選用哪個產生式進行推導，則分析是確定的。2025/1/11Page7第5章自頂向下語法分析方法例1設有文法G1[S]: S→pA|qB A→cAd|a B→dB|b

若輸入串W=pccadd。自頂向下的推導過程為:SSApcAdcAda=>pA=>pcAd=>pccAdd=>pccaddG1[S]有如下特點：

(1)每個產生式的右部由終結符開頭;(2)同一非終結符的不同產生式的右部由不同的終結符開頭。對于這種文法，在推導過程可以根據當前的輸入符號唯一確定選哪個產生式往下推導，即分析過程是確定的。2025/1/11Page8第5章自頂向下語法分析方法例2：設有文法G2[S]為:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>Ap該例說明，當(1)產生式右部以終結符或非終結符開頭（無空產生式）；(2)同一非終結符的不同產生式的右部由不同的符號開頭。對于這種文法，在推導過程選用哪個產生式不直觀，關鍵是判斷產生式右部推出的開始符號（集）——First集，分析過程可能是確定的。若輸入串W=ccap,自頂向下的推導過程為：2025/1/11Page9第5章自頂向下語法分析方法例3：設有文法G3[S]S→aA|dA→bAS|ε若輸入串W=abd，自頂向下的推導過程為：AaSbSAεd=>abd

S=>abAS=>abS文法的特點是：包含空產生式對于空產生式左部的非終結符，關鍵是判斷該非終結符的后跟符號（集）——Follow集，分析過程可能是確定的。=>aA2025/1/11Page10第5章自頂向下語法分析方法1確定分析的條件要進行確定的自頂向下的分析，文法要滿足一定的限制——即文法是LL(1)文法。先研究三個定義開始符號集FIRST集后跟符號集FOLLOW集選擇集合SELECT集2025/1/11Page11第5章自頂向下語法分析方法2

開始符號集FIRST(α)的定義定義:

設G=(VN,VT,P,S)是上下文無關文法，

(VN

VT)*

FIRST(

)={a

VT|

*a}

若

*ε

則規(guī)定ε∈FIRST(

)

直觀上說，文法符號串

的開始符號集是由

推導出的開頭的終結符（包括ε）組成。2025/1/11Page12第5章自頂向下語法分析方法例文法G2[S]:S→ApS→BqA→aA→cAB→bB→dBFIRST(Ap)=FIRST(Bq)=FIRST(a)=FIRST(cA)=FIRST(b)=FIRST(dB)=由于同一非終結符的兩個產生式的右部推導出來的開始符號集不相交，因此可根據當前輸入符屬于哪個產生式右部的開始符號集而決定選哪個產生式進行推導，可以進行確定的自頂向下分析{a,c}{b,d}{a}{c}qbsolntFirst:開始符號集2025/1/11Page13第5章自頂向下語法分析方法例2：設有文法G2[S]為:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>ApS→ApFIRST(Ap)={a,c}S→BqFIRST(Bq)={b,d}A→aFIRST(a)={a}A→cAFIRST(cA)={c}B→bFIRST(b)=B→dBFIRST(dB)=9z9p4am若輸入串W=ccap,自頂向下的推導過程為：2025/1/11Page14第5章自頂向下語法分析方法3

后跟符號集FOLLOW(A)的定義定義： 設G=(VT,VN,P,S)是上下文無關文法，A∈VN

，

FOLLOW(A)={a|S=>*…Aa…，a∈VT}， 若有S=>*…A，則規(guī)定#∈FOLLOW(A)

（注：#輸入串#，‘#’做為輸入串的結束符） 直觀上說，非終結符A的后跟符號集是由句型中緊跟A后的那些終結符（包括#）組成。2025/1/11Page15第5章自頂向下語法分析方法例文法G3[S]: S→aA|dA→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}2025/1/11Page16第5章自頂向下語法分析方法3

后跟符號集FOLLOW(A)的定義說明：對于非終結符A的兩個產生式A→bAS和A→ε：當輸入符號∈FIRST(bAS)=時，選A→bAS推導，當輸入符號∈FOLLOW(A)={#,a,d}時，選A→ε推導。由于FIRST(bAS)∩FOLLOW(A)=ф，所以可進行確定的自頂向下分析。2025/1/11Page17第5章自頂向下語法分析方法例3：設有文法G3[S]S→aA|dA→bAS|ε若輸入串W=abd，自頂向下的推導過程為：AaSbSAεd=>abd

S=>abAS=>abS文法的特點是:包含空產生式對于空產生式左部的非終結符，關鍵是判斷該非終結符的后跟符號（集），分析過程可能是確定的。=>aAFIRST(bAS)=FOLLOW(A)={#,a,d}2025/1/11Page18第5章自頂向下語法分析方法4

選擇集合SELECT(A→α)的定義定義 對給定的上下文無關文法的產生式A→α，A∈VN，α∈V*，若α≠>*ε,則

SELECT(A→α)=FIRST(α)若α=>*ε,則

SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11Page19第5章自頂向下語法分析方法4

選擇集合SELECT(A→α)的定義解釋 當A面對應輸入符a，若First(α)中包含a，在自頂向下的分析中應選擇產生式A→α進行推導； 此外若α可能導出空串，A自動獲得匹配，輸入符a有可能與A后的一個符號匹配，所以當a屬于Follow(A)時，選擇產生式A→α也是可以的。

直觀上說某產生式A→α的SELECT集是指遇到哪些輸入符號（包括#）時選用該產生式向下推導。SELECT(A→α)={a,b,c}2025/1/11Page20第5章自頂向下語法分析方法4

選擇集合SELECT(A→α)的定義即：若α≠>*ε,則是否選擇A→α這條產生式進行推導，主要是看當時輸入字符是否屬于FIRST(α)，若是，則選它。若α=>*ε,則是否選擇A→α這條產生式進行推導，除了看當時輸入字符是否屬于FIRST(α)，還可以看當時輸入字符是否屬于FOLLOW(A)，若屬于其中一個集合，則選它。若α≠>*ε,則SELECT(A→α)=FIRST(α)若α=>*ε,則SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11Page21第5章自頂向下語法分析方法例G3[S]:S→aAS→dA→bASA→εSELECT(S→aA)=SELECT(S→d)=SELECT(A→bAS)=SELECT(A→ε)=若α≠>*ε,則SELECT(A→α)=FIRST(α)若α=>*ε,則SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)FIRST(aA)=FIRST(d)=FIRST(bAS)=FOLLOW(A)={#,a,b}dqwhmjv{a}2025/1/11Page22第5章自頂向下語法分析方法4選擇集合SELECT(A→α)的定義說明： 同一非終結符的不同產生式A→α與A→β，若SELECT(A→α)∩SELECT(A→β)=Φ，則一定可以進行確定的自頂向下分析。SELECT(A→α)={a,b}SELECT(A→β)={c,d}SELECT(A→α)={a,b}SELECT(A→β)={a,d}可確定不可確定2025/1/11Page23第5章自頂向下語法分析方法5LL(1)文法的定義定義:

一個上下文無關文法是LL(1)文法的充分必要條件是，對每個非終結符A的兩個不同產生式A→α與A→β，滿足SELECT(A→α)∩SELECT(A→β)=Φ（無交集）。LL(1)文法的含義是：第一個L表示從左到右掃描輸入串第二個L表示分析過程用最左推導1表明只需向前看一個符號便可以決定選哪個產生式進行推導，類似地LL(k)文法需要向前看K個符號才可以確定選用哪個產生式。2025/1/11Page24第5章自頂向下語法分析方法例有文法G[S]為：

S→aAS S→b A→bA A→εSELECT(S→aAS)={a}由于SELECT(A→bA)∩SELECT(A→ε)=≠Φ，所以文法G[S]不是LL(1)文法，當A遇輸入符b時，不能確定選A→bA還是A→ε去推導。SELECT(S→b)=SELECT(A→bA)=SELECT(A→ε)=Follow(A)={a,b}2025/1/11第5章自頂向下語法分析方法Page25§5.2LL(1)文法的判別要判別一個上下文無關文法是否是LL(1)文法分為五步：

1.

求出能推出ε的非終結符集

2.

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

3.

計算每個非終結符A的FOLLOW(A)集

4.

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

5.

按LL(1)文法的定義判別2025/1/11Page26第5章自頂向下語法分析方法1.

求出能推出ε的非終結符集步驟：(1)第1次掃描——掃描文法中的產生式對能直接推出ε的產生式左部的終結符標“是”。刪除所有右部含有終結符的產生式。若以某一非終結符為左部的所有產生式都被刪除，則該非終結符不能推出ε，將其標為“否”。2025/1/11Page27第5章自頂向下語法分析方法1.

求出能推出ε的非終結符集例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|cS→ABS→bCA→bA→εB→aDB→εC→ADC→bD→aSD→c非終結符SABCD第1次掃描第2次掃描是是否2025/1/11Page28第5章自頂向下語法分析方法1.

求出能推出ε的非終結符集(2)第2次掃描——掃描產生式右部的符號對每個產生式p:A→X1Xn，如果X1,…,Xn都被標為“是”(即X1,…,Xn都能推出ε)，則A也能推出ε，將其標為“是”。如果A→Y1Yn中，Y1Yn中任一個已被標為“否”，則刪掉該產生式，若這么做使得A的所有產生式都被刪去，則A不能推出ε，將其標為“否”。2025/1/11Page29第5章自頂向下語法分析方法1.

求出能推出ε的非終結符集例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|cS→ABS→bCA→bA→εB→aDB→εC→ADC→bD→aSD→c非終結符SABCD第1次掃描第2次掃描是是否是否能推出ε的非終結符集為{A,B,S}2025/1/11Page30第5章自頂向下語法分析方法2.

計算每個產生式右部α的FIRST(α)集首先對每一文法符號X

(X

VT

VN)，求FIRST(X)的算法:對每個a

VT

：FIRST(a)={a}對每個A

VN

：若

A

*ε

，則ε

FIRST(A)對每個A

VN

：若A→a···,a

VT

，則a

FIRST(A)2025/1/11Page31第5章自頂向下語法分析方法2.

計算每個產生式右部α的FIRST(α)集若X,Y1,Y2,…,Yn都

VN,有產生式X→Y1Y2…Yn.當Y1,Y2,…,Yn-1都

*ε時，F(xiàn)IRST(Y1)-{ε},FIRST(Y2)-{ε},…,FIRST(Yn-1)-{ε},FIRST(Yn)都包含在FIRST(X)中。當4中所有Yi

*ε，則FIRST(X)=FIRST(Y1)

FIRST(Y2)…FIRST(Yn){ε}2025/1/11Page32第5章自頂向下語法分析方法例G[S]： S→AB S→

bC A→b A→

ε B→aD B→

ε C→AD C→

b D→aS D→

cbaacbacεaεbεbaFirst集(3)baacbεaεb

εbFirst集(2)ba

εεεFirst集(1)ABCDabSabFirst集(0)已求出能推出ε的非終結符集為{A,B,S}babacaacεεεb2025/1/11Page33第5章自頂向下語法分析方法利用求出每個文法符號的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)∪{ε}2025/1/11Page34第5章自頂向下語法分析方法例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→ABFIRST(AB)=

S→bCFIRST(bC)=

A→εFIRST(ε)=

A→b FIRST(b)=

C→ADFIRST(AD)=

D→aSFIRST(aS)=

FIRST(A)∪FIRST(B)∪{ε}={a,b,ε}(FIRST(A)-{ε})∪FIRST(D)={b,a,c}{a}{ε}2025/1/11Page35第5章自頂向下語法分析方法3．計算每個非終結符A的FOLLOW(A)集1.對所有A

VN令Follow(A)={};對開始符S，令Follow(S)={#}因為S=>*S，顯然#∈FOLLOW(S)2.

對每條產生式A→xBy，考察產生式右部的每一非終結符B，x,y∈V*，如果y不能推出ε

Follow(B)=Follow(B)

First(y),否則,若y

*ε，

Follow(B)=Follow(B)

(First(y)-{ε})

Follow(A)3.

重復2，直至對所有A

VN，F(xiàn)ollow(A)收斂為止。若a∈FOLLOW(A),則表明S=>*…Aa…，由于A→xBy，且y=>*ε,則有

S=>*…Aa…=>…xBya=>…xBa…，即S=>*…xBa…,所以a∈FOLLOW(B)2025/1/11Page36第5章自頂向下語法分析方法例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)c2025/1/11Page37第5章自頂向下語法分析方法4．計算每個產生式A→α的SELECT(A→α)集按定義計算SELECT(A→α)：若α≠>*ε，則

SELECT(A→α)=FIRST(α)若α=>*ε，則

SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11Page38第5章自頂向下語法分析方法例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)=SELECT(S→bC)=SELECT(A→ε)=SELECT(A→b)=SELECT(B→aD)=SELECT(C→AD)=(FIRST(AB)-{ε})∪FOLLOW(S)={b,a,#}FIRST(bC)=FIRST(b)=FIRST(aD)={a}FIRST(AD)={b,a,c}(FIRST(ε)-{ε})∪FOLLOW(A)={a,c,#}2025/1/11Page39第5章自頂向下語法分析方法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)文法一個上下文無關文法是LL(1)文法的充分必要條件是，對每個非終結符A的兩個不同產生式A→α與A→β，滿足SELECT(A→α)∩SELECT(A→β)=Φ2025/1/11第5章自頂向下語法分析方法Page40非LL(1)文法含有左公共因子的文法

若文法中含有形如：A→αβ|αr的產生式，稱文法含有左公共因子。 顯然, SELECT(A→αβ)∩SELECT(A→αr)≠ф,文法不是LL(1)文法5.3某些非LL(1)文法到

LL(1)文法的等價變換2025/1/11第5章自頂向下語法分析方法Page41含有左遞歸的文法

文法中只要含有下列形式的產生式（含有①或含有②或二者皆有），則稱文法含有左遞歸:A→AβA→Bβ B→Aα

在①中含有左遞歸的產生式，稱為直接左遞歸；

在②中雖然沒有含左遞歸的產生式，

但A=>Bβ=>Aαβ即A=>+

A…,稱為間接左遞歸.5.3某些非LL(1)文法到

LL(1)文法的等價變換2025/1/11第5章自頂向下語法分析方法Page42以直接左遞歸為例，若有如下產生式

A→A

|

A→其中和

為任意語法符號串。不難證明有下面關系式：

Select(A→A

))

First(A

)

First(

) Select(A→

))

First(

)故A→A

和A→的Select集相交，不是LL(1)文法5.3某些非LL(1)文法到

LL(1)文法的等價變換A

A

A

A

…不知何時結束不確定若α≠>*ε,則SELECT(A→α)=FIRST(α)若α=>*ε,則SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11第5章自頂向下語法分析方法Page43對非LL(1)文法進行等價變換提取左公共因子消除左遞歸 注意：變換后的文法不一定是LL(1)文法，文法不含左遞歸和左公共因子只是LL(1)文法的必要條件。5.3某些非LL(1)文法到

LL(1)文法的等價變換2025/1/11Page44第5章自頂向下語法分析方法將產生式A→αβ|αr等價變換為: A→α(β|r)， 將括號內用一新引入的非終結符A’表示,得 A→αA’，A’→β|r一般形式：若A→αβ1|αβ2|…|αβn,

提取左公共因子后變?yōu)? A→α(β1|β2|…|βn)，引進新的非終結符A’，得：

A→αA’，A’→β1|β2|…|βn

若在βi中仍含有左公共因子,可再次提取.1、提取左公因子2025/1/11Page45第5章自頂向下語法分析方法例文法G1：

S→aSb|aS|ε

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

引進新的非終結符S’得: S→aSS’|ε S’→b|ε1、提取左公因子2025/1/11Page46第5章自頂向下語法分析方法1)消除直接左遞歸文法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’|ε

2、消除左遞歸不難驗證，改寫前和改寫后的文法都產生語言{ban|n≥0}

2025/1/11Page47第5章自頂向下語法分析方法2)消除間接左遞歸將間接左遞歸變成直接左遞歸，再加以消除。算法步驟：把文法的所有非終結符按任一順序排列，

如：A1，A2，…，An從A1開始，按以下順序處理Ai。首先，消除左部為Ai的產生式的直接左遞歸；然后，若左部為Ai的產生式的右部為非終結符Aj(j<i)開頭，即Ai→Aj…，則用左部為Aj的所有產生式的右部分別代替Ai→Aj…

中的Aj；最后，得到的左部為Ai的產生式若有直接左遞歸，則消除之。去掉無用產生式。2025/1/11Page48第5章自頂向下語法分析方法例文法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’|ε2025/1/11Page49第5章自頂向下語法分析方法示例說明：當非終結符順序為R，Q，S，消除左遞歸的最終結果為：

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

S→Qc|c Q→Rb|bR→bcaR’|caR’|aR’R’→bcaR’|ε結論：當非終結符的排序不同時，結果的產生式形式不同，但它們是等價的。2025/1/11第5章自頂向下語法分析方法Page50不確定的自頂向下分析也稱帶回溯的自頂向下分析定義：

不確定是指某個非終結符有多條產生式，而面臨當前輸入符無法唯一確定選用哪條產生式進行推導，只好逐個試探。當分析不成功時，則推翻分析退回到適當位置重新試探其余候選可能的推導，直到把所有可能的推導序列都試完仍不成功，才能確認輸入串不是該文法的句子。5.4不確定的自頂向下分析思想2025/1/11Page51第5章自頂向下語法分析方法例1

設有文法

S→xAyA→ab|a，對輸入串w=xay，推導樹為SxAySxAybaSxAy回溯aSxAy由于A的兩條產生式：A→ab和A→a右部First集交集不為空，從而引起回溯2025/1/11Page52第5章自頂向下語法分析方法例2

文法G：S→aAS

S→b A→bAS A→ε

輸入串w=ab，推導樹為:SaAS回溯SaASSaASSbASaASεb由于A的產生式A→ε右部能=>*ε，且Follow(A)∩First(bAS)=≠ф

，從而引起回溯2025/1/11Page53第5章自頂向下語法分析方法例3

文法G：S→Sa S→b

輸入串w=baa，推導樹為:SSabSbSSa回溯回溯SSaSaSSaSab由于文法含有左遞歸而引起回溯2025/1/11第5章自頂向下語法分析方法Page545.5確定的自頂向下分析方法確定的自頂向下分析方法有：遞歸子程序法(recursive-descentparser)預測分析法(predictiveparser)兩種方法都要求文法是LL(1)文法。2025/1/11第5章自頂向下語法分析方法Page55實現(xiàn)思想： 對應文法中每個非終結符編寫一個遞歸過程，識別由該非終結符推出的串。當非終結符有多條產生式時，按當前輸入符屬于哪條產生式的SELECT集可唯一確定選擇哪個產生式進行匹配。當識別到終結符時，與當前輸入符號匹配，并讀取下一輸入符；當識別到非終結符時，則調用該非終結符相應的過程。5.5.1遞歸子程序法2025/1/11第5章自頂向下語法分析方法Page565.5.1遞歸子程序法由于遞歸子程序法對每個過程可能存在直接或間接遞歸調用，所以對某個過程在退出之前可能又被調用，因此有些信息需要保留，通常在入口時需保留某些信息，出口時需恢復——先進后出棧。優(yōu)點：簡單直觀、易于構造缺點：對文法要求高，必須是LL(1)文法遞歸調用多，速度慢，占用空間多2025/1/11第5章自頂向下語法分析方法Page575.5.2預測分析方法一個預測分析器由三個部分組成：預測分析程序：控制分析過程的進行。分析棧：存放從文法開始符號出發(fā)的自頂向下推導過程中等待匹配的文法符號。開始時放入‘#’和文法開始符，結束時棧應是空的。預測分析表：是一張二維表，元素M[A,a]的內容是當非終結符A面臨輸入符號a(終結符或句子括號＃)時應選取的產生式，當無產生式時，元素內容為轉向出錯處理。2025/1/11Page58第5章自頂向下語法分析方法構造預測分析表步驟：

(1)把文法轉變?yōu)長L(1)文法

(2)求出每條產生式的SELECT集

(3)依照SELECT集把產生式填入分析表對每個終結符或‘?！胊表示若a

SELECT(A→

)，則把A→

放入M[A,a]中，把所有無定義的M[A,a]標上出錯標記。2025/1/11Page59第5章自頂向下語法分析方法例算術表達式文法G

E→E+T│T T→T*F│F F→(E)│i（1）消除G的左遞歸得到文法

G‘ E→TE' E'→+TE'│ε T→FT' T'→*FT'│ε F→(E)│i 2025/1/11Page60第5章自頂向下語法分析方法（2）求出每個產生式的select集,G’是LL(1)文法

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}F→(E)F→iFT'→εT'→εT'→*FT'T'→εT'T→FT’T→FT’TE'→εE'→εE'→+TE’E'E#）（*+iE→TE’E→TE’（3）依照選擇集合把產生式填入分析表注：表中空白處為出錯2025/1/11Page61第5章自頂向下語法分析方法上托棧頂符放入XNYYNNNNYYY把’#’和文法開始符壓入分析棧；當前輸入符送a把產生式右部反序進棧X∈VT?X=’#’?X=a?X=a?讀下一輸入符到aM[X,a]有產生式？出錯結束出錯預測分析程序工作過程預測分析程序2025/1/11Page62第5章自頂向下語法分析方法輸入串i+i*i#的分析過程i+*（）#EE→TE’E→TE’E'E'→+TE’E'→εE'→εTT→FT’T→FT’T'T'→εT'→*FT'T'→εT'→εFF→iF→(E)+匹配+i*i##E’T+7E’→+TE’+i*i##E’6T’→ε+i*i##E’T’5i匹配i+i*i##E’T’i4F→ii+i*i##E’T’F3T→FT’i+i*i##E’T2E→TE’i+i*i##E1所用產生式剩余輸入串分析棧步驟反序壓棧!2025/1/11Page63第5章自頂向下語法分析方法T→FT’ i*i##E’T8F→i i##E’T’F13i匹配 i##E’T’i14T’→ε ##E’T’15E’→ε ##E’16接受 ##17*匹配 *i##E’T’F*12T’→*FT’ *i##E’T’11i匹配 i*i##E’T’i10F→i i*i##E’T’F9i+*（）#EE→TE’E→TE’E'E'→+TE’E'→εE'→εTT→FT’T→FT’T'T'→εT'→*FT'T'→εT'→εFF→iF→(E)2025/1/11Page64第5章自頂向下語法分析方法P96例1已知文法G[S]: SaH HaMd|d MAb|ε AaM|e1.判斷G[S]是否為LL(1