5第五章自頂向下語法分析方法

1、第五章第五章 自頂向下語法分析方法自頂向下語法分析方法學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo): :掌握：掌握：ll(1)ll(1)文法的判別，預(yù)測分析文法的判別，預(yù)測分析法，遞歸子程序的構(gòu)造方法法，遞歸子程序的構(gòu)造方法理解：理解：llll（1 1）文法文法了解：不確定的自頂向下分析了解：不確定的自頂向下分析語法分析的作用是識別由詞法分析給出的單詞序語法分析的作用是識別由詞法分析給出的單詞序列是否是給定文法的正確句子列是否是給定文法的正確句子分類分類:語法分析語法分析自頂向下分析自頂向下分析自底向上分析自底向上分析確定的確定的不確定的不確定的算法優(yōu)先分析（第六章）算法優(yōu)先分析（第六章）lr分析（第七章）分析（第七章）

2、自頂向下的基本思想自頂向下的基本思想:從文法的開始符出發(fā)企圖推導(dǎo)出與輸入的單詞串從文法的開始符出發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子完全相匹配的句子.5.1確定的自頂向下分析思想確定的自頂向下分析思想5.2ll(1)文法的判別文法的判別5.3某些非某些非ll(1)文法到文法到ll(1)文法的等價(jià)變換文法的等價(jià)變換5.4不確定的自頂向下分析思想不確定的自頂向下分析思想5.5確定的自頂向下分析方法確定的自頂向下分析方法5.1 確定的自頂向下分析思想確定的自頂向下分析思想1 確定分析的條件確定分析的條件2 開始符號集開始符號集first()的定義的定義3 后跟符號集后跟符號集follow(a)

3、的定義的定義4 選擇集合選擇集合select(a)的定義的定義5 ll(1)文法的定義文法的定義1 確定分析的條件確定分析的條件從文法的開始符出發(fā)，如能根據(jù)當(dāng)前的從文法的開始符出發(fā)，如能根據(jù)當(dāng)前的輸入符號（單詞符號）輸入符號（單詞符號）唯一地唯一地確定選用確定選用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，則分析是確定的。哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，則分析是確定的。例例1 設(shè)有文法設(shè)有文法g1s:spa|qbacad|abdb|b若輸入串若輸入串w=pccadd。自頂向下的推導(dǎo)過程為自頂向下的推導(dǎo)過程為:ssapcadcada=pa =pcad =pccadd =pccaddg1s有如下特點(diǎn)：有如下特點(diǎn)： (1) 每個(gè)產(chǎn)生式

4、的右部由終結(jié)符開頭每個(gè)產(chǎn)生式的右部由終結(jié)符開頭; (2) 同一非終結(jié)符的不同產(chǎn)生式的右部由不同一非終結(jié)符的不同產(chǎn)生式的右部由不同的終結(jié)符開頭。同的終結(jié)符開頭。對于這種文法，在推導(dǎo)過程可以根據(jù)當(dāng)前的對于這種文法，在推導(dǎo)過程可以根據(jù)當(dāng)前的輸入符號唯一確定選哪個(gè)產(chǎn)生式往下推導(dǎo)，輸入符號唯一確定選哪個(gè)產(chǎn)生式往下推導(dǎo)，即分析過程是確定的。即分析過程是確定的。例例2：設(shè)有文法設(shè)有文法g2s為為:sap|bqaa|cabb|dbpascacaa=ccaps=cap =ccap=ap該例說明，當(dāng)該例說明，當(dāng)(1) 產(chǎn)生式右部以終結(jié)符或非終結(jié)符開頭（無空產(chǎn)生式右部以終結(jié)符或非終結(jié)符開頭（無空產(chǎn)生式）；產(chǎn)生式）；

5、(2) 同一非終結(jié)符的不同產(chǎn)生式的右部由不同的同一非終結(jié)符的不同產(chǎn)生式的右部由不同的符號開頭。符號開頭。對于這種文法，在推導(dǎo)過程選用哪個(gè)產(chǎn)生式不對于這種文法，在推導(dǎo)過程選用哪個(gè)產(chǎn)生式不直觀，關(guān)鍵是判斷直觀，關(guān)鍵是判斷產(chǎn)生式右部推出的開始符號產(chǎn)生式右部推出的開始符號（集）（集），分析過程可能是確定，分析過程可能是確定若輸入串若輸入串w=ccap,自頂向下的自頂向下的推導(dǎo)過程為：推導(dǎo)過程為：例例3：設(shè)有文法設(shè)有文法g3ssaa|dabas| 若輸入串若輸入串w=abd，自頂向下的推導(dǎo)過程為：自頂向下的推導(dǎo)過程為：aasbsa d=abd s=abas =abs文法的特點(diǎn)是文法的特點(diǎn)是:包含空產(chǎn)生式

