工學(xué)第4章編譯原理課件

1、第4章 語法分析自上而下分析 4.1 語法分析器的功能 4.2 自上而下分析面臨的問題 4.3 LL（1）分析法4.4 遞歸下降分析程序構(gòu)造4.5 預(yù)測分析程序第4章 語法分析自上而下分析 內(nèi)容回顧句型、句子和語言的定義句型有文法GS，若S =*，且*, 則稱是是文法G的一個句型句子有文法GS，若S =*，且T* , 則稱是是文法G的一個句子語言由文法 G 產(chǎn)生的所有句子的集合 L(G)=|S=+,且T*內(nèi)容回顧 最左(最右)推導(dǎo)在推導(dǎo)的任何一步=*(其中和是句型)， 都對中的最左(最右)非終結(jié)符進(jìn)行替換句型分析(句子分析)識別一個符號串是否為某文法的句型(句子)的過程也就是某文法的某個推導(dǎo)的

2、構(gòu)造過程設(shè)文法G為: E E+T|T T T*F|F F (E)|i 請問符號串i+i*i是 否為該文法的句子? 自上 而下自下而上EE + TT * FFFTiii內(nèi)容回顧 術(shù)語解釋分析算法(分析器、識別算法)在語言的編譯實(shí)現(xiàn)中，把完成句型(句 子)分析的程序稱為分析程序或識別程序從左到右的分析算法即總是從左到右地識別輸入符號串，首 先識別符號串中的最左符號，進(jìn)而依次 識別右邊的一個符號內(nèi)容回顧 4.1語法分析器的功能任務(wù)分析并判定輸入的單詞符 號串是否符合該語言的語 法規(guī)則(上下文無關(guān)文法)實(shí)質(zhì)就是按照文法的產(chǎn)生式， 識別輸入符號串是否為一 個句子(合法程序，語句， 表達(dá)式等)詞法掃描器語

3、法分析器語義處理單詞符號語法樹4.1語法分析的功能 設(shè)計思想判斷是否能從文法的開始符號出發(fā)推導(dǎo)出這個輸入串或者,判斷能否建立一棵與輸入串匹配的語法分析樹輸入 單詞符號串輸出 語法分析樹格式化的程序合法的表達(dá)式、語句、函數(shù)出錯處理要求盡快發(fā)現(xiàn)錯誤，準(zhǔn)確定位可能時進(jìn)行恢復(fù)處理，繼續(xù)語法分析4.1語法分析的功能 根據(jù)建立方法，語法分析算法可分為兩大類:自上而下分析法從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式向 下推導(dǎo)，尋找與輸入符號串匹配的推導(dǎo)自下而上分析法從輸入串開始，逐步進(jìn)行歸約，直至歸約到文法 的開始符號兩種方法反映了兩種不同的語法樹的構(gòu)造過程自上而下從樹根推導(dǎo)到樹葉自下而上從樹葉歸約到樹根4.

4、1語法分析的功能 4.2 自上而下分析面臨的問題基本方法對任何輸入串,試圖從文法的開始符號出發(fā)， 自上而下地為輸入串建立一棵語法樹或者說，為輸入串尋找一個最左推導(dǎo)過程本質(zhì)是一種試探過程，是反復(fù)使用不同產(chǎn)生式 謀求匹配輸入串的過程如何選擇哪個產(chǎn)生式進(jìn)行推導(dǎo)?4.2自上而下分析面臨的問題 例 文法GS SxAy Aab|a 判斷輸入串 w = x a y是否為該文法的句子？SxAy試探ab失敗回溯a試探成功分析結(jié)束SxAy=xay=問題產(chǎn)生回溯的原因是什么?4.2自上而下分析面臨的問題 公共左因子產(chǎn)生回溯例 文法G: S xAy A ab|a無法確定非終結(jié)符A面臨輸入符 號a時選用哪個關(guān)于A的候選

