編譯原理實(shí)踐及應(yīng)用課件自上而下語(yǔ)法分析公開(kāi)課一等獎(jiǎng)省優(yōu)質(zhì)課大賽獲獎(jiǎng)?wù)n件

自上而下語(yǔ)法分析方法第四章（1）本章要求主要內(nèi)容：語(yǔ)法分析任務(wù)和設(shè)計(jì)，自上而下語(yǔ)法分析方法及其相關(guān)概念，Sample語(yǔ)言語(yǔ)法分析程序設(shè)計(jì)重點(diǎn)掌握：語(yǔ)法分析任務(wù)和接口設(shè)計(jì)，自頂向下語(yǔ)法分析面臨問(wèn)題及處理方法，掌握First集和Follow集概念和求解方法，掌握LL(1)文法判定方法，能夠使用遞歸下降分析方法和預(yù)測(cè)分析方法實(shí)現(xiàn)編寫(xiě)語(yǔ)法分析器，并對(duì)一個(gè)輸入串進(jìn)行分析。高級(jí)語(yǔ)言語(yǔ)法結(jié)構(gòu)適適用上下文無(wú)關(guān)文法來(lái)描述，上下文無(wú)關(guān)文法是語(yǔ)法分析基礎(chǔ)。語(yǔ)法分析是編譯過(guò)程關(guān)鍵，其任務(wù)是在詞法分析識(shí)別出正確單詞符號(hào)串基礎(chǔ)上，分析并判定程序語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。4.1語(yǔ)法分析任務(wù)問(wèn)題：在上一章詞法分析中講解了怎樣判斷源程序中單詞正確性，并輸出了正確單詞符號(hào)。那么怎樣知道這些正確單詞是否能組成正確表示式、語(yǔ)句或程序呢？這就是語(yǔ)法分析任務(wù)。語(yǔ)法分析任務(wù)在詞法分析識(shí)別出正確單詞符號(hào)串基礎(chǔ)上，分析并判定程序語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。語(yǔ)法分析在編譯系統(tǒng)中所處位置語(yǔ)法分析器輸入Token序列：詞法分析輸出，是各個(gè)單詞都正確源程序變換形式，是一個(gè)有限序列語(yǔ)法分析器輸出分析樹(shù)：表示方法？見(jiàn)教材P89錯(cuò)誤處理信息：定位、繼續(xù)編譯4.2語(yǔ)法分析接口設(shè)計(jì)語(yǔ)法分析器功效按照語(yǔ)言語(yǔ)法組成規(guī)則,識(shí)別輸入符號(hào)串能否組成一個(gè)句子。這些規(guī)則是用文法產(chǎn)生式來(lái)定義。問(wèn)題對(duì)給定一個(gè)輸入串，怎樣判定它是不是一個(gè)句子？方法依據(jù)文法產(chǎn)生式規(guī)則，從開(kāi)始符號(hào)出發(fā)，看能否推導(dǎo)出與這個(gè)輸入串匹配句子。這就需要建立與輸入串匹配語(yǔ)法分析樹(shù)。G=({E},{i,+,*,(,)},P,E)

P：EE+EEE*E E(E) Ei解：使用最左推導(dǎo)：EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i例：判定輸入串(i+i)*i是否是下述文法句子？結(jié)論：能夠從開(kāi)始符號(hào)出發(fā)推導(dǎo)出給定輸入串，所以，是句子。慣用語(yǔ)法分析方法：自頂向下分析法：

從文法開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)(使用最左推導(dǎo))，盡可能使用各種產(chǎn)生式，推導(dǎo)出與輸入串匹配句子，從而建立語(yǔ)法樹(shù)。自底向上分析法：

從輸入符號(hào)串開(kāi)始，逐步進(jìn)行歸約(最右推導(dǎo)逆過(guò)程)，直至歸約到文法開(kāi)始符號(hào)，從而建立語(yǔ)法樹(shù)。詳細(xì)分類：自頂向下分析遞歸下降分析預(yù)測(cè)分析(LL)自底向上分析

算符優(yōu)先分析