6、包含空產(chǎn)生式對于空產(chǎn)生式左部的非終結(jié)符對于空產(chǎn)生式左部的非終結(jié)符，關(guān)鍵是判斷關(guān)鍵是判斷該該非終結(jié)符的后跟符號（集非終結(jié)符的后跟符號（集），分析過程可），分析過程可能是確定的。能是確定的。=aa要進(jìn)行確定的自頂向下的分析，文法要滿足一要進(jìn)行確定的自頂向下的分析，文法要滿足一定的限制定的限制即文法是即文法是ll(1)文法。文法。先研究三個(gè)定義先研究三個(gè)定義開始符號集開始符號集firstfirst后跟符號集后跟符號集followfollow選擇集合選擇集合selectselect2 開始符號集開始符號集first()的定義的定義定義定義:設(shè)設(shè)g=(vn, vt, p, s)是上下文無關(guān)文法，是上下文

7、無關(guān)文法，(vn vt)* first( ) = a vt | * a. 若若* 則規(guī)定則規(guī)定 first( )直觀上說文法符號串直觀上說文法符號串 的開始符號集是由的開始符號集是由 推導(dǎo)出的開頭的終結(jié)符（包括推導(dǎo)出的開頭的終結(jié)符（包括）組成。組成。 例文法例文法g2s: sapsbqaaacabbbdbfirst(ap)=a,cfirst(bq)=b,dfirst(a)=a first(ca)=cfirst(b)=bfirst(db)=d由于由于同一非終結(jié)符同一非終結(jié)符的兩個(gè)的兩個(gè)產(chǎn)生式的右部產(chǎn)生式的右部推導(dǎo)出來的推導(dǎo)出來的開始符號集開始符號集不相交，因此可根據(jù)當(dāng)前輸入符屬于哪不相交，因此可

8、根據(jù)當(dāng)前輸入符屬于哪個(gè)產(chǎn)生式右部的開始符號集而決定選哪個(gè)產(chǎn)生式進(jìn)個(gè)產(chǎn)生式右部的開始符號集而決定選哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，可以進(jìn)行確定的自頂向下分析行推導(dǎo)，可以進(jìn)行確定的自頂向下分析3 后跟符號集后跟符號集follow(a)的定義的定義定義定義 設(shè)設(shè)g=(vt, vn, p, s)是上下文無關(guān)文法，是上下文無關(guān)文法，avn ，follow(a)=a| |s=*aa，a vt，若有若有s=* a，則規(guī)定則規(guī)定 # follow(a)（注：（注： # 輸入串輸入串#，#做為輸入串的結(jié)束符）做為輸入串的結(jié)束符）直觀上說直觀上說,非終結(jié)符非終結(jié)符a的后跟符號集是由句型中緊跟的后跟符號集是由句型中緊跟a后的那

9、些終結(jié)符（包括后的那些終結(jié)符（包括#）組成。）組成。例例 文法文法g3s:saa|d abas|由由 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說明：說明：對于非終結(jié)符對于非終結(jié)符a的兩個(gè)產(chǎn)生式的兩個(gè)產(chǎn)生式 abas 和和 a，當(dāng)輸入符號當(dāng)輸入符號first(bas)=b時(shí)，選時(shí)，選abas推導(dǎo)，推導(dǎo)，當(dāng)輸

10、入符號當(dāng)輸入符號follow(a)=#,a,d 時(shí)，選時(shí)，選a推導(dǎo)。推導(dǎo)。由于由于first(bas)follow(a)=，所以可進(jìn)行確定所以可進(jìn)行確定的自頂向下分析。的自頂向下分析。4 選擇集合選擇集合select(a)的定義的定義定義定義對給定的上下文無關(guān)文法的產(chǎn)生式對給定的上下文無關(guān)文法的產(chǎn)生式a，avn，v*，若若*,則則select(a)=first()若若=*, 則則select(a)=(first()-)follow(a)解釋解釋當(dāng)當(dāng)a面面對應(yīng)輸入符對應(yīng)輸入符a，在自頂向下的分析中應(yīng)選擇這在自頂向下的分析中應(yīng)選擇這樣的產(chǎn)生式樣的產(chǎn)生式a 進(jìn)行推導(dǎo)：進(jìn)行推導(dǎo)：first( )中包含