5、式 左遞歸無限循環(huán)例 文法G: S Sa|abaw = abaaaSSaSa無法確定何時用Saba產(chǎn)生式 進(jìn)行推導(dǎo)某些文法導(dǎo)致自上而下分析具有不確定性4.2自上而下分析面臨的問題 4.3 LL(1)分析法為了構(gòu)造不帶回溯的自上而下分析算法消除文法的左遞歸消除回溯、提取左因子LL(1)分析條件LL(1)文法4.3 LL（1）分析法 4.3.1 左遞歸的消除關(guān)于非終結(jié)符P的規(guī)則直接左遞歸定義：若P P 、 *例如 E E + TT（含有E的左遞歸） T T * FF（含有T的左遞歸） F ( E )i 4.3 LL（1）分析法 間接左遞歸定義： 若P =+ P *例如 間接左遞歸 S Aa A S

6、b|b S =Aa=Sba 即S=+Sb用S的產(chǎn)生式右部替換A右部的S得： A Aab|b 變成A的產(chǎn)生式含有直接左遞歸4.3 LL（1）分析法 消除直接左遞歸的方法改寫為等價的右遞歸 形如：P P 非，不以P開始 改寫為：PP（P為新增加的非終結(jié)符） PP改寫前產(chǎn)生式可產(chǎn)生短語 P=P= 改寫后產(chǎn)生式可產(chǎn)生短語 P= P = P = 等價4.3 LL（1）分析法 E E + TTT T * FFF ( E )iE T EE + T ET F TT * F TF ( E )i4.3 LL（1）分析法 消除多個直接左遞歸若有多個左遞歸的產(chǎn)生式如：PP1| P2 | Pm |1| 2 |n消除左遞

7、歸后變?yōu)椋?P1P |2 P|nP P 1P | 2 P| mP| 消除左遞歸要求文法： 1.無回路（A =* A） 2.無空產(chǎn)生式（A ）4.3 LL（1）分析法 練習(xí)例如有文法：KKa | Kb| Kc | d | e 消除左遞歸后變?yōu)椋?K dK |eK K aK | bK| cK|4.3 LL（1）分析法 間接左遞歸消除舉例 S Qcc Q Rbb R SaaS=Qc=Rbc=Sabc 是間接左遞歸消除方法1：將非終結(jié)符排序： R Q S將R的右部代入Q，S：Q Sababb S Qcc （不變）將Q的右部代入S：S Sabcabcbcc消除S的直接左遞歸： S abcSbcS|cS

8、SabcS| Q Sabab|b R Saa整理化簡：刪除Q，R（無用）消除左遞歸后得： S abcSbcS|cS SabcS| 4.3 LL（1）分析法 S Qcc Q Rbb R Saa消除方法2：將非終結(jié)符排序： S Q R將S的右部代入Q，R：Q Rbb（不變） R Qcaca|a將Q的右部代入R： R Rbcabca|ca|a消除R的直接左遞歸： R bcaRcaR|aR RbcaR| 整理化簡：S，Q（有用）消除左遞歸后得： S Qcc Q Rbb R bcaRcaR|aR RbcaR| 4.3 LL（1）分析法 消除左遞歸算法1.以某種S順序?qū)⑽姆ǖ姆墙K結(jié)符排列 P1，P2，,P

9、n 2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj的規(guī)則改寫成 Pi1|2|k,其中 Pj1|2|是關(guān)于Pj的所有規(guī)則; 消除Pi的直接左遞歸 END3.化簡由2所得的文法，即去除那些從開始符號 出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生式當(dāng)非終結(jié)符的排列順序不 同時，變換后的文法形式 可能不同，但是它們都和 原文法是等價的 4.3 LL（1）分析法 4.3.2 消除回溯、提左因子消除回溯目的對文法的任何非終結(jié)符，當(dāng)它去匹配輸入串 時，能夠根據(jù)輸入符號，準(zhǔn)確地選擇合適的 候選式去匹配若需要非終結(jié)符A去匹配輸入串，A的候選式 為A1| 2 | n ，