LR分析4.3自頂向下語(yǔ)法分析及面臨問(wèn)題自上而下分析主要是：對(duì)任何輸入串，試圖用一切可能方法，從文法開(kāi)始符號(hào)出發(fā)，自上而下地為輸入串建立一個(gè)語(yǔ)法樹(shù)。從推導(dǎo)角度看，從開(kāi)始符號(hào)出發(fā)，使用最左推導(dǎo)，試圖推導(dǎo)出與輸入符號(hào)串相同句子。從語(yǔ)法樹(shù)角度看，從根節(jié)點(diǎn)出發(fā)，重復(fù)使用全部可能產(chǎn)生式，尋求輸入串匹配，試圖向下結(jié)構(gòu)一棵語(yǔ)法樹(shù)，其末端節(jié)點(diǎn)恰好與輸入符號(hào)串相同。需要重復(fù)試探。例1：設(shè)有文法

(1)SxAy (2)A**|*現(xiàn)有輸入串：x*y其分析過(guò)程如右：SxAy**失敗，需要退回，重新選取A侯選式，這時(shí)使得分析器動(dòng)作不穩(wěn)定思索：產(chǎn)生回溯原因？x*y輸入符號(hào)串：?jiǎn)栴}1：回溯(P67)真正原因是：文法產(chǎn)生式有問(wèn)題。左遞歸：文法中存在某個(gè)AVn，有AA。直接左遞歸：有產(chǎn)生式AA間接左遞歸：例2：設(shè)有文法G(E)：(1)EE+T|T(2)TT*F|F(3)F(E)|i現(xiàn)有輸入串i*i+i,分析過(guò)程是：EE+TE+TE+T…失敗：對(duì)左遞歸文法使用最左推導(dǎo)，出現(xiàn)死循環(huán)。思索：產(chǎn)生左遞歸原因？問(wèn)題2：左遞歸(P68)真正原因是：文法產(chǎn)生式有問(wèn)題。

結(jié)論1.左遞歸和回溯問(wèn)題產(chǎn)生直接與描述語(yǔ)言文法相關(guān)2.應(yīng)該改造文法，使其不含左遞歸和回溯，才能進(jìn)行確定自頂向下分析4.3問(wèn)題處理方法消除左遞歸消除回溯消除左遞歸1.直接左遞歸消除P69：假定產(chǎn)生式為：P→Pα|β，將其替換為形式等價(jià)產(chǎn)生式組：例2：文法EE+T|TTT*F|FF(E)|i消去左遞歸后為：TFT'T'*FT'|ε

P→βP'

P'→αP'｜εETE'E'+TE'|εF(E)|i普通而言，若產(chǎn)生式形式為： A→Aα1|Aα2|…|Aαn|β1|β2|…|βm

將其替換為：Aβ1B|β2B

|…|βmBBα1B|α2B

|…|αnB|ε練習(xí)消去文法G[S]左遞歸S(T)|a+S|aTT,S|SS(T)|a+S|aTST'T’,ST'|ε答案：例：給定間接左遞歸文法，請(qǐng)消除左遞歸(1)代入(2)消除直接左遞歸SQc|cQRb|bRSa|a解：第1步：為R、S、Q排序第2步：代入：將R代入Q,Q代入S，得到新文 法產(chǎn)生式組： RSa|a

Q

Sab|ab|b S

Sabc|abc|bc|c第3步：消去S直接左遞歸，得到S

abcS'|bcS'|cS'S'abcS'|ε2.間接左遞歸消除方法P69方法是:重復(fù)“提取公共左因子”，使得文法每個(gè)非終止符號(hào)各個(gè)候選式首終止符集兩兩不相交，來(lái)防止回溯。設(shè)產(chǎn)生式為：A→δα1|δα2|…|δαn

AδA'A'

α1|α2|…|αn替換為：消除回溯例3：有以下兩個(gè)產(chǎn)生式：<IF語(yǔ)句>ifEthenS1elseS2;<IF語(yǔ)句>ifEthenS1;

提取左因子后：<IF語(yǔ)句>ifEthenS1B;BelseS2|ε;練習(xí)提取下述文法左因子S(T)|a+S|aTST'T’,ST'|εS(T)|aS'S’+S|εTST’T’,ST'|S答案:問(wèn)題:假如希望沒(méi)有回溯，對(duì)文法有什么要求？回溯產(chǎn)生真正原因是：某非終止符對(duì)應(yīng)多個(gè)侯選式，它們右部第一個(gè)終止符相同，從而造成語(yǔ)法分析器選擇了錯(cuò)誤侯選式。假如希望沒(méi)有回溯，對(duì)文法有什么要求？對(duì)不含左遞歸文法G，對(duì)某非終止符侯選式：

