byyl-ch4自頂向下語(yǔ)法分析方法

自動(dòng)機(jī)、正則文法、正則表達(dá)式

的相互轉(zhuǎn)化正則文法NFA正則表達(dá)式123456DFA最小化復(fù)習(xí)第五章語(yǔ)法分析5.1自頂向下分析法5.1.1自頂向下分析的思想5.1.2左遞歸和回溯性質(zhì)5.1.3遞歸子程序法（遞歸下降分析法）5.1.4LL(1)分析法編譯程序的功能和組織結(jié)構(gòu)表處理詞法分析源程序目標(biāo)程序錯(cuò)誤處理語(yǔ)法分析語(yǔ)義分析目標(biāo)代碼生成前端后端中間代碼優(yōu)化中間代碼生成44

功能：根據(jù)文法規(guī)則，從源程序單詞符號(hào)串中識(shí)別出語(yǔ)法成分，并進(jìn)行語(yǔ)法檢查。

基本任務(wù)：識(shí)別符號(hào)串S是否為某語(yǔ)法成分兩大類分析方法：自頂向下分析自底向上分析語(yǔ)法分析概述5若ZS則SL(G[Z])否則SL(G[Z])+G[Z]存在主要問(wèn)題:

左遞歸問(wèn)題回溯問(wèn)題

主要方法:

遞歸子程序法

LL分析法自頂向下分析算法的基本思想為：若ZS則SL(G[Z])否則SL(G[Z])+G[Z]自底向上分析算法的基本思想為：存在主要問(wèn)題:

句柄的識(shí)別問(wèn)題主要方法:

算法優(yōu)先分析法

LR分析法自頂向下分析665.1.1自頂向下分析的思想5.1.2自頂向下分析存在的問(wèn)題及解決方法5.1.3遞歸子程序法（遞歸下降分析法）5.1.4LL(1)分析法5.1.1自頂向下分析的思想77我們可以通過(guò)一例子來(lái)說(shuō)明語(yǔ)法分析過(guò)程給定符號(hào)串S，若預(yù)測(cè)是某一語(yǔ)法成分，那么可根據(jù)該語(yǔ)法成分的文法,設(shè)法為S構(gòu)造一棵語(yǔ)法樹.若成功,則S最終被識(shí)別為某一語(yǔ)法成分,即

SL(G[Z])其中G[Z]為某語(yǔ)言成分的文法.若不成功,則SL(G[Z])88例：已知符號(hào)串S=cad

文法G[Z]:Z→cAdA→ab|a求解SL(G[Z])分析過(guò)程是設(shè)法建立一棵語(yǔ)法樹,使語(yǔ)法樹的末端結(jié)點(diǎn)與給定符號(hào)串相匹配.1.開始:令Z為根結(jié)點(diǎn)Z2.用Z的右部,符號(hào)串去匹配輸入串

·ZcAd完成一步推導(dǎo)ZcAd

檢查c-c匹配

A是非終結(jié)符,將匹配任務(wù)交給A993.選用A的右部符號(hào)串匹配輸入串

A有兩個(gè)右部,選第一個(gè)

·cAdabZ完成進(jìn)一步推導(dǎo)Aab

檢查,a-a匹配,b-d不匹配(失敗)但是還不能冒然宣布SL(G[Z])4.回溯即砍掉A的子樹改選A的第二右部·ZcAdaAa檢查a-a匹配

d-d匹配建立語(yǔ)法樹,末端結(jié)點(diǎn)為cad與輸入cad相匹配,建立了推導(dǎo)序列ZcAdcad∴cadL(G(Z))S=cadG[Z]:Z→cAdA→ab|a分析工作要部分地或全部地退回去重做叫回溯自頂向下分析方法特點(diǎn)1.分析過(guò)程是帶有預(yù)測(cè)的，對(duì)輸入符號(hào)串要預(yù)測(cè)屬于什么語(yǔ)法成分，然后根據(jù)該語(yǔ)法成分的文法建立語(yǔ)法樹。2.分析過(guò)程是一種試探過(guò)程，是盡一切辦法(選用不同規(guī)則)