10、 A所面臨的第一 個輸入符號為a時，A能準(zhǔn)確地選擇i去執(zhí)行 匹配任務(wù)，則無需回溯4.3 LL（1）分析法 提取公共左因子方法對于所有形如 A12.n的規(guī)則 其中，為左因子，不以開頭改寫為AA 其中A為新增加的非終結(jié)符 A12.n例如 S xAy A ab|a提左因子后變換為 S xAy A aA A b|4.3 LL（1）分析法 4.3.3 LL(1)分析條件FIRST集合的定義FOLLOW集合的定義LL(1)分析條件LL(1)文法的定義4.3 LL（1）分析法 FIRST()集合的定義設(shè)G=(T，N，S，P） * FIRST()=a|=* a ，aT若=*，則FIRST() FIRST()是

11、的所有可能推導(dǎo)的首遇 終結(jié)符號或，是選擇產(chǎn)生式的依據(jù)a E T E E + T ET F T T * F T F ( E )iFIRST(E) = (（E）=0（E） FIRST（TE） =（，iTE=FTE=（E）TETE=FTE=iTE4.3 LL（1）分析法 FOLLOW(A)集合的定義 A N FOLLOW(A)= aS=*Aa，aT 若S=*A，則#FOLLOW（A）#輸入串的結(jié)束符 也可看作是句子的括號 #S#FOLLOW(A)表示了句型中可能緊跟在A后面的終結(jié)符號SAaE T E E + T E T F T T * F T F ( E )i ） FOLLOW（E）S = TE =

12、 FTE =（E）TE + FOLLOW（T）S = TE = T+TE # FOLLOW（E）S =0 E 4.3 LL（1）分析法 消除回溯的條件非終結(jié)符A的所有候選首符集兩兩不相交， 即A的任何兩個不同候選和，滿足： FIRST() FIRST() = 當(dāng)要求 A 匹配輸入串時，A就能根據(jù)它所面 臨的第一個輸入符號 a，準(zhǔn)確地指派某一個 候選去執(zhí)行任務(wù)，這個候選就是那個終結(jié)首 符集含 a 的4.3 LL（1）分析法 非終結(jié)符A的自動匹配當(dāng)非終結(jié)符 A 面臨輸入符號a，但a不屬于A 的任何候選首符集，如果A有候選式A(A 的某個候選首符集包含)，可以讓A自動得 到匹配，即A匹配于空字，但輸

13、入符號不讀 進(jìn)要想讓A自動匹配成功，需要考察FOLLOW(A) 4.3 LL（1）分析法 i + i # 的推導(dǎo)過程設(shè)有文法GETE E+TE| TFT T*FT| F(E)|i iFIRST(i)+FIRST(+TE)+FOLLOW(T)#FOLLOW(E)#FOLLOW(T)ii生成語法分析樹4.3 LL（1）分析法 推導(dǎo)過程的分析輸入輸出輸入：符號串(有序的) 輸出：結(jié)構(gòu)化的符號串(樹結(jié)構(gòu))產(chǎn)生式的選擇根據(jù)當(dāng)前符號（單詞）語法分析樹的表示按照使用序列排列的產(chǎn)生式序列4.3 LL（1）分析法 無回溯的自上而下分析的文法的條件文法不含左遞歸對于文法的每個非終結(jié)符 A 的任何兩 個不同的產(chǎn)生式

14、 A|1) FIRST()FIRST() = 2) =*和=*不能同時成立3) 如果=*，則 FISRT(/A)FOLLOW(A)= 滿足以上條件的文法稱為LL(1)文法4.3 LL（1）分析法 LL(1)分析含義第一個 L 表示從左向右掃描輸入符號串第二個 L 表示生成最左推導(dǎo)1 表示讀入一個符號可確定下一步推導(dǎo)對于LL（1）文法，可以對輸入串進(jìn)行有效的無回溯的自上而下分析。對于文法G，當(dāng)面臨的輸入符號為a，要用非終結(jié)符A進(jìn)行匹配時，假設(shè)A的所有產(chǎn)生式為 A1| 2 | n1)若aFIRST(i )，則指派i去執(zhí)行任務(wù)2)若a不屬于任何候選首符集，則： 若屬于某個FIRST(i )且 aFO