11、中包含a；此外若此外若 可能導(dǎo)出空串，可能導(dǎo)出空串，a自動獲得匹配，輸入符自動獲得匹配，輸入符a有可能與有可能與a后后的一個(gè)符號匹配，所以當(dāng)?shù)囊粋€(gè)符號匹配，所以當(dāng)a應(yīng)屬于應(yīng)屬于follow(a)時(shí)，選擇產(chǎn)生式時(shí)，選擇產(chǎn)生式a 也是可以的也是可以的。 直觀上說某產(chǎn)生式直觀上說某產(chǎn)生式a的選擇集合是指遇到哪些輸?shù)倪x擇集合是指遇到哪些輸入符號（包括入符號（包括#）時(shí)選用該產(chǎn)生式向下推導(dǎo)。）時(shí)選用該產(chǎn)生式向下推導(dǎo)。例例 g3s: saa sd abas aselect(saa)=first(aa)=aselect(sd)=first(d)=dselect(abas)=first(bas)=bselec

12、t(a)=follow(a)=#,a,d若若*,則則select(a)=first()若若=*, 則則select(a)=(first()-)follow(a)說明：說明：同一非終結(jié)符的不同產(chǎn)生式同一非終結(jié)符的不同產(chǎn)生式a與與a，若若select(a)select(a)=，則一定則一定可以進(jìn)行確定的自頂向下分析可以進(jìn)行確定的自頂向下分析5 ll(1)文法的定義文法的定義定義定義 : 一個(gè)上下文無關(guān)文法是一個(gè)上下文無關(guān)文法是ll(1)文法的充分必要條件是，文法的充分必要條件是， 對每個(gè)非終結(jié)符對每個(gè)非終結(jié)符a的兩個(gè)不同產(chǎn)生式的兩個(gè)不同產(chǎn)生式a與與a，滿足滿足select(a)select(a)=

13、。 ll(1)文法的含義是：文法的含義是：第一個(gè)第一個(gè)l表示從左到右掃描輸入串表示從左到右掃描輸入串第二個(gè)第二個(gè)l表示分析過程用最左推導(dǎo)表示分析過程用最左推導(dǎo)1表明只需向前看一個(gè)符號便可以決定選哪個(gè)產(chǎn)生式表明只需向前看一個(gè)符號便可以決定選哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，類似地進(jìn)行推導(dǎo)，類似地ll(k)文法需要向前看文法需要向前看k個(gè)符號才個(gè)符號才可以確定選用哪個(gè)產(chǎn)生式?？梢源_定選用哪個(gè)產(chǎn)生式。例例 有文法有文法gs為：為：saas sbabaaselect(saas)= aselect(sb)= bselect(aba)= bselect(a)=follow(a)= a,b由于由于select(aba)s

14、elect(a)=b，所以文法所以文法gs不是不是ll(1)文法，當(dāng)文法，當(dāng)a遇輸入符遇輸入符b時(shí)，不時(shí)，不能確定選能確定選aba還是還是a去推導(dǎo)。去推導(dǎo)。5.2 ll(1)文法的判別文法的判別要判別一個(gè)上下文無關(guān)文法是否是要判別一個(gè)上下文無關(guān)文法是否是ll(1)文法文法分為五步：分為五步： 1. 求能推出求能推出的非終結(jié)符集的非終結(jié)符集 2. 計(jì)算每個(gè)產(chǎn)生式右部計(jì)算每個(gè)產(chǎn)生式右部的的first()集集 3. 計(jì)算每個(gè)非終結(jié)符計(jì)算每個(gè)非終結(jié)符a的的follow(a)集集 4. 計(jì)算每個(gè)產(chǎn)生式計(jì)算每個(gè)產(chǎn)生式a的的select(a)集集 5. 按按ll(1)文法的定義判別文法的定義判別1. 求出能