設(shè)法建立語(yǔ)法樹的過(guò)程，由于是試探過(guò)程，故難免有失敗，所以分析過(guò)程需進(jìn)行回溯，因此我們也稱這種方法是帶回溯的自頂向下分析方法。5.1.2自頂向下分析存在的問(wèn)題及解決方法自頂向下分析方法的基本缺點(diǎn)：不能處理具有左遞歸性的文法自頂向下分析為什么不能處理左遞歸文法？文法G，存在U∈Vn，ifU==>U…,則G為左遞歸文法+1．左遞歸文法：左遞歸文法回溯問(wèn)題1212在采用最左推導(dǎo)的自頂向下分析中，左遞歸的存在是十分有害的，例如，考慮文法G[S]：SSa|b，分析輸入串baaa是否為文法的合法句子。按照自頂向下分析法，對(duì)輸入串baaa的當(dāng)前輸入符b從開始符號(hào)S開始進(jìn)行最左推導(dǎo)，若首次使用SSa則可能得到：

SSaSaaSaaaSaaaa如果文法具有間接左遞歸，則也將發(fā)生上述問(wèn)題，只不過(guò)環(huán)的圈子兜的更大。要實(shí)行自頂向下分析，必須要消除文法的左遞歸，下面我們將介紹直接左遞歸的消除方法，在此基礎(chǔ)上再介紹一般左遞歸的消除方法。自頂向下分析為什么不能處理左遞歸文法？1313將左遞歸規(guī)則改為右遞歸規(guī)則若：S→SS→則可改寫為：S

→S’

S’→S’|ε證明的關(guān)鍵步驟：S

->Sα|βS->β|βα|βαα|βααα|……S->β(ε|α|αα|ααα|……)S->βS’,S’->ε|α|αα|ααα|……S->βS’,S’->ε|αS’①

消除直接左遞歸:1414文法E->E+T|TT->T*F|FF->(E)|i例2已知G[E]：

E->T*F|T/F|F

T->F|T*F|T/F

解：左遞歸改為右遞歸得：

E->T*F|T/F|F

T->FT’T’->*FT’|/FT’|ε消除左遞歸后：E->TE’,E’->+TE’|εT->FT’,T’->*FT’|εF->(E)|i1515②消除一般左遞歸基本思想先用代入法把間接左遞歸變成直接左遞歸，再消除直接左遞歸，最后去掉多余規(guī)則以化簡(jiǎn)文法。算法說(shuō)明要求文法不能含有回路(即形如P+

P的推導(dǎo))，并且不含作為規(guī)則的右部。1616算法描述消除所有左遞歸的算法1.把G的非終結(jié)符整理成某種順序A1，A2，……An

，使得：

A1::=δ1|δ2|……δkA2::=A1r……A3::=A2u|

A1v…..…….2.Fori:=1tondobeginforj:=1toi-1do

把每個(gè)形如Ai→Ajr的規(guī)則替換成

Ai→(δ1|δ2|……δk)r

其中Aj→δ1|δ2|……δk是當(dāng)前全部Aj

的規(guī)則消除Ai規(guī)則中的直接左遞歸

end3.化簡(jiǎn)由2得到的文法即可。間接左遞歸直接左遞歸消除直接左遞歸一般左遞歸也可以通過(guò)改寫法予以消除。1717例：文法G[s]為

S→Qc|cQ→Rb|bR→Sa|a非終結(jié)符順序重新排列R→Sa|aQ→Rb|bS→Qc|c該文法是無(wú)直接左遞歸，但有間接左遞歸

SQcRbcSabc∴SSabc+1.檢查規(guī)則R是否存在直接左遞歸R→Sa|a2.把R代入Q的有關(guān)選擇，改寫規(guī)則QQ→Sab|ab|b3.檢查Q是否直接左遞歸4.把Q代入S的右部選擇S→Sabc|abc|bc|c5.消除S的直接左遞歸S→(abc|bc|c)S’S’→abcS’|ε最后得到文法為:S→(abc|bc|c)S’S’→abcS’|εQ→Sab|ab|bR→Sa|a1818最后得到的文法:S→(abc|bc|c)S’S’→abcS’|εQ→Sab|ab|bR→Sa|a可以看出其中關(guān)于Q和R的規(guī)則是多余的規(guī)則∴經(jīng)過(guò)壓縮后S→(abc|bc|c)S’S’→abcS’|ε可以證明改寫前后的文法是等價(jià)的應(yīng)該指出,由于對(duì)非終結(jié)符的排序不同,最后得到的文法在形式上可能是不一樣的,但是不難證明它們的等價(jià).2．回溯問(wèn)題1919什么是回溯?分析工作要部分地或全部地退回去重做叫回溯造成回溯的條件：