15、LLOW(A)，則讓A與自動匹配 否則，a的出現(xiàn)是一種語法錯誤4.3 LL（1）分析法 4.4 遞歸下降分析程序構(gòu)造不帶回溯的自上而下分析程序分析程序一組遞歸過程每個非終結(jié)符一個子過程LL（1）文法構(gòu)造分析程序從開始符號所對應(yīng)的過程開始運(yùn)行子過程的功能： 對相應(yīng)非終結(jié)符產(chǎn)生式右部進(jìn)行語法分析4.4 遞歸下降分析程序構(gòu)造 例 表達(dá)式文法的遞歸下降分析器消除左遞歸后的表達(dá)式文法G為：E TE E+TE| T FT T*FT| F (E)|i可以證明 G是一個LL（1）文法E( )E( )T( )T( )F( )5個非終結(jié)符構(gòu)造5個子過程4.4 遞歸下降分析程序構(gòu)造 遞歸下降分析器構(gòu)造說明C語言 E

16、（ ） T; E;ETE（1）E（）：完成對 E T E的右部分析PASCAL語言procedure E;begin T; E;end;右部有非終結(jié)符時，調(diào)用該非終結(jié)符對應(yīng)的子過程來完成E()if (c=+) p+; T; E; ETE（2）E（）：完成對 E +T E|的右部分析procedure E;if sym=+ then begin advance; T; E; end；+其它 非+字符 自動匹配advance：把輸入指針ip下移一位sym：當(dāng)前所面臨的輸入符號4.4 遞歸下降分析程序構(gòu)造 C語言練習(xí)T( ) F; T; (3)T(): T F Tprocedure T;begin

17、F; T;end;TFT4.4 遞歸下降分析程序構(gòu)造 (4)T(): T* F T|C語言練習(xí)T()if (c=*) p+; F; T; procedure T;if sym=* then begin advance; F; T; end；TF*其它 非*字符 自動匹配T4.4 遞歸下降分析程序構(gòu)造 (5)F(): F (E)|i procedure F; begin if sym=( then begin advance; E; if sym= ) then advance else error括號不匹配 end else if sym= i then advance else error

18、F面臨非（，i輸入符號，語法錯誤 endEF()i其它 非(,i字符出現(xiàn)語法錯誤4.4 遞歸下降分析程序構(gòu)造 的子程序F() if (c=() p+; E; if (c=) p+; else error; /*括號不匹配*/ else if (c=i) p+; else error;/*F面臨非(,i輸入符號， 語法錯誤*/ EF()i其它 非(,i字符出現(xiàn)法錯誤4.4 遞歸下降分析程序構(gòu)造 i+i的遞歸下降分析過程 ii生成語法分析樹i + i #匹配成功返回，指針下移自動匹配，返回自動匹配，返回自動匹配，返回匹配成功繼續(xù)，指針下移匹配成功返回，指針下移分析成功結(jié)束4.4 遞歸下降分析程序構(gòu)

19、造 遞歸下降分析程序優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：1）直觀、簡單、可讀性好2）便于擴(kuò)充缺點(diǎn)：1) 遞歸算法的實(shí)現(xiàn)效率低2) 處理能力相對有限3) 通用性差，難以自動生成4.4 遞歸下降分析程序構(gòu)造 遞歸下降分析程序課堂練習(xí)文法G為：S (T)|a+S|a T T,S|S 消除左遞歸：S (T)|a+S|a T ST T ，ST|提取左因子：S (T)|aS S +S| T ST T ，ST|4個子程序：S（） S（） T（） T（） BEGIN4.4 遞歸下降分析程序構(gòu)造 遞歸下降分析程序課堂練習(xí)答案（1）S (T)|aSS() if(c=() /*匹配第一候選式*/ p+; T; if(c=) p+; e

20、lse error; /*括號不匹配*/ else if(c=a) p+;S;/*匹配第二候選式*/ else error; /*語法錯誤*/4.4 遞歸下降分析程序構(gòu)造 (2)S+S| S() if(c=+) p+; S; (3)T STT()S; T;(4)T,ST|T()if(c=,) p+; S; T;4.4 遞歸下降分析程序構(gòu)造 4.5 預(yù)測分析程序?qū)崿F(xiàn)LL(1)分析的另一種有效方法使用一張二維分析表（預(yù)測分析表）和一個分析棧（文法符號棧）聯(lián)合進(jìn)行控制來實(shí)現(xiàn)自上而下分析技術(shù)4.5 預(yù)測分析程序 預(yù)測分析表說明預(yù)測分析表實(shí)際上是一個矩陣MA,aMA，a =A i當(dāng)A面臨a時所應(yīng)選用的候