15、推出求出能推出的非終結(jié)符集的非終結(jié)符集算法算法:用用s表示能推出表示能推出的非終結(jié)符集的非終結(jié)符集第一步令第一步令s= aj | aj 產(chǎn)生式集產(chǎn)生式集對每個(gè)產(chǎn)生式對每個(gè)產(chǎn)生式p: apx1.xn，若若x1.xn s，則則 s:= s ap 重復(fù)第二步的循環(huán)重復(fù)第二步的循環(huán)，直至直至s 收斂（不再收斂（不再變化）為止。變化）為止。例例gs：sab|bcab|bad|cad|b das|ca,b,a,b,s s 第一次第一次 a,ba,b初值初值a,b,sa,b,s收斂收斂第二次第二次非終結(jié)符集非終結(jié)符集s s能推出能推出的非終結(jié)符集為的非終結(jié)符集為a,b,s2. 計(jì)算每個(gè)產(chǎn)生式右部計(jì)算每個(gè)產(chǎn)生

16、式右部的的first()集集首先對每一首先對每一文法符號文法符號x (x vt vn)，求求first(x)的算法的算法:1.對每個(gè)對每個(gè)a vt ：first(a)= a 2.對每個(gè)對每個(gè)a vn ：若若 a * 則則 first(a):= 否則否則 first(a):= 3.對每個(gè)產(chǎn)生式對每個(gè)產(chǎn)生式 ax1xjxn 做：做：first(a)=first(a) sectionfirst(x1xjxn)其中其中 sectionfirstsectionfirst(x(x1 1x xj jx xn n) ) = (first(x= (first(x1 1) -) ) -) (first(x(fir

17、st(x2 2)-)-) (first(first(x xj j) ) -) -) first(first(x xj j+1+1) ) x xj j+1+1是產(chǎn)生式右部中第一個(gè)不能推出是產(chǎn)生式右部中第一個(gè)不能推出的符號的符號 若若x x1 1 * * 則則sectionfirstsectionfirst(x(x1 1x xj jx xn n)=first(x)=first(x1 1) ) 若若x x1 1x xn n全可推出全可推出則則sectionfirstsectionfirst(x(x1 1x xn n)=first(x)=first(x1 1)first(first(x xn n) )

18、 4.4. 重復(fù)重復(fù)3 3直到每個(gè)符號的直到每個(gè)符號的firstfirst集合都不再增大為止。集合都不再增大為止。例例gs：sab|bc ab| bad| cad|b das|cb ba aa ca cb a cb a c a b b afirstfirst集集(3)(3)b ba aa ca cb b a b bfirstfirst集集(2)(2)b ba a firstfirst集集(1)(1)a ab bc cd da ab bs sa ab bfirstfirst集集(0)(0)已求出能推出已求出能推出的非終結(jié)符集的非終結(jié)符集為為a,b,sbbab ba ca caa ca c利用求出

19、利用求出每個(gè)文法符號每個(gè)文法符號的的first集集求求符號串符號串的的first集集設(shè)設(shè)=x1x2xn1. 當(dāng)當(dāng)x1不能不能=* ，則，則first()=first(x1)2. 若對任何若對任何j (1jn）都有都有first(xj), 則則first()=(first(x1) - ) (first(xj) - ) first(xj+1) 3. 若對所有若對所有i (1in)，都有都有first(xi)， 則則 first()=first(x1)first(xn) 例例gs sab|bc ab| bad| cad|b das|c已求出非終結(jié)符的已求出非終結(jié)符的first集合如下集合如下:fir

20、st(s)=a,b, first(a)=b, first(b)=a, first(c)=a,b,cfirst(d)=a,c 產(chǎn)生式右部產(chǎn)生式右部符號串符號串的開始符集合為的開始符集合為:sabfirst(ab)=first(a)first(b)=a,b,sbcfirst(bc)= bafirst()= abfirst(b)= bcadfirst(ad)=(first(a)-)first(d) =b,a,cdasfirst(as)= a3計(jì)算每個(gè)非終結(jié)符計(jì)算每個(gè)非終結(jié)符a的的follow(a)集集1.對所有對所有a vn令令follow(a)= ;對開始符對開始符s，令令follow(s)=#

21、# 因?yàn)橐驗(yàn)閟=*s，顯然，顯然#follow(s)2. 對每條產(chǎn)生式對每條產(chǎn)生式axby，考察產(chǎn)生式右部的每一非終考察產(chǎn)生式右部的每一非終結(jié)符結(jié)符b， x,y v*，如果如果y不能推出不能推出follow(b)=follow(b) first(y) 否則否則 follow(b)=follow(b) (first(y)-) follow(a)3. 重復(fù)重復(fù)2，直至對所有，直至對所有a vn，follow(a)收斂為止。收斂為止。若若afollow(a) ,則表明則表明s=*aa， 由于由于axby，且且y=*,則有則有 s=*aa=xbya=xba，即即s=*xba, 所以所以afollow(

22、b)例例gs：1sab2sbc3ab4a5bad6b7cad8cb9das10dc已求出已求出 非終結(jié)符的非終結(jié)符的first集合如下集合如下:first(s)=a,b, first(a)=b, first(b)=a, first(c)=a,b,cfirst(d)=a,c #d#c#ba #a#a # csfollow集集(2)follow集集(1)follow集集(0)c4計(jì)算每個(gè)產(chǎn)生式計(jì)算每個(gè)產(chǎn)生式a的的select(a)集集按定義計(jì)算按定義計(jì)算select(a)： 若若*，則則select(a)=first() 若若=*，則則select(a)=(first()-)follow(a)例例

23、gs：sab|bc ab| bad| cad|b das|c是否是否=* * firstfirst集集 followfollow集集s s是是a, b,#a a是是 b,a, c, # b b是是 a,#c c否否a,b,ca,b,c #d d否否a,ca,c#部分產(chǎn)生式的部分產(chǎn)生式的select集合集合select(sab)=(first(ab)-)follow(s)=b,a,#select(sbc)=first(bc) =bselect(a)=(first()-）follow(a)=a,c,#select(ab)=first(b) =bselect(bad)=first(ad) =asel

24、ect(cad)=first(ad) =b,a,c5. 按按ll(1)文法的定義判別文法的定義判別產(chǎn)生式的產(chǎn)生式的select集如下集如下:select(sab)= b,a,#select(sbc)=bselect(a)= a,c,#select(ab)= bselect(b)= #select(bad)=aselect(cad)= b,a,cselect(cb) =bselect(das)= aselect(dc)= c 由于由于 select(sab)select(sbc)=b select(cad)select(cb)=b所以文法所以文法gs不是不是ll(1)文法文法5.3 某些非某些非

25、ll(1)文法到文法到ll(1)文法的等價(jià)變換文法的等價(jià)變換非非ll(1)文法文法含有含有左公共因子左公共因子的文法的文法若文法中含有形如：若文法中含有形如：a|r 的產(chǎn)生式，稱文法的產(chǎn)生式，稱文法含有左公共因子。含有左公共因子。顯然顯然,select(a)select(a r),文法文法不是不是ll(1)文法文法含有含有左遞歸左遞歸的文法的文法文法中只要含有下列形式的產(chǎn)生式（含有文法中只要含有下列形式的產(chǎn)生式（含有a a或含有或含有b b或二者皆有）則稱文法含有左遞歸：或二者皆有）則稱文法含有左遞歸：a)a)a aa ab)b)ababbaba在在a)a)中含有左遞歸的產(chǎn)生式，稱為中含有左遞