First(α)={a|αa…,a∈VT}若αε，則ε∈First(α)**侯選式首終止符集定義即，由該候選式推導(dǎo)出全部符號(hào)串中第一個(gè)終止符集合。4.3LL(1)文法例：對(duì)右邊文法G，每個(gè)候選式First集為：

SAp

Aa|ε

AcAAaAFirst(Ap)={a,c,p}First(a)={a}First(ε)={ε}First(cA)={c}First(aA)={a}解：SAp

SBq

Aa

AcA

Bb

BdB練習(xí)：求給定文法每個(gè)候選式First集First(S1)=First(Ap)＝{a,c}

First(S2)=First(Bq)={b,d}

First(A1)={a}

First(A2)={c}

First(B1)=First(B2)=u0ccwuo解：(1)SxAy(2)A**|*在右邊給定文法中，A候選式有兩個(gè)，其首終止符集為：First(A1)={*}First(A2)={*}相交,就會(huì)產(chǎn)生回溯所以，只要存在某個(gè)非終止符多個(gè)候選式首終止符集相交，就會(huì)在推導(dǎo)某時(shí)刻產(chǎn)生回溯。從而造成語(yǔ)法分析器選擇了錯(cuò)誤侯選式。所以，不產(chǎn)生回溯條件就是：對(duì)非終止符A任意兩個(gè)不一樣侯選式ai和aj，都有：

First(ai)∩First(aj)=φ當(dāng)要求用A進(jìn)行匹配時(shí)，就能依據(jù)所面臨輸入字符，準(zhǔn)確地選取一個(gè)A侯選式。非終止符A首終止符集定義即，由該非終止符推導(dǎo)出全部符號(hào)串中第一個(gè)終止符集合。對(duì)不含左遞歸文法G，對(duì)某非終止符A：

First(A)={a|Aa…,a∈VT}若Aε，則ε∈First(A)**SAp

SBq

Aa

AcA

Bb

BdB練習(xí)：求給定文法每個(gè)候選式First集和每個(gè)非終止符First集。解：First(A)={a,c}First(B)={b,d}First(S)={a,c,b,d}求非終止符AFirst集算法

求某一非終止符A首終止符集First(A)算法為：1.若有產(chǎn)生式Aaα,a∈VT，把a(bǔ)加到First(A)中；2.若有產(chǎn)生式Aε,把ε加到First(A)中；3.若有產(chǎn)生式AXα，X∈VN，把First(X)中非ε元素加到First(A)中；4.若有產(chǎn)生式AX1X2X3...Xkα,其中X1X2...Xk∈VN。則當(dāng)X1X2X3...Xi

=>ε(1≤i≤k)時(shí)，把First(Xi+1...Xkα)非ε元素加到

First(A)中；

當(dāng)X1X2X3...Xk=>ε時(shí)，把First(α)加入First(A)中5.重復(fù)執(zhí)行上述過(guò)程，直到First(A)不再增大**SAp

SBq

Aa

AcA

Bb

BdB例：用算法求下述文法每個(gè)非終止符First集First(A)={a,c}

First(B)={b,d}First(S)=First(A)∪First(B)={a,c,b,d}解：ETE'

E'+TE'

E'ε

TFT'

T'*FT'

T'ε

F(E)

F