21、選式空(error)A不可能與a匹配出現(xiàn)語法錯誤待匹配棧頂非終結(jié)符所面臨輸入符號4.5.1預(yù)測分析程序工作過程表達(dá)式文法的預(yù)測分析表ME，+ = E+T EE面臨+時選用E+T EMT，) = TT面臨）時選用T MF，* = errorF面臨*時出現(xiàn)語法錯誤分析棧的說明分析棧用于存放分析過程中的文法符號topstack棧頂指針分析棧初始化時：棧底壓入一個#底頂#Stoptop次棧底壓入文法開始符S入棧操作push出棧操作poptop 預(yù)測分析器模型 輸入緩沖區(qū): a# X # ?？偪刂瞥绦蝾A(yù)測分析表輸出所選用產(chǎn)生式序列查找4.5 預(yù)測分析程序 總控程序執(zhí)行時可能動作對于任何（X，a） X是棧

22、頂符號 a是面臨輸入符號(1) XT 且Xa#，分析成功結(jié)束，輸入串是 一個合法句子(2) XT 且Xa#，X出棧，輸入指針指向下一 輸入符號(3) XN ，查分析表MX，a 若MX，a=Xi，X出棧，i逆序入棧，輸入指針 不動 若MX，a=空，則調(diào)用error程序，進(jìn)行錯誤處理4.5 預(yù)測分析程序 執(zhí)行例子： i*i+i分析過程 棧 輸入緩沖區(qū) 所用產(chǎn)生式0 #E i*i+i# E TE ET入棧1 #ET i*i+i# T FT 2 #ETF i*i+i# F i3 #ETi i*i+i# i出棧，a下移4 #ET *i+i# T*FT 5 #ETF* *i+i# *出棧，a下移6 #ET

23、F i+i# F i 7 #ETi i+i# i出棧，a下移4.5 預(yù)測分析程序 i*i+i 分析過程續(xù) 棧 輸入緩沖區(qū) 所用產(chǎn)生式8 #ET +i# T 9 #E +i# E +TE10 #ET+ +i# 11 #ET i# T FT12 #ETF i# F i13 #ETi i# 14 #ET # T 15 #E # E 16 # # # = #分析成功結(jié)束輸出的產(chǎn)生式序列形成了按最左推導(dǎo)生成的語法分析樹4.5 預(yù)測分析程序 課堂練習(xí)一：i+i分析過程棧 輸入緩沖區(qū) 所用產(chǎn)生式0 #E i+i# E TE1 #ET i+i# T FT2 #ETF i+i# F i 3 #ETi i+i#

24、4 #ET +i# T 5 #E +i# E +TE6 #ET+ +i# 7 #ET i# T FT 4.5 預(yù)測分析程序 i+i 分析過程續(xù)棧 輸入緩沖區(qū) 所用產(chǎn)生式8 #ETF i# F i9 #ETi i# 10 #ET # T 11 #E # E 12 # # # = #分析成功4.5 預(yù)測分析程序 課堂練習(xí)二：i+i*i分析過程棧 輸入緩沖區(qū) 所用產(chǎn)生式0 #E i+i*i# E TE1 #ET i+i*i# T FT2 #ETF i+i*i# F i3 #ETi i+i*i# 4 #ET +i*i# T 5 #E +i*i# E +TE6 #ET+ +i*i#7 #ET i*i#

