byyl-ch4自頂向下語法分析方法

自動機、正則文法、正則表達式

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

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

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

左遞歸問題回溯問題

主要方法:

遞歸子程序法

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

句柄的識別問題主要方法:

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

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

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

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

·ZcAd完成一步推導ZcAd

檢查c-c匹配

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

A有兩個右部,選第一個

·cAdabZ完成進一步推導Aab

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

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

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

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

→S’

S’→S’|ε證明的關鍵步驟：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ī)則以化簡文法。算法說明要求文法不能含有回路(即形如P+

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

，使得：

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

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

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

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

其中Aj→δ1|δ2|……δk是當前全部Aj

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

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

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

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

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

1|

2|

3

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

設文法G（不具左遞歸性）

FIRST(α)={a|α

aβ，aVt，α,βV*}

若α

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

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

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

則：Z::=a(b|c)5.1.3遞歸子程序法（遞歸下降分析法）遞歸下降分析法也稱遞歸子程序法，是一種直觀易于構(gòu)造的自頂向下分析方法。分析過程則通過自上而下一級一級地調(diào)用子程序來實現(xiàn)，所以稱為遞歸下降分析法。思想對文法中的每個非終結(jié)符編寫一個處理子程序，處理子程序的代碼結(jié)構(gòu)由相應的非終結(jié)符的規(guī)則右部來決定：規(guī)則右部的終結(jié)符號與輸入符號相匹配，非終結(jié)符與相應的子程序調(diào)用相對應，非終結(jié)符對應的各個候選式與分支結(jié)構(gòu)相對應。限制：對文法要求高，必須滿足LL(1)文法；由于遞歸調(diào)用多，速度慢，占用空間多。盡管這樣,它還是許多高級語言的編譯系統(tǒng)經(jīng)常采用的語法分析方法。擴展的巴科斯范式(EBNF)EBNF是在BNF基礎上擴展如下三組符號：“{}”：表示花括號內(nèi)的語法成分可以重復；“[]”：表示方括號內(nèi)的成分是可選項；“()”：表示括號內(nèi)的成分優(yōu)先。用EBNF改寫文法對于非終結(jié)符A的一組形如Ax|y||z|Aa的規(guī)則，可表示成A(x|y||z){a}。例如，對于規(guī)則EE+T|T，可以寫成ET{+T}。例設有文法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[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－自左向右掃描輸入串。分析過程表現(xiàn)為最左推導的性質(zhì)。每步推導只需向前查看一個符號。一種自頂向下分析方法通常把按LL(1)方法完成語法分析任務的程序叫LL(1)分析程序或者LL(1)分析器。此過程有三部分組成:分析表執(zhí)行程序(總控程序）符號棧（分析棧）#執(zhí)行程序分析表#符號棧輸入串在實際語言中，每一種語法成分都有確定的左右界符，為了研究問題方便，統(tǒng)一以‘＃’表示。1、LL分析程序構(gòu)造及分析過程3737M[A,a]=A→αi

表示當要用A去匹配輸入串時，且當前輸入符號為a時，可用A的第i個選擇去匹配。即當αi≠ε時，有αia…;

當αi＝ε時，則a為A的后繼符號。*M[A,a]=error

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

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

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

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

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

無X

a…X∈Vt,Xa+

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

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

a)

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

注：U在棧頂（最左推導）

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

3、反復執(zhí)行2）。4343分析表注：矩陣元素空白表示Error例：文法G[E] E::=E+T|T T::=T*F|F F::=(E)|i請用自頂向下的方法分析是否字符串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#步驟 符號棧 讀入符號 剩余符號串 使用規(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#(出棧，讀下一個符號）6.＃E’ E’#

＋ i*i# T::=ε

7.＃E’T++TE’#

＋ i*i# E::=+TE’4545步驟 符號棧 讀入符號 剩余符號串 使用規(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推導過程：

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最左推導。E::=TE’E::=+TE’|εT::=FT’T’::=*FT’|εF::=(E)|i2、分析表的構(gòu)造：LL(1)分析器構(gòu)造的核心。定義：FIRST(α)={a|α

aβ，aVt，α,βV*}

若α

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

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

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

首先求出組成α的每一個符號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，則按如下順序計算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)

注意：要順序往下做，一旦不滿足條件，過程就要中斷進行

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

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

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

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

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

2、M中不能由1)定義的元素都是空白元素?；蛘呃斫鉃椋?、若a∈FIRST（αi

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

表示：A在棧頂，輸入符號是a，應選擇αi

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

ε,而且a∈FOLLOW（s），則A::=αi==>M[A,a]，表示A已經(jīng)匹配輸入串成功，其后繼符號終結(jié)符a由A后面的語法成分去匹配。3、把所有無定義的M[A,a]都標上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)造過程：1）求FIRST：2）求FOLLOW3）構(gòu)造分析表5555E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW(E)={#,)}∵因為E是識別符號∴#∈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。對于能用上述算法構(gòu)造分析表的文法我們稱為LL(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，其分析表M不含多重定義入口(即分析表中無二條以上規(guī)則)，則稱它是一個LL(1)文法.定理：文法G是LL(1)文法的充分必要條件是：對于G的每一個非終結(jié)符A的任意兩條規(guī)則A::=α|β,下列條件成立：1、FIRST(α)∩FIRST(β)=ФSELECT(A→α)∩SELECT(A→β)=Ф或LL(1)文法及LL(1)語言的性質(zhì)任何LL(1)文法都是無二義性的；若一文法中的非終結(jié)符含有左遞歸，則它必然是非LL(1)文法；非LL(1)語言是存在的；存在一種算法，它能判定任一文法是否為LL(1)文法；不存在這樣的算法，它能判定上下文無關語言能否由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)造過程：1）求FIRST：6161E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW(E)={#,)}∵因為E是識別符號∴#∈FOLLOW(E)

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

∵E→TE’∴FOL