文法中，對(duì)于某個(gè)非終結(jié)符號(hào)的規(guī)則其右部有多個(gè)選擇，并根據(jù)所面臨的輸入符號(hào)不能準(zhǔn)確的確定所要選擇時(shí)，就可能出現(xiàn)回溯。回溯帶來(lái)的問(wèn)題：嚴(yán)重的效率低，只有在理論上的意義而無(wú)實(shí)際意義U::=

1|

2|

3

2020效率低的原因1)語(yǔ)法分析要重做2)語(yǔ)法處理工作要推倒重來(lái)為避免回溯，對(duì)文法的要求是FIRST(αi)∩FIRST(αj)=φ(ij)非終結(jié)符的候選式的首符集兩兩不相交[定義]

設(shè)文法G（不具左遞歸性）

FIRST(α)={a|α

aβ，aVt，α,βV*}

若α

ε，則規(guī)定εFIRST(α)

符號(hào)串α的所有可能推導(dǎo)出的開頭終結(jié)符或ε**2121例子設(shè)有文法G[S]:S->Aa|BbA->d|cAB->b|aB對(duì)S:FIRST(Aa)={d,c},FIRST(Bb)={a,b},FIRST(Aa)∩FIRST(Bb)=φ對(duì)A:FIRST(d)=1dnpp3r,FIRST(cA)={c},FIRST(d)∩FIRST(cA)=φ對(duì)B:FIRST(b)=,FIRST(aB)={a},FIRST(b)∩FIRST(aB)=φ若給定w=abb則自頂而下分析對(duì)應(yīng)的推導(dǎo)為:S=>Bb=>aBb=>abb2222消除回溯的途徑：改寫文法對(duì)具有多個(gè)右部的規(guī)則反復(fù)提取左因子例U→xV|xWU,V,W∈Vn,x∈Vt改寫為U→x(V|W)更清楚表示

U→xZZ→V|W注意：?jiǎn)栴}到此并沒有結(jié)束，還需要進(jìn)一步檢查V和W的首符號(hào)是否相交若V∷=ab|cdFIRST(V)={a,c}W∷=de|fgFIRST(W)={d,f}只要不相交就可以根據(jù)輸入符號(hào)確定目標(biāo)，若相交，則要代入，并再次提取左因子。如：V::=abw::=ac

則：Z::=a(b|c)5.1.3遞歸子程序法（遞歸下降分析法）遞歸下降分析法也稱遞歸子程序法，是一種直觀易于構(gòu)造的自頂向下分析方法。分析過(guò)程則通過(guò)自上而下一級(jí)一級(jí)地調(diào)用子程序來(lái)實(shí)現(xiàn)，所以稱為遞歸下降分析法。思想對(duì)文法中的每個(gè)非終結(jié)符編寫一個(gè)處理子程序，處理子程序的代碼結(jié)構(gòu)由相應(yīng)的非終結(jié)符的規(guī)則右部來(lái)決定：規(guī)則右部的終結(jié)符號(hào)與輸入符號(hào)相匹配，非終結(jié)符與相應(yīng)的子程序調(diào)用相對(duì)應(yīng)，非終結(jié)符對(duì)應(yīng)的各個(gè)候選式與分支結(jié)構(gòu)相對(duì)應(yīng)。限制：對(duì)文法要求高，必須滿足LL(1)文法；由于遞歸調(diào)用多，速度慢，占用空間多。盡管這樣,它還是許多高級(jí)語(yǔ)言的編譯系統(tǒng)經(jīng)常采用的語(yǔ)法分析方法。擴(kuò)展的巴科斯范式(EBNF)EBNF是在BNF基礎(chǔ)上擴(kuò)展如下三組符號(hào)：“{}”：表示花括號(hào)內(nèi)的語(yǔ)法成分可以重復(fù)；“[]”：表示方括號(hào)內(nèi)的成分是可選項(xiàng)；“()”：表示括號(hào)內(nèi)的成分優(yōu)先。用EBNF改寫文法對(duì)于非終結(jié)符A的一組形如Ax|y||z|Aa的規(guī)則，可表示成A(x|y||z){a}。例如，對(duì)于規(guī)則EE+T|T，可以寫成ET{+T}。例設(shè)有文法G[E]：