25、T FT 4.5 預(yù)測分析程序 i+i*i 分析過程續(xù)棧 輸入緩沖區(qū) 所用產(chǎn)生式8 #ETF i*i# F i 9 #ETi i*i# 10 #ET *i# T *FT11 #ETF* *i# 12 #ETF i# F i13 #ETi i# 14 #ET # T 15 #E # E 16 # #4.5 預(yù)測分析程序 總控程序?qū)崿F(xiàn)算法描述BEGIN PUSH(STACK,#)；PUSH(STACK,開始符號); a=第一個輸入符號； FLAG:=TRUE； WHILE FLAG DO BEGIN X=POP(STACK); IF XT THEN IF X=a THEN a=下一個符號 終結(jié)符匹

26、配 ELSE ERROR與當(dāng)前輸入符號不匹配 4.5 預(yù)測分析程序 ELSE IF X=# THEN IF X=a FLAG:=FALSE ELSE ERRORX=a=# 分析成功結(jié)束ELSE IF MA，a = X X1 X2Xk 把 XkX2 X1一一推進(jìn)STACK棧 ELSE ERROREND OF WHILESTOP 分析成功,過程完畢END4.5 預(yù)測分析程序 4.5.2 預(yù)測分析表的構(gòu)造設(shè)有文法G，預(yù)測分析表構(gòu)造過程：計算所有候選式的首符集 FIRST（）計算所有非終結(jié)符A的后繼符集 FOLLOW（A）構(gòu)造預(yù)測分析表 M4.5 預(yù)測分析程序 FIRST()的計算法FIRST()=

27、a =* a ，aT 若 =*，則 FIRST() 計算文法符號X的FIRST（X）計算文法符號串=X1X2Xn的FIRST()4.5 預(yù)測分析程序 FIRST( X )的計算法重復(fù)以下計算，直到FIRST（X）不再增大為止：1) 若 XT，則 FIRST( X ) = X 。 例 FIRST（+）=+ FIRST（i）=i2) 若 XN，若有Xa，則將 a 加入FIRST(X)； 例 E+TE +FIRST（E） F（E）|i （，iFIRST（F）若有X ，則將加入FIRST( X )。 例 E FIRST（E）4.5 預(yù)測分析程序 若有X Y1Yi-1YiYk ，并對于某個i， 有1ji

28、-1，F(xiàn)IRST（Yj）， 即Y1 ，Yi-1=*， 則將所有FIRST( Yj )-FIRST( Yi )- 加入FIRST( X )中； -3)若有 X Y，且 Y N ， 則 FIRST(Y)-加入FIRST(X);例 F(E)|i FIRST(F)=（，iTFT FIRST(T)=FIRST(F)-=（，i若所有Y1,Yk=*，則將加入到 FIRST( X )。計算XY1Yi-1YiYk FIRST(X)集舉例若有文法G為： X Y1 Y2 Y3 Y4 Y5 Y1 a Y2 b Y3 c Y4 d Y5 efFIRST集Y1Y2Y3Y4Y5Xa，b，c，d，e，fa,b,c,d,e,f