26、歸的產(chǎn)生式，稱為直接左遞歸直接左遞歸；在在b)b)中雖然沒有含左遞歸的產(chǎn)生式，中雖然沒有含左遞歸的產(chǎn)生式，但但a a=b b=aa 即即a a=+ + a a, ,稱為稱為間接左遞歸間接左遞歸以直接左遞歸為例，若有如下產(chǎn)生式以直接左遞歸為例，若有如下產(chǎn)生式aa |a 其中其中 和和 為任意語法符號串。為任意語法符號串。不難證明有下面關(guān)系式：不難證明有下面關(guān)系式：select( aa ) ) first( a ) first( )select( a ) first( )故故aa 和和a 的的select集集相交相交，不是不是ll(1)文法。文法。對非對非ll(1)文法進(jìn)行等價(jià)變換文法進(jìn)行等價(jià)變換

27、提取左公共因子提取左公共因子消除左遞歸消除左遞歸注意：變換后的文法不一定是注意：變換后的文法不一定是ll(1)文法，文法，文法不含左遞歸和左公共因子只是文法不含左遞歸和左公共因子只是ll(1)文文法的必要條件。法的必要條件。1 提取左公共因子提取左公共因子將產(chǎn)生式將產(chǎn)生式a|r 等價(jià)變換為等價(jià)變換為:a(|r)，將括號內(nèi)用一新引入的非終結(jié)符將括號內(nèi)用一新引入的非終結(jié)符a表示表示,得得 aa，a|r一般形式：若一般形式：若a1|2|n,提取左公共因子后變?yōu)樘崛∽蠊惨蜃雍笞優(yōu)閍a，a 1|2|n若在若在i中仍含有左公共因子中仍含有左公共因子,可再次提取可再次提取.例例 文法文法g1：sasb|a