EE+T|E-T|TTT*F|T/F|FFPF|PP(E)|i用EBNF表示消除左遞歸得到文法G[E]：

ET{(+|-)T}TF{(*|/)F}

FP{P}P(E)|i

T->FT’

T’->*FT’|/FT’|ε遞歸子程序E的遞歸子程序E(){T();while(w==“+”||w==“-”){get_w();T();}}T的遞歸子程序T(){F();while(w==“*”||w==“/”){get_w();F();}}F的遞歸子程序F(){P();while(w==“”){get_w();P();}}P的遞歸子程序P(){if(w==“(”){get_w();E();if(w==“)”)get_w();elseerror();}elseif(w==“i”)get_w();elseerror();}另一個(gè)例子對(duì)于文法G[E]：

EE+T|TTT*F|FF(E)|i經(jīng)消除左遞歸后得到G[E]：

ETEE+TE|TFTT*FT|F(E)|iE的遞歸子程序E(){T();E();}E的遞歸子程序E(){if(w==“+”){get_w();T();E();}}T的遞歸子程序T(){F();T();}T的遞歸子程序T(){if(w==“*”){get_w();F();T();}}F的遞歸子程序F(){if(w==“(”){get_w();E();if(w==“)”)get_w();elseerror();}elseif(w==“i”)get_w();elseerror();}5.1.4LL(1)分析法3636LL－自左向右掃描輸入串。分析過(guò)程表現(xiàn)為最左推導(dǎo)的性質(zhì)。每步推導(dǎo)只需向前查看一個(gè)符號(hào)。一種自頂向下分析方法通常把按LL(1)方法完成語(yǔ)法分析任務(wù)的程序叫LL(1)分析程序或者LL(1)分析器。此過(guò)程有三部分組成:分析表執(zhí)行程序(總控程序）符號(hào)棧（分析棧）#執(zhí)行程序分析表#符號(hào)棧輸入串在實(shí)際語(yǔ)言中，每一種語(yǔ)法成分都有確定的左右界符，為了研究問(wèn)題方便，統(tǒng)一以‘?！硎?。1、LL分析程序構(gòu)造及分析過(guò)程3737M[A,a]=A→αi

表示當(dāng)要用A去匹配輸入串時(shí)，且當(dāng)前輸入符號(hào)為a時(shí)，可用A的第i個(gè)選擇去匹配。即當(dāng)αi≠ε時(shí)，有αia…;

當(dāng)αi＝ε時(shí)，則a為A的后繼符號(hào)。*M[A,a]=error

表示當(dāng)用A去匹配輸入串時(shí)，若當(dāng)前輸入符號(hào)為a，則不能匹配，表示無(wú)Aa…,或a不是A的后繼符號(hào).*（1）分析表：二維矩陣MA→αiαi∈V*M[A,a]=或A∈Vnerrora∈Vtor#（2）符號(hào)棧:用于存放分析過(guò)程中的文法符號(hào)。分析棧初始化時(shí)，在棧底壓入一個(gè)”#”，然后再壓入文法開始符號(hào)。（2）符號(hào)棧:有四種情況#E符號(hào)棧

開始狀態(tài)E#xxxxxx#

工作狀態(tài)#…..X符號(hào)棧X….#a……#查分析表得：X∈Vn,M[X,a]=X∷=αiX

a…X∈Vt,X=a+XX::=iaXerrora

出錯(cuò)狀態(tài)#…..X符號(hào)棧X….#a……#查分析表得：X∈Vn,M[X,a]=error

無(wú)X

a…X∈Vt,Xa+

結(jié)束狀態(tài)#符號(hào)棧##4141執(zhí)行程序主要實(shí)現(xiàn)如下操作:1.分析開始時(shí)候進(jìn)行有關(guān)的初始化工作。把#和文法識(shí)別符號(hào)E推進(jìn)棧,并讀入輸入串的第一個(gè)符a,重復(fù)下述過(guò)程直到正常結(jié)束或出錯(cuò).2.設(shè)分析到的某一步，分析棧當(dāng)前的棧頂符號(hào)X和當(dāng)前輸入符號(hào)a,執(zhí)行如下操作:若X∈VT:(1)若X=a=#，分析成功，停止。E匹配輸入串成功.(2)若X=a≠#，則從棧頂彈出X，輸入串的分析指針指向下一個(gè)輸入符號(hào)。(3)若X≠a，則表示發(fā)現(xiàn)錯(cuò)誤，調(diào)相應(yīng)的出錯(cuò)處理程序（3）執(zhí)行程序:據(jù)分析表和分析?？刂茖?duì)輸入符號(hào)串的分析和識(shí)別#…..X符號(hào)棧X….#a……#4242

若X∈Vn，查分析表M，根據(jù)M[X,a]的內(nèi)容決定：

a)