iFirst(F)={(，i}First(T')={*，ε}First(E‘)={+，ε}

First(T)=First(F)={(，i}

First(E)=First(T)={(，i}練習(xí)求以下文法每個(gè)非終止符First集 是否滿足：沒(méi)有左遞歸，每個(gè)侯選式首終止符集不相交這兩個(gè)條件，就一定能進(jìn)行有效自頂向下分析呢？思索題確定自上而下分析舉例1：對(duì)于文法G1[S]：S→pA S→qB A→cAd A→a對(duì)輸入串pccadd，自上而下推導(dǎo)過(guò)程是： S=>pA=>pcAd=>pccAdd=>pccadd對(duì)應(yīng)分析樹(shù)：例2：對(duì)于文法G2[S]： S→ApS→BqA→aA→cAB→bB→dB輸入串ccap，自上而下推導(dǎo)過(guò)程是：S=>Ap=>cAp=>ccAp=>ccap例3：使用下述文法對(duì)i+i進(jìn)行分析：ETE'E'

+TE'|εTFT'T'*FT'|εF(E)|i第一步：i∈First(TE')i∈First(FT')i∈First(F)ETE'FT'i第三步：+∈First(E')……第二步：+first(T')用ε自動(dòng)匹配不讀輸入符號(hào)+TE'FT'iεεεLL(1)分析條件后隨符號(hào)集定義假定S是文法開(kāi)始符號(hào)，對(duì)于A∈ＶN：Follow(a)={a|S…Aa…，a∈ＶT}

尤其，若S…A，則，#

∈FOLLOW(A)當(dāng)非終止符A面臨a時(shí)，a不屬于A任何侯選首終止符集，但A某個(gè)候選首終止符集中含ε，只有當(dāng)a∈FOLLOW(A)時(shí)才能自動(dòng)進(jìn)行匹配。**對(duì)右邊給定文法，求A后隨符號(hào)集follow(A)SAp

Aa|ε

AcAAaAfollow(A)={p}求非終止符AFollow集算法

1.假如A是開(kāi)始符號(hào)，?！蔉ollow(A)2.若有產(chǎn)生式BαAaβ,a∈VT，則把a(bǔ)加入到Follow(A)中；3.若有產(chǎn)生式BαAXβ，X∈VN，則把First(Xβ)中非ε元素加入Follow(A)中；4.若BαA

或BαAβ，β=>ε，則把Follow(B)加入到Follow(A)中；5.連續(xù)使用上述規(guī)則，直到Follow(A)不再增大。*例:求下題Follow集SAp

SBq

Aa

AcA

Bb

BdB解：Follow(S)={#}Follow(A)={p}Follow(B)={q}規(guī)則1規(guī)則2規(guī)則2練習(xí)1.ETE'

2.E'+TE'

3.E'ε

4.TFT'

5.T'*FT'

6.T'ε

7.F(E)

8.Fifollow(E)={#，)}

follow(E')=follow(E)={#，)}

follow(T)=(first(E')-{ε})

∪

follow(E')={#,),+}

follow(T')=follow(T)={#，)，+}

follow(F)=(first(T')-{ε})∪f(wàn)ollow(T)={*,#,),+}E是開(kāi)始符號(hào)，應(yīng)用規(guī)則1，依據(jù)產(chǎn)生式7，應(yīng)用規(guī)則2依據(jù)產(chǎn)生式1，應(yīng)用規(guī)則4依據(jù)產(chǎn)生式2，應(yīng)用規(guī)則3，依據(jù)產(chǎn)生式2，3，應(yīng)用規(guī)則4依據(jù)產(chǎn)生式4，應(yīng)用規(guī)則4依據(jù)產(chǎn)生式4，應(yīng)用規(guī)則3依據(jù)產(chǎn)生式4，6，應(yīng)用規(guī)則4求下題Follow集(對(duì)文法進(jìn)行不帶回溯確實(shí)定自頂向下分析條件)，據(jù)此判別是否為L(zhǎng)L(1)文法。(1)文法不含左遞歸(2)對(duì)文法中任一個(gè)非終止符A各個(gè)候選式首終止符集兩兩不相交，即：若 Aα1|α2|…|αn，則

First(ai)∩First(aj)=φ(i≠j)(3)對(duì)文法中每個(gè)非終止符A,若它某個(gè)首終止符集含有ε，則

First(A)∩Follow(A)=φLL(1)文法定義LL(1)文法判別

依據(jù)LL(1)三個(gè)條件來(lái)判斷.判別步驟:1.首先檢驗(yàn)是否含有左遞歸2.若無(wú)，計(jì)算First集,判別是否滿足條件2(即是否有回溯)3.若存在某個(gè)A=>ε,求A

Follow集，并判別條件(3)是否滿足(是否能夠使用ε-產(chǎn)生式進(jìn)行匹配)*例：判斷下述文法是否是LL(1)文法：SaAS

Sb

AbA

Aε解：(1)該文法不含左遞歸(2)First(SaAS)={a}First(Sb)= First(AbA)=First(Aε)={ε}

S和A侯選式first集都不相交，滿足條件2(3)因?yàn)棣拧蔉irst(Aε) Follow(A)=First(S)={a,b}Follow(A)∩First(A

bA))

≠φ不滿足條件3，則不是LL(1)文法練習(xí)判斷給定文法是否為L(zhǎng)L(1)文法，若不是，進(jìn)行改造解答：First(Aab)={a};First(Aa)={a};不滿足條件2，故不是LL(1)文法改造方法：(消除回溯——提取公因子) SxAy;Aa(b|ε)

=>SxAy;AaA';A'b|εSxAy

Aab|a例3：使用下述文法對(duì)i+i進(jìn)行分析：ETE'E'

+TE'|εTFT'T'*FT'|εF(E)|i第一步：i∈First(TE')i∈First(FT')i∈First(F)ETE'FT'i第三步：+∈First(E')……第二步：+first(T')ε∈First(T')，+∈Follow(T')ε自動(dòng)匹配,不讀輸入符號(hào)+TE'FT'iεεεLL(1)分析過(guò)程follow(E)={#，)}

follow(E')=follow(E)={#，)}

follow(T)=follow(E')∪(first(E')-{ε})={#,),+}

follow(T')=follow(T)={#，)，+}

follow(F)=(first(T')-{ε})∪f(wàn)ollow(T)={*,#,),+}LL(1)文法分析過(guò)程假設(shè)要用非終止符A進(jìn)行匹配，面臨輸入符號(hào)a，A全部侯選式為：Aα1|α2|…|αn分析過(guò)程為：(總結(jié))若a

∈First(Aαi),使用αi去匹配。若a不屬于任何一個(gè)產(chǎn)生式首終止符集，(1)若ε不屬于任何一個(gè)First(Aαi)，則犯錯(cuò)。(2)若ε屬于某個(gè)First(Aαi),同時(shí)a

∈Follow(A),則讓A與ε自動(dòng)匹配；不然，a出現(xiàn)是一個(gè)語(yǔ)法錯(cuò)誤。4.4遞歸下降分析方法是進(jìn)行語(yǔ)法分析一個(gè)方法要求文法是LL(1)文法實(shí)現(xiàn)思想：識(shí)別程序由一組過(guò)程組成。每個(gè)過(guò)程對(duì)應(yīng)于文法一個(gè)非終止符號(hào)。每一個(gè)過(guò)程功效是：選擇正確右部，掃描完對(duì)應(yīng)字。在右部中有非終止符號(hào)時(shí)，調(diào)用該非終止符號(hào)對(duì)應(yīng)過(guò)程來(lái)完成。基本架構(gòu)(1)對(duì)于每個(gè)非終止符號(hào)產(chǎn)生式U→u1|u2|…|un處理方法以下：U(){

ch=當(dāng)前符號(hào); if(ch是u1符號(hào)串第一個(gè)符號(hào))處理u1 elseif(ch是u2符號(hào)串第一個(gè)符號(hào))處理u2 …… else

error()}因?yàn)闊o(wú)回溯文法確保選擇是唯一。當(dāng)存在ε時(shí)，能夠用error()替換為{return;}這么能夠較晚發(fā)覺(jué)錯(cuò)誤。約定：進(jìn)入這個(gè)過(guò)程時(shí)，已讀入U(xiǎn)第一個(gè)符號(hào)。離開(kāi)這個(gè)過(guò)程時(shí)，下一個(gè)符號(hào)已經(jīng)被讀到當(dāng)前符號(hào)?；炯軜?gòu)(2)對(duì)于U每個(gè)右部ui=x1x2…xn處理架構(gòu)以下：

處理x1程序； 處理x2程序； ……… 處理xn程序；假如右部為空ε，則不處理?；炯軜?gòu)(3)對(duì)于右部中每個(gè)符號(hào)xi假如xi為終止符號(hào)：If(x==當(dāng)前輸入符號(hào)串中符號(hào)) {NextCh()；return;}else 犯錯(cuò)處理假如xi為非終止符號(hào)，直接調(diào)用對(duì)應(yīng)過(guò)程： xi()P74過(guò)程對(duì)應(yīng)于前述文法：ETE'

E'+TE'|ε

TFT'

T'*FT'|ε

F(E)|i在給定語(yǔ)法定義中選擇與IF語(yǔ)句相關(guān)產(chǎn)生式。<if語(yǔ)句>::=if<布爾表示式>then<執(zhí)行句>else<執(zhí)行句><布爾表示式>::=<變量><關(guān)系符><變量><關(guān)系符>::=<|>|<>|<=|>=|=<執(zhí)行語(yǔ)句>::=<變量>:=<整數(shù)><變量>::=<標(biāo)識(shí)符><整數(shù)>::=<數(shù)字>|<整數(shù)><數(shù)字><數(shù)字>::=0|1|2|3…|9如：對(duì)應(yīng)于產(chǎn)生式

<if語(yǔ)句>::=if<布爾表示式>then<執(zhí)行句>

過(guò)程算法描述為：ifs(){ gettoken(); If(token!=“if”)error; getnexttoken();

bool_expr(); getnexttoken(); If(token!=“then”)error; getnexttoken();

exe_sentence();}對(duì)應(yīng)于產(chǎn)生式：

<布爾表示式>::=<變量><關(guān)系符><變量>

過(guò)程：bool_expr(){ gettoken();

handle_varible(); Getnexttoken(); If(tokennotin!(<|>|<>|<=|>=|=)error; Getnexttoken();

handle_varible();}請(qǐng)寫(xiě)出for語(yǔ)句遞歸下降分析程序：<for語(yǔ)句>::=for<標(biāo)識(shí)符>:=<算術(shù)表示式1>to<算術(shù)表示式2>do<執(zhí)行句><算術(shù)表示式>::=<算術(shù)表示式>±<項(xiàng)>|±<項(xiàng)>|<項(xiàng)><項(xiàng)>::=<項(xiàng)>*<因子>|<項(xiàng)>/<因子>|<因子><因子>::=<算術(shù)量><算術(shù)量>::=<標(biāo)識(shí)符>|<整數(shù)><執(zhí)行語(yǔ)句>::=<變量>:=<整數(shù)><執(zhí)行語(yǔ)句>::=<for語(yǔ)句>………….遞歸分析程序優(yōu)點(diǎn)實(shí)現(xiàn)思想簡(jiǎn)單明了。程序結(jié)構(gòu)和語(yǔ)法規(guī)則直接對(duì)應(yīng)。因?yàn)槊總€(gè)過(guò)程表示一個(gè)非終止符號(hào)處理，添加語(yǔ)義加工工作比較方便。需要書(shū)寫(xiě)程序語(yǔ)言支持遞歸調(diào)用。假如遞歸調(diào)用機(jī)制是高效，那么分析程序也是高效。4.5預(yù)測(cè)分析程序遞歸下降分析法：采取遞歸過(guò)程。所以實(shí)現(xiàn)分析程序所使用高級(jí)語(yǔ)言必須支持遞歸過(guò)程才行。預(yù)測(cè)分析法是自頂向下分析另一個(gè)方法。使用下推自動(dòng)機(jī)方式實(shí)現(xiàn)。使用一個(gè)二維分析表和棧聯(lián)合進(jìn)行控制來(lái)實(shí)現(xiàn)分析。預(yù)測(cè)分析器模型預(yù)測(cè)分析器組成：預(yù)測(cè)分析程序(與文法無(wú)關(guān))先進(jìn)后出棧預(yù)測(cè)分析表－與文法相關(guān)分析表M:是一個(gè)從VN(VT{#})到產(chǎn)生式映射。在分析時(shí)碰到A和a時(shí)，應(yīng)該選擇M[A,a]中存放產(chǎn)生式。假如M[A,a]為空，表示出現(xiàn)語(yǔ)法錯(cuò)誤。分析表格式:i+*()#ETE'TE'E'+TE'TFT'FT'T'*FT'Fi(E)第1列為非終止符第1行為終止符+’#’每個(gè)元素為產(chǎn)生式或空ETE'

E'+TE'|ε

TFT'

T'*FT'|ε

F(E)|i總控程序:將’#’壓入堆棧中，將開(kāi)始符號(hào)S壓入堆棧中讀取第一個(gè)輸入符號(hào)到a；循環(huán)執(zhí)行下述操作：棧頂符號(hào)彈出放入X中；假如X為終止符號(hào)：假如X==a!=‘#’，表明成功匹配a符號(hào);讀取下一個(gè)符號(hào)到a，不然犯錯(cuò)；假如X==‘#’假如X==a，分析結(jié)束，接收句子。假如X!=a，犯錯(cuò)處理。假如X為非終止符號(hào),則查分析表M:假如M[X,a]為空，犯錯(cuò)處理。假如M[X,a]=‘X1X2…Xn’,則:將右部Xn…X2X1反序壓入堆棧中。預(yù)測(cè)分析過(guò)程下面用預(yù)測(cè)分析方法對(duì)輸入串i+i*i#進(jìn)行分析，給出棧改變過(guò)程以下：1#Ei+i*i#ETE2#ETi+i*i#TFT3#ETFi+i*i#Fi4#ETii+i*i#i匹配5#ET+i*i#Tε6#E+i*i#E+TE7#ET++i*i#+匹配步驟分析棧剩下輸入串所用產(chǎn)生式8#ETi*i#TFT'9#ETFi*i#Fi10#ETii*i#i匹配11#ET*i#T*FT12#ETF**i#*匹配13#ETFi#Fi14#ETii#i匹配15#ET#Tε16#E#Eε17##接收結(jié)構(gòu)預(yù)測(cè)分析表預(yù)測(cè)分析過(guò)程總控程序是固定。對(duì)于某個(gè)文法，分析表是分析過(guò)程關(guān)鍵。表中M[A,a]=A→X1X2…Xn表示對(duì)應(yīng)于X1X2…Xn字首終止符能夠是a。就是說(shuō)X1X2…Xn=>aw。能夠經(jīng)過(guò)這個(gè)方式來(lái)確定分析表中值。(即：求首終止符)*預(yù)測(cè)分析表結(jié)構(gòu)算法對(duì)文法每個(gè)文法符號(hào)X結(jié)構(gòu)First(X)對(duì)于每一產(chǎn)生式A→α,對(duì)于每個(gè)終止符a∈First(α),將A→α填入M[A,a]；假如ε∈First(α)，則結(jié)構(gòu)Follow(A)，對(duì)任何元素b∈Follow(A)，將A→α填入M[A,b]；將全部沒(méi)有定義M[A,a]標(biāo)上錯(cuò)誤標(biāo)志。假如文法是LL(1)文法，其預(yù)測(cè)分析表中沒(méi)有多重定義元素，能夠進(jìn)行確定分析。例：求對(duì)應(yīng)于下述文法預(yù)測(cè)分析表：1.首先求first集ETE'

E'+TE'|ε

TFT'

T'*FT'|ε

F(E)|iFirst(E)={(，i}

First(E')={+，ε}

First(T)={(，i}

First(T')={*，ε}First(F)={(，i}2.因?yàn)棣臚irst(E'),εFirst(T'),求E'和T'Follow集Follow(E')={#，)}

Follow(T')={#，)，+}3.依據(jù)集合值填表，得到i+*()#ETE'TE'E'+TE'TFT'FT'T'*FT'Fi(E)綜合練習(xí)設(shè)文法G(S)：S→(L)|aS|aL→L，S|S(1)消除左遞歸和回溯；(2)計(jì)算每個(gè)非終止符First和Follow集；(3)結(jié)構(gòu)預(yù)測(cè)分析表。預(yù)測(cè)分析表a，()＃SS→aS'S→(L)S'S'→SS'→εS'→SS'→εS'→εLL→SL'L→SL'L'L'→,SL'L'→εFirst(S)＝{(,a}Follow(S)＝{#,，,)}First(S')＝{(,a,ε}Follow(S')＝{#,，,)}First(L)＝{(,a}Follow(L)＝{)}First(L')＝{，,ε}

Follow(L')＝{)}

S→(L)|aS'S'→S|εL→SL'L'→,SL'|ε

4.6自上而下語(yǔ)法分析程序設(shè)計(jì)

實(shí)現(xiàn)語(yǔ)法成份包含：(1)帶類型簡(jiǎn)單變量說(shuō)明語(yǔ)句；(2)算術(shù)表示式和布爾表示式；(3)簡(jiǎn)單賦值語(yǔ)句；(4)各種控制語(yǔ)句：如if語(yǔ)句、while語(yǔ)句、repeat語(yǔ)句、for語(yǔ)句源程序舉例：programexample;consti＝5；var a,b,c:integer; x:char;begin if(a+c*3>b)and(b>3)thenc:=3; x:=2+(3*a)-b*c*8; forx:=1+2to3dob:=100; whilea>bdoc:=5; repeata:=10;