28、s| 提左因子得提左因子得:sas(b|)| 引進(jìn)新的非終結(jié)符得引進(jìn)新的非終結(jié)符得:sass|s b|2. 消除左遞歸消除左遞歸1) 消除直接左遞歸消除直接左遞歸文法文法g:ssa|b可改寫成可改寫成 sbss as|一般情形一般情形:含直接左遞歸的文法含直接左遞歸的文法g：aa1|a2|am|1|2|n消除左遞歸后改寫成：消除左遞歸后改寫成： a1a|2a|na a1 a|2 a|m a| 2)消除間接左遞歸消除間接左遞歸將間接左遞歸變成直接左遞歸，再消除將間接左遞歸變成直接左遞歸，再消除算法步驟：算法步驟：1.把文法的所有非終結(jié)符按任一順序排列，把文法的所有非終結(jié)符按任一順序排列，如：如：

29、a1，a2，an2.從從a1開始，按以下順序處理開始，按以下順序處理ai。首先，消除左部為首先，消除左部為ai的產(chǎn)生式的直接左遞歸的產(chǎn)生式的直接左遞歸然后，若左部為然后，若左部為ai的產(chǎn)生式的右部為非終結(jié)的產(chǎn)生式的右部為非終結(jié)符符aj(j* ，且，且follow(a) first(bas) =b ，從而引起回溯，從而引起回溯例例3文法文法g：ssasb輸入串輸入串w=baa，推導(dǎo)樹為推導(dǎo)樹為:ssabsbssa回溯回溯回溯回溯ssasassasab由于文法含有左遞歸而引起回溯由于文法含有左遞歸而引起回溯5.5 確定的自頂向下分析方法確定的自頂向下分析方法確定的自頂向下分析方法有：確定的自頂向下

30、分析方法有：遞歸子程序法遞歸子程序法(recursive-descent parser)預(yù)測分析法預(yù)測分析法(predictive parser)兩種方法都要求文法是兩種方法都要求文法是ll(1)文法。文法。5.5.1 遞歸子程序法遞歸子程序法q實(shí)現(xiàn)思想：實(shí)現(xiàn)思想：對文法中的每個(gè)非終結(jié)符編寫一個(gè)遞歸過程，對文法中的每個(gè)非終結(jié)符編寫一個(gè)遞歸過程，識別由該非終結(jié)符推出的串。當(dāng)非終結(jié)符有多識別由該非終結(jié)符推出的串。當(dāng)非終結(jié)符有多條產(chǎn)生式時(shí)，按當(dāng)前輸入符屬于哪條產(chǎn)生式的條產(chǎn)生式時(shí)，按當(dāng)前輸入符屬于哪條產(chǎn)生式的select集可唯一確定選擇哪個(gè)產(chǎn)生式進(jìn)行匹集可唯一確定選擇哪個(gè)產(chǎn)生式進(jìn)行匹配。配。當(dāng)識別到終

31、結(jié)符時(shí)，與當(dāng)前輸入符號匹配，當(dāng)識別到終結(jié)符時(shí)，與當(dāng)前輸入符號匹配，并讀取下一輸入符；并讀取下一輸入符；當(dāng)識別到非終結(jié)符時(shí)，則調(diào)用該非終結(jié)符相當(dāng)識別到非終結(jié)符時(shí)，則調(diào)用該非終結(jié)符相應(yīng)的過程。應(yīng)的過程。例例 算術(shù)表達(dá)式文法算術(shù)表達(dá)式文法g ee+tttt*fff(e)i1）消除左遞歸得消除左遞歸得 g: ete e+te tft t*ftf(e)i2 2）求出求出gg的選擇集合的選擇集合select(ete ) = (,i select(e+te ) = + select(e ) = ),# select(tft ) = (,i select(t*ft ) = * select(t ) = +,)

32、,# select(f(e) ) = ( select(f i ) = i g是是ll(1)文法文法1 判斷是否可以應(yīng)用遞歸子程序法判斷是否可以應(yīng)用遞歸子程序法n 表達(dá)式的正規(guī)式表達(dá)式的正規(guī)式 e=t(+t)e=t(+t)*n 轉(zhuǎn)換成正則文法轉(zhuǎn)換成正則文法etbetb， b(+t) b(+t)* ，即即b(+t)b(+t)* b(+t)bb(+t)b， b b ，即即b (+t)bb (+t)b n 與與ee+tt 消除左遞歸所得消除左遞歸所得ete e+te 一致一致表表達(dá)達(dá)式式項(xiàng)項(xiàng)原產(chǎn)生式變換后產(chǎn)生式規(guī)則1axyaxb by規(guī)則2ax*yaxa ay規(guī)則3ax|yax ay2 構(gòu)造文法構(gòu)造

33、文法g的遞歸下降分析器的遞歸下降分析器定義：定義：當(dāng)一個(gè)文法滿足當(dāng)一個(gè)文法滿足ll(1)ll(1)條件時(shí)，就為它構(gòu)造一條件時(shí)，就為它構(gòu)造一個(gè)不帶回溯的自頂向下的分析程序，這個(gè)分析個(gè)不帶回溯的自頂向下的分析程序，這個(gè)分析程序由一組程序由一組遞歸過程遞歸過程組成，每個(gè)過程對應(yīng)文法組成，每個(gè)過程對應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞遞歸下降分析器歸下降分析器。組成：組成：遞歸下降分析器由一個(gè)主程序遞歸下降分析器由一個(gè)主程序mainmain和每個(gè)非終結(jié)符和每個(gè)非終結(jié)符對應(yīng)的一個(gè)遞歸過程組成。對應(yīng)的一個(gè)遞歸過程組成。用到的一些子過程：用到的一些子過程：過程

34、過程getnextgetnext負(fù)責(zé)讀入下一個(gè)負(fù)責(zé)讀入下一個(gè)tokentoken字字過程過程errorerror負(fù)責(zé)報(bào)告語法錯(cuò)誤負(fù)責(zé)報(bào)告語法錯(cuò)誤約定：約定：變量變量tokentoken存放已讀入的存放已讀入的tokentoken字字過程進(jìn)入時(shí)變量過程進(jìn)入時(shí)變量tokentoken存放了一個(gè)待匹配的存放了一個(gè)待匹配的tokentoken字字退出過程時(shí)，變量退出過程時(shí)，變量tokentoken中仍存放著一個(gè)待匹配中仍存放著一個(gè)待匹配的的tokentoken字。字。 非終結(jié)符相應(yīng)的分析子程序的構(gòu)造方法非終結(jié)符相應(yīng)的分析子程序的構(gòu)造方法1) 對于每個(gè)非終結(jié)符對于每個(gè)非終結(jié)符u，編寫一個(gè)相應(yīng)的子程序編寫