若M[X,a]中為一個(gè)規(guī)則，則將X彈出棧，并將此規(guī)則右部的符號(hào)序列按倒序壓入分析棧。

注：U在棧頂（最左推導(dǎo)）

b)若M[X,a]為空，則表示出錯(cuò)，調(diào)出相應(yīng)的出錯(cuò)處理程序。

3、反復(fù)執(zhí)行2）。4343分析表注：矩陣元素空白表示Error例：文法G[E] E::=E+T|T T::=T*F|F F::=(E)|i請(qǐng)用自頂向下的方法分析是否字符串i+i*i∈L(G[E])。E::=TE’E’::=+TE’|εT::=FT’T’::=*FT’|εF::=(E)|i消除左遞歸i+*()#EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→(E)4444輸入串為:i+i*i#步驟 符號(hào)棧 讀入符號(hào) 剩余符號(hào)串 使用規(guī)則1.＃EE# i +i*i# 2.＃E’T TE’# i +i*i# E::=TE’3.＃E’T’FFT’E’#i +i*i# T::=FT’4.＃E’T’iiT’E’# i +i*i# F::=i5.＃E’T’T’E’# + i*i#(出棧，讀下一個(gè)符號(hào)）6.＃E’ E’#

＋ i*i# T::=ε

7.＃E’T++TE’#

＋ i*i# E::=+TE’4545步驟 符號(hào)棧 讀入符號(hào) 剩余符號(hào)串 使用規(guī)則8. ＃E’T i *i# 9. ＃E’T’F i *i# T::=FT’10. ＃E’T’i i *i# F::=i11. ＃E’T’ * i# 12. ＃E’T’F* * i# T’::=*FT’13. ＃E’T’F i # 14. ＃E’T’i i # F::=i15. ＃E’T’ # 16. ＃E’ # T’::=ε

17. ＃ # E’::=ε

輸入串為:i+i*i#4646推導(dǎo)過(guò)程：

E

TE'

FT'E'iT'E'iE'

i+TE'i+FT'E'i+iT'E'

i+i*FT'E'i+i*iT'E'

i+i*iE'i+i*i最左推導(dǎo)。E::=TE’E::=+TE’|εT::=FT’T’::=*FT’|εF::=(E)|i2、分析表的構(gòu)造：LL(1)分析器構(gòu)造的核心。定義：FIRST(α)={a|α

aβ，aVt，α,βV*}

若α

ε，則規(guī)定εFIRST(α)該集合稱為α的頭符號(hào)集合**設(shè)有文法G[Z]:4747定義：

A∈VnFOLLOW(A)={a|ZμAβ且a∈Vt,a∈FIRST(β),μ∈Vt*,β∈V+}若ZμAβ,且β