29、 因?yàn)閅5=*， 所以FIRST（X）=*=*因?yàn)閅5=*， 所以FIRST（X）4.5 預(yù)測分析程序 計算表達(dá)式文法FIRST(X)集舉例文法G為：E T EE+ T ET F T T* F T F ( E )i先找以終結(jié)符開頭的產(chǎn)生式FIRST( F ) = ( ,i FIRST( E ) = + ，F(xiàn)IRST( T ) = * , 再找右部以非終結(jié)符開頭的產(chǎn)生式FIRST( T ) = FIRST( F )FIRST( E ) = FIRST( T )= ( ,i 4.5 預(yù)測分析程序 計算FIRST(X)集合課堂練習(xí)=a，c，d，q 文法G為：S ApBqA acA B dB先找以終結(jié)

30、符開頭的產(chǎn)生式FIRST(A)= a ,c FIRST(B)= d ,再找右部以非終結(jié)符開頭的產(chǎn)生式FIRST(S)= FIRST(A)-FIRST(B)-因?yàn)锽=FIRST(S),因?yàn)镾=*FIRST(q)4.5 預(yù)測分析程序 計算表達(dá)式文法候選式FIRST()集舉例候選式的FIRST集FIRST(TE)=FIRST(T)=(,iFIRST(+TE)=+FIRST(FT)=FIRST(F)=(,iFIRST(*FT)=*FIRST(E)=(FIRST(i)=iFIRST()=文法G為：ETE E+TE| TFT T*FT| F(E)|i非終結(jié)符的FIRST集FIRST(E)=(,iFIRST

31、(E)=+,FIRST(T)=(,iFIRST(T)=*, FIRST(F)=(,i4.5 預(yù)測分析程序 計算FIRST()集合課堂練習(xí)文法G為：S ApBq A acAB dB非終結(jié)符的FIRST集FIRST(S)=a,c,d,q FIRST(A)=a,cFIRST(B)=d, 候選式的FIRST集FIRST(Ap)=FIRST(A)=a,cFIRST(Bq)=FIRST(B)- FIRST(q) =d,qFIRST(a)=aFIRST(cA)=cFIRST(dB)=dFIRST()=4.5 預(yù)測分析程序 FOLLOW(A)的計算法FOLLOW(A)= aS=*Aa，aT 若S=*A，則#F

32、OLLOW（A）重復(fù)以下計算，直到每個FOLLOW(A)不再增大為止：1)將 # 加入到 FOLLOW( S )中 例 # FOLLOW( E )2)若AB, 則將FIRST()-加入FOLLOW(B) 例 ETE FIRST(E)-加入FOLLOW(T) TFT FIRST(T)-加入FOLLOW(F)4.5 預(yù)測分析程序 3) 若 A B ，或 A B， 且 =*，即 FIRST()，AB 則將FOLLOW(A)所有元素加入FOLLOW(B) 例 E T EFOLLOW(E)加入FOLLOW(E)E T EEFOLLOW(E)加入FOLLOW(T)T F TFOLLOW(T)加入FOLLO

33、W(T)T F TFOLLOW(T)加入FOLLOW(F)T4.5 預(yù)測分析程序 計算表達(dá)式文法的FOLLOW集舉例#FOLLOW（開始符號）對每個非終結(jié)符查看其在產(chǎn)生式右邊的出現(xiàn)G：ETE E+TE| TFT T*FT| F(E)|i#FOLLOW(E)=FIRST(E)-FOLLOW(T)FOLLOW(E)=+,),#FOLLOW(F)=FIRST(T)-FOLLOW(T)=*,+,),#FOLLOW(E)=),#FOLLOW(E)=FOLLOW(E)=),#FOLLOW(T)=FOLLOW(T)=+,),#相同不需處理計算FOLLOW(A)集合課堂練習(xí)文法G為：S ApBq A acAB

34、 dB非終結(jié)符的FIRST集FIRST(S)=a,c,d,q FIRST(A)=a,cFIRST(B)=d, 非終結(jié)符FOLLOW集FOLLOW(S)=#FOLLOW(A)=FIRST(p)- =pFOLLOW(B)=FIRST(q)- =q4.5 預(yù)測分析程序 表達(dá)式文法是 LL(1) 文法滿足條件（3）： E FIRST(+TE)=+ FOLLOW(E)=),# T FIRST(*FT)=* FOLLOW(T)=+,),# 文法G是LL（1）文法滿足條件（1）：已消除左遞歸滿足條件（2）：FIRST(+TE)=+ FIRST()= FIRST(*FT)=* FIRST()= FIRST(E)=( FIRST(i)=i 文法G：E TE E+TE | T FT T*FT | F (E)i預(yù)測分析表的構(gòu)造算法(4)把所有無定義的 MA,a標(biāo)上“出錯標(biāo)志”(1)對文法G的每個產(chǎn)生式 A，執(zhí)行(2)和(3)(2)對每個終結(jié)符aFIRST()， 把 A 填入 MA,a(3