35、一個(gè)相應(yīng)的子程序p(u);2) 對于產(chǎn)生式對于產(chǎn)生式ux1 | x2 |xn，x1,.xn都都 關(guān)于關(guān)于u的子的子程序程序p(u)按如下方法構(gòu)造：按如下方法構(gòu)造：if token in first(x1) then p(x1) else if token in first(x2) then p(x2) else . if token in first(xn) then p(xn) else error3) 如果如果u還有空產(chǎn)生式還有空產(chǎn)生式u ,則算法中的語句：則算法中的語句：if token in first(xn) then p(xn) else error改寫為改寫為if token i

36、n first(xn) then p(xn) else if token not in follow(u) then error4) 對于符號串對于符號串x=y1y2yn；p(x)的含義為：的含義為：begin p(y1);p(y2);p(yn) end如果如果yivn，則則p(yi)就代表調(diào)用就代表調(diào)用yi的子程序；的子程序；yivt t，則則p(yi)為形如下述語句的一段程序?yàn)樾稳缦率稣Z句的一段程序if token=yi then getnext(token) else error(1) program main; /* 主程序主程序,匹配匹配ee# */ begin getnext (t

37、oken); e (token); /* 轉(zhuǎn)匹配轉(zhuǎn)匹配ete */ if token # then error end. 構(gòu)造文法構(gòu)造文法g：ete e+te tft t*ft f(e)i的遞歸下降分析器的遞歸下降分析器(2) procedure e (token); /*匹配匹配ete*/ begin t (token); /*轉(zhuǎn)匹配轉(zhuǎn)匹配tft*/ e (token) /*轉(zhuǎn)匹配轉(zhuǎn)匹配e+te*/ end; (3) procedure e (token); /*匹配匹配e+te*/ begin if token=+ then /*選擇產(chǎn)生式選擇產(chǎn)生式e+te*/ begin getnext