ε，則#FOLLOW(A)該集合稱為A的后繼符號(hào)集合或定義為：FOLLOW(A)={a|Z…Aa…，a∈Vt}A∈Vn,Z識(shí)別符號(hào)特殊地：若Z...A則#∈FOLLOW(A)*****4848設(shè)α=X1X2...Xn,Xi∈VnVt求FIRST(α)=?

首先求出組成α的每一個(gè)符號(hào)Xi的FIRST集合若Xi∈Vt，則FIRST(Xi)={Xi}(2)若Xi∈Vn且Xi→a…..|ε，a∈Vt

則FIRST(Xi)={a，ε}(Ⅰ)集合FIRST的算法4949(3)若Xi∈Vn且Xi→y1y2…yk，則按如下順序計(jì)算FIRST(Xi)

若FIRST(Xi)

FIRST(y1)–{ε}；若ε∈FIRST(y1)則將FIRST(y2)-{ε}加入FIRST(Xi)；若ε∈FIRST(y1)ε∈FIRST(y2)則將FIRST(y3)-{ε}加入FIRST(Xi)........

若ε∈FIRST(yk-1)則將FIRST(yk)-{ε}加入FIRST(Xi)

若ε∈FIRST(y1)～FIRST(yk)

則將ε加入FIRST(Xi)

注意：要順序往下做，一旦不滿足條件，過(guò)程就要中斷進(jìn)行

得到FIRST(Xi)，即可求出FIRST(α)。5050(Ⅱ)構(gòu)造集合FOLLOW的算法若S為識(shí)別符號(hào),則把“#”加入FOLLOW(S)中(2)若A→αBβ(β≠ε),則把FIRST(β)-{ε}加入FOLLOW(B)(3)若A→αB或A→αBβ，且βε則把FOLLOW(A)加入FOLLOW(B)*注：FOLLOW集合中不能有ε設(shè)S,A,B∈Vn,算法：連續(xù)使用以下規(guī)則，直至FOLLOW集合不再擴(kuò)大5151定義：給定上下文無(wú)關(guān)文法A→α，A∈Vn，αV*若α

ε，SELECT(A→α)=FIRST(α)若α

ε，SELECT(A→α)=FIRST(α)∪FOLLOW(A)**注：

SELECT集合中不能有ε由定義可見，SELECT(Ax)實(shí)際上是指在推導(dǎo)過(guò)程中，若采用規(guī)則Ax進(jìn)行推導(dǎo)時(shí)，可能推導(dǎo)出的下一個(gè)終結(jié)符號(hào)組成的集合。5252(Ⅲ)構(gòu)造分析表基本思想是:當(dāng)文法中某一非終結(jié)符呈現(xiàn)在棧頂時(shí),根據(jù)當(dāng)前的輸入符號(hào),分析表應(yīng)指示要用該非終結(jié)符里的哪一條規(guī)則取匹配輸入串(即進(jìn)行下一步最左推導(dǎo))

根據(jù)這個(gè)思想,我們不難把構(gòu)造分析表算法構(gòu)造出來(lái)!終結(jié)符號(hào)非終結(jié)符號(hào)算法：設(shè)A→αi為文法中的任意一條規(guī)則，a為任一終結(jié)符或#。所謂構(gòu)造分析表M就是定義M的各個(gè)元素，若已經(jīng)對(duì)文法中的每一條規(guī)則都求出SELECT集，則分析表的構(gòu)造算法為：1、若a∈SELECT（A→αi），則M[A,a]=A→αi

2、M中不能由1)定義的元素都是空白元素。或者理解為：1、若a∈FIRST（αi

），則A::=αi==>M[A,a]

表示：A在棧頂，輸入符號(hào)是a，應(yīng)選擇αi

去匹配2、若αi=ε或αi