38、 (token);/*匹配匹配+,讀下一個(gè)讀下一個(gè)token字字*/ t (token); /*轉(zhuǎn)匹配轉(zhuǎn)匹配tft*/ e (token) /*轉(zhuǎn)匹配轉(zhuǎn)匹配e+te*/ end else /*e對應(yīng)的語句對應(yīng)的語句*/if token) and token# then error /*構(gòu)造方法構(gòu)造方法3，求，求follow(e)= follow(e)=) , # */ end;(5) procedure t (token); /* 匹配匹配t*ft */ begin if token = * then /* 選擇產(chǎn)生式選擇產(chǎn)生式t*ft */ begin getnext (token); /*

39、 匹配匹配*，讀下一，讀下一token字字 */ f (token); /* 轉(zhuǎn)匹配轉(zhuǎn)匹配f(e)i */ t (token) /* 轉(zhuǎn)匹配轉(zhuǎn)匹配t*ft */ end else /* t對應(yīng)的語句對應(yīng)的語句*/if token+ and token) and token# then error end; /*follow(t)= follow(t)=first(e)+ follow(e)=+ ,) , # */ (4) procedure t (token); /*匹配匹配tft */ begin f (token); /*轉(zhuǎn)匹配轉(zhuǎn)匹配f(e)i*/ t (token) /*轉(zhuǎn)匹配轉(zhuǎn)匹配t*

40、ft*/ end; (6) procedure f (token); /* 匹配匹配f(e)i */ begin if token = ( then /*選擇產(chǎn)生式選擇產(chǎn)生式f(e) */ begin getnext (token); /* 匹配匹配(，讀下一，讀下一token字字 */ e (token); /* 轉(zhuǎn)匹配轉(zhuǎn)匹配ete */ if token=) then getnext (token) /* 匹配匹配), 讀下一讀下一token字字 */ else error end else /* 選擇產(chǎn)生式選擇產(chǎn)生式fi */ if token=i then getnext (token

41、) else error end; 特點(diǎn)：特點(diǎn)：優(yōu)點(diǎn)：簡單直觀、易于構(gòu)造優(yōu)點(diǎn)：簡單直觀、易于構(gòu)造缺點(diǎn)：缺點(diǎn)：對文法要求高，必須滿足對文法要求高，必須滿足ll(1)文法；文法；遞歸調(diào)用多，速度慢，占用空間多遞歸調(diào)用多，速度慢，占用空間多實(shí)用性：許多高級語言，如實(shí)用性：許多高級語言，如pascal、c等編等編譯系統(tǒng)常常采用此方法。譯系統(tǒng)常常采用此方法。5.5.2 預(yù)測分析方法預(yù)測分析方法一個(gè)預(yù)測分析器由三個(gè)部分組成：一個(gè)預(yù)測分析器由三個(gè)部分組成：預(yù)測分析程序：控制分析過程的進(jìn)行。預(yù)測分析程序：控制分析過程的進(jìn)行。分析棧：存放從文法開始符號出發(fā)的自頂向下推分析棧：存放從文法開始符號出發(fā)的自頂向下推導(dǎo)過程中導(dǎo)過程中等待匹配等待匹配的文法符號。開始時(shí)放入的文法符號。開始時(shí)放入#和文法開始符，結(jié)束時(shí)棧應(yīng)是空的。和文法開始符，結(jié)束時(shí)棧應(yīng)是空的。預(yù)測分析表：是一張二維表，元素預(yù)測分析表：是一張二維表，元素ma,a的內(nèi)容的內(nèi)容是當(dāng)非終結(jié)符是當(dāng)非終結(jié)符a面臨輸入符號面臨輸入符號a（終結(jié)符或句子括終結(jié)符或句子括號）時(shí)應(yīng)選取的號）時(shí)應(yīng)選取的產(chǎn)生式產(chǎn)生式，當(dāng)無產(chǎn)生式時(shí)，元素，當(dāng)無產(chǎn)生式時(shí)，元素內(nèi)容為轉(zhuǎn)向出錯(cuò)處理。內(nèi)容為轉(zhuǎn)向出錯(cuò)處理。1.1. 構(gòu)造預(yù)測分析表構(gòu)造預(yù)測分析表步驟