ε,而且a∈FOLLOW（s），則A::=αi==>M[A,a]，表示A已經(jīng)匹配輸入串成功，其后繼符號(hào)終結(jié)符a由A后面的語(yǔ)法成分去匹配。3、把所有無(wú)定義的M[A,a]都標(biāo)上error5353+5454解：1）求FIRST：FIRST(F)={(，i}FIRST(T’)={*,ε}FIRST(T)=FIRST(F)-{ε}={(，i}FIRST(E’)={+,ε}FIRST(E)=FIRST(T)-{ε}={(，i}∴FIRST(TE’)=FIRST(T)-{ε}={(，i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)=FIRST(F)-{ε}={(，i}FIRST(（E）)={(}FIRST(i)={i}例：G[E]分析表的構(gòu)造

E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i構(gòu)造過(guò)程：1）求FIRST：2）求FOLLOW3）構(gòu)造分析表5555E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW(E)={#,)}∵因?yàn)镋是識(shí)別符號(hào)∴#∈FOLLOW(E)

又F→(E)∴)∈FOLLOW(E)FOLLOW(E’)={#,)}

∵E→TE’∴FOLLOW(E)加入FOLLOW(E’)FOLLOW(T)={+,),#}

∵E’→+TE’∴FIRST(E’)-{ε}加入FOLLOW(T)

又E’ε，∴FOLLOW(E’)加入FOLLOW(T)FOLLOW(T’)=FOLLOW(T)={+,),#}

∵T→FT’∴FOLLOW(T)加入FOLLOW(T’)FOLLOW(F)={*,+,),#}

∵T→FT’∴FOLLOW(F)=FIRST（T’）-{ε}*又T’ε∴FOLLOW(T)加入FOLLOW(F)2）求FOLLOWFIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}5656E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i求SELECTFIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}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}FOLLOW(F)={*,+,),#}FOLLOW(T’)={+,),#}FOLLOW(T)={+,),#}FOLLOW(E’)={#,)}FOLLOW(E)={#,)}5757E’→εT’→εi+*()#EE’TT’FE→TE’E→TE’E’→+TE’E’→εT→FT’T→FT’T’→εT’→*FT’T’→εF→iF→(E)注意:用上述算法可以構(gòu)造出任意給定文法的分析表,但不是所有文法都能構(gòu)造出上述那種形狀的分析表即M[A,a]=一條的規(guī)則或Error。對(duì)于能用上述算法構(gòu)造分析表的文法我們稱為L(zhǎng)L(1)文法3）構(gòu)造分析表FIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)=={(,i}FIRST(E’)={+,ε}FIRST(E)=={(,i}E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW(E)={#,)}FOLLOW(E’)={#,)}FOLLOW(T)={+,),#}FOLLOW(T’)={+,),#}FOLLOW(F)={*,+,),#}58582、若β==>ε,則FIRST(α)∩FOLLOW(A)=Ф*3、LL(1)文法定義：一個(gè)文法G，其分析表M不含多重定義入口(即分析表中無(wú)二條以上規(guī)則)，則稱它是一個(gè)LL(1)文法.定理：文法G是LL(1)文法的充分必要條件是：對(duì)于G的每一個(gè)非終結(jié)符A的任意兩條規(guī)則A::=α|β,下列條件成立：1、FIRST(α)∩FIRST(β)=ФSELECT(A→α)∩SELECT(A→β)=Ф或LL(1)文法及LL(1)語(yǔ)言的性質(zhì)任何LL(1)文法都是無(wú)二義性的；若一文法中的非終結(jié)符含有左遞歸，則它必然是非LL(1)文法；非LL(1)語(yǔ)言是存在的；存在一種算法，它能判定任一文法是否為L(zhǎng)L(1)文法；不存在這樣的算法，它能判定上下文無(wú)關(guān)語(yǔ)言能否由LL(1)文法產(chǎn)生。6060解：1）求FIRST：FIRST(F)={(，i}FIRST(T’)={*,ε}FIRST(T)=FIRST(F)-{ε}={(，i}FIRST(E’)={+,ε}FIRST(E)=FIRST(T)-{ε}={(，i}∴FIRST(TE’)=FIRST(T)-{ε}={(，i}FIRST(+TE’)={+}FIRST(ε)={ε}FIRST(FT’)=FIRST(F)-{ε}={(，i}FIRST(（E）)={(}FIRST(i)={i}例：G[E]:E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i構(gòu)造過(guò)程：1）求FIRST：6161E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW(E)={#,)}∵因?yàn)镋是識(shí)別符號(hào)∴#∈FOLLOW(E)

又F→(E)∴)∈FOLLOW(E)FOLLOW(E’)={#,)}

∵E→TE’∴FOL