《《編譯原理課程教案》第4章：自上而下語(yǔ)法分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《編譯原理課程教案》第4章：自上而下語(yǔ)法分析.ppt（74頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

自上而下語(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ò)程的核心，其任務(wù)是在詞法分析識(shí)別出正確的單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。,4.1語(yǔ)法分析的任務(wù),問(wèn)題：在上一章詞法分析中講解了如何判斷源程序中單詞的正確性，并輸出了正確的單詞符號(hào)。那么如何知道這些正確的單詞是否能構(gòu)成正確的表達(dá)式、語(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ǔ)法構(gòu)成規(guī)則,識(shí)別輸入的符號(hào)串能否構(gòu)成一個(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：E?E+EE?E*EE?(E)E?i,解：使用最左推導(dǎo)：E?E*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ù)。具體分類：,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)生式，謀求輸入串的匹配，試圖向下構(gòu)造一棵語(yǔ)法樹(shù)，其末端節(jié)點(diǎn)正好與輸入符號(hào)串相同。需要反復(fù)試探。,例1：設(shè)有文法(1)S?xAy(2)A?**|*現(xiàn)有輸入串：x*y其分析過(guò)程如右：,失敗，需要退回，重新選取A的侯選式，這時(shí)使得分析器的動(dòng)作不穩(wěn)定,思考：產(chǎn)生回溯的原因？,,,問(wèn)題1：回溯(P67),真正原因是：文法的產(chǎn)生式有問(wèn)題。,左遞歸：文法中存在某個(gè)A?Vn，有AA?。直接左遞歸：有產(chǎn)生式A?A?間接左遞歸：,例2：設(shè)有文法G(E)：(1)E?E+T|T(2)T?T*F|F(3)F?(E)|i現(xiàn)有輸入串i*i+i,分析過(guò)程是：,,失敗：對(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：文法E?E+T|TT?T*F|FF?(E)|i消去左遞歸后為：,T?FTT?*FT|ε,,E?TEE?+TE|ε,F?(E)|i,,一般而言，若產(chǎn)生式形式為：A→Aα1|Aα2|…|Aαn|β1|β2|…|βm將其替換為：,,練習(xí),消去文法G[S]的左遞歸,S?(T)|a+S|aT?T,S|S,例：給定間接左遞歸文法，請(qǐng)消除左遞歸,(1)代入(2)消除直接左遞歸,S?Qc|cQ?Rb|bR?Sa|a,解：第1步：為R、S、Q排序第2步：代入：將R代入Q,Q代入S，得到新的文法產(chǎn)生式組：R?Sa|aQ?Sab|ab|bS?Sabc|abc|bc|c第3步：消去S的直接左遞歸，得到,S?abcS|bcS|cSS?abcS|ε,2.間接左遞歸的消除方法P69,方法是:反復(fù)“提取公共左因子”，使得文法的每個(gè)非終結(jié)符號(hào)的各個(gè)候選式的首終結(jié)符集兩兩不相交，來(lái)避免回溯。,設(shè)產(chǎn)生式為：A→δα1|δα2|…|δαn,消除回溯,例3：有如下兩個(gè)產(chǎn)生式：?ifEthenS1elseS2;?ifEthenS1;,提取左因子后：?ifEthenS1B;B?elseS2|ε;,練習(xí),提取下述文法的左因子,S?(T)|a+S|aT?STT’?,ST|ε,問(wèn)題:如果希望沒(méi)有回溯，對(duì)文法有什么要求？,回溯產(chǎn)生的真正原因是：某非終結(jié)符對(duì)應(yīng)多個(gè)侯選式，它們右部的第一個(gè)終結(jié)符相同，從而導(dǎo)致語(yǔ)法分析器選擇了錯(cuò)誤的侯選式。如果希望沒(méi)有回溯，對(duì)文法有什么要求？,侯選式的首終結(jié)符集的定義,即，由該候選式推導(dǎo)出的所有符號(hào)串中的第一個(gè)終結(jié)符的集合。,4.3LL(1)文法,,,S?ApS?BqA?aA?cAB?bB?dB,練習(xí)：求給定文法的每個(gè)候選式的First集,(1)S?xAy(2)A?**|*,在右邊給定的文法中，A的候選式有兩個(gè)，其首終結(jié)符集為：First(A1)={*}First(A2)={*}相交,就會(huì)產(chǎn)生回溯,因此，只要存在某個(gè)非終結(jié)符的多個(gè)候選式的首終結(jié)符集相交，就會(huì)在推導(dǎo)的某時(shí)刻產(chǎn)生回溯。從而導(dǎo)致語(yǔ)法分析器選擇了錯(cuò)誤的侯選式。,因此，不產(chǎn)生回溯的條件就是：對(duì)非終結(jié)符A的任意兩個(gè)不同的侯選式ai和aj，都有：First(ai)∩First(aj)=φ當(dāng)要求用A進(jìn)行匹配時(shí)，就能根據(jù)所面臨的輸入字符，準(zhǔn)確地選取一個(gè)A的侯選式。,非終結(jié)符A的首終結(jié)符集的定義,即，由該非終結(jié)符推導(dǎo)出的所有符號(hào)串中的第一個(gè)終結(jié)符的集合。,S?ApS?BqA?aA?cAB?bB?dB,練習(xí)：求給定文法的每個(gè)候選式的First集和每個(gè)非終結(jié)符的First集。,求非終結(jié)符A的First集的算法,求某一非終結(jié)符A的首終結(jié)符集First(A)的算法為：1.若有產(chǎn)生式A?aα,a∈VT，把a(bǔ)加到First(A)中；2.若有產(chǎn)生式A?ε,把ε加到First(A)中；3.若有產(chǎn)生式A?Xα，X∈VN，把First(X)中非ε元素加到First(A)中；4.若有產(chǎn)生式A?X1X2X3...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)不再增大,*,*,S?ApS?BqA?aA?cAB?bB?dB,例：用算法求下述文法的每個(gè)非終結(jié)符的First集,E?TEE?+TEE?εT?FTT?*FTT?εF?(E)F?i,First(F)={(，i}First(T)={*，ε}First(E‘)={+，ε}First(T)=First(F)={(，i}First(E)=First(T)={(，i},練習(xí),求下列文法的每個(gè)非終結(jié)符的First集,,是否滿足：沒(méi)有左遞歸，每個(gè)侯選式的首終結(jié)符集不相交這兩個(gè)條件，就一定能進(jìn)行有效的自頂向下分析呢？,思考題,確定的自上而下的分析舉例1：對(duì)于文法G1[S]：S→pAS→qBA→cAdA→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)行分析：,E?TEE?+TE|εT?FTT?*FT|εF?(E)|i,第一步：i∈First(TE)i∈First(FT)i∈First(F),第三步：+∈First(E)……,第二步：+?first(T)用ε自動(dòng)匹配不讀輸入符號(hào),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)非終結(jié)符A面臨a時(shí)，a不屬于A的任何侯選首終結(jié)符集，但A的某個(gè)候選首終結(jié)符集中含ε，只有當(dāng)a∈FOLLOW(A)時(shí)才能自動(dòng)進(jìn)行匹配。,*,*,,對(duì)右邊給定的文法，求A的后隨符號(hào)集follow(A),S?ApA?a|εA?cAA?aA,follow(A)={p},求非終結(jié)符A的Follow集的算法,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集,S?ApS?BqA?aA?cAB?bB?dB,解：Follow(S)={#}Follow(A)={p}Follow(B)={q},規(guī)則1,規(guī)則2,規(guī)則2,練習(xí),1.E?TE2.E?+TE3.E?ε4.T?FT5.T?*FT6.T?ε7.F?(E)8.F?i,follow(E)={#，)}follow(E)=follow(E)={#，)}follow(T)=(first(E)-{ε})∪f(wàn)ollow(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)行不帶回溯的確定的自頂向下分析的條件)，據(jù)此判別是否為L(zhǎng)L(1)文法。(1)文法不含左遞歸(2)對(duì)文法中的任一個(gè)非終結(jié)符A的各個(gè)候選式的首終結(jié)符集兩兩不相交，即：若A?α1|α2|…|αn，則First(ai)∩First(aj)=φ(i≠j)(3)對(duì)文法中的每個(gè)非終結(jié)符A,若它的某個(gè)首終結(jié)符集含有ε，則First(A)∩Follow(A)=φ,LL(1)文法的定義,LL(1)文法的判別,根據(jù)LL(1)的三個(gè)條件來(lái)判斷.判別步驟:1.首先檢查是否含有左遞歸2.若無(wú)，計(jì)算First集,判別是否滿足條件2(即是否有回溯)3.若存在某個(gè)A=>ε,求A的Follow集，并判別條件(3)是否滿足(是否可以使用ε-產(chǎn)生式進(jìn)行匹配),*,,例：判斷下述文法是否是LL(1)文法：S?aASS?bA?bAA?ε,解：(1)該文法不含左遞歸(2)First(S?aAS)={a}First(S?b)=First(A?bA)=First(A?ε)={ε}S和A的侯選式的first集都不相交，滿足條件2(3)由于ε∈First(A?ε)Follow(A)=First(S)={a,b}Follow(A)∩First(A?bA))≠φ不滿足條件3，則不是LL(1)文法,練習(xí),,判斷給定的文法是否為L(zhǎng)L(1)文法，若不是，進(jìn)行改造,解答：First(A?ab)={a};First(A?a)={a};不滿足條件2，故不是LL(1)文法,改造方法：(消除回溯——提取公因子)S?xAy;A?a(b|ε)=>S?xAy;A?aA;A?b|ε,S?xAyA?ab|a,例3：使用下述文法對(duì)i+i進(jìn)行分析：,E?TEE?+TE|εT?FTT?*FT|εF?(E)|i,第一步：i∈First(TE)i∈First(FT)i∈First(F),,第三步：+∈First(E)……,第二步：+?first(T)ε∈First(T)，+∈Follow(T)ε自動(dòng)匹配,不讀輸入符號(hào),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è)要用非終結(jié)符A進(jìn)行匹配，面臨輸入符號(hào)a，A的所有侯選式為：A?α1|α2|…|αn分析過(guò)程為：(總結(jié))若a∈First(A?αi),使用αi去匹配。若a不屬于任何一個(gè)產(chǎn)生式的首終結(jié)符集，(1)若ε不屬于任何一個(gè)First(A?αi)，則出錯(cuò)。(2)若ε屬于某個(gè)First(A?αi),同時(shí)a∈Follow(A),則讓A與ε自動(dòng)匹配；否則，a的出現(xiàn)是一種語(yǔ)法錯(cuò)誤。,4.4遞歸下降分析方法,是進(jìn)行語(yǔ)法分析的一種方法要求文法是LL(1)文法實(shí)現(xiàn)思想：識(shí)別程序由一組過(guò)程組成。每個(gè)過(guò)程對(duì)應(yīng)于文法的一個(gè)非終結(jié)符號(hào)。每一個(gè)過(guò)程的功能是：選擇正確的右部，掃描完相應(yīng)的字。在右部中有非終結(jié)符號(hào)時(shí)，調(diào)用該非終結(jié)符號(hào)對(duì)應(yīng)的過(guò)程來(lái)完成。,基本架構(gòu)(1),對(duì)于每個(gè)非終結(jié)符號(hào)的產(chǎn)生式U→u1|u2|…|un處理的方法如下：U(){ch=當(dāng)前符號(hào);if(ch是u1符號(hào)串的第一個(gè)符號(hào))處理u1elseif(ch是u2符號(hào)串的第一個(gè)符號(hào))處理u2……elseerror()},由于無(wú)回溯的文法保證選擇是唯一的。當(dāng)存在ε時(shí)，可以用error()替代為{return;}這樣可以較晚發(fā)現(xiàn)錯(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為終結(jié)符號(hào)：If(x==當(dāng)前輸入符號(hào)串中的符號(hào)){NextCh()；return;}else出錯(cuò)處理如果xi為非終結(jié)符號(hào)，直接調(diào)用相應(yīng)的過(guò)程：xi(),,P74過(guò)程對(duì)應(yīng)于前述的文法：,E?TEE?+TE|εT?FTT?*FT|εF?(E)|i,在給定的語(yǔ)法定義中選擇與IF語(yǔ)句有關(guān)的產(chǎn)生式。::=ifthenelse::=::=||=|=::=:=::=::=|::=0|1|2|3…|9,如：對(duì)應(yīng)于產(chǎn)生式::=ifthen的過(guò)程的算法描述為：,ifs(){gettoken();If(token!=“if”)error;getnexttoken();bool_expr();getnexttoken();If(token!=“then”)error;getnexttoken();exe_sentence();},相應(yīng)于產(chǎn)生式：::=的過(guò)程：,bool_expr(){gettoken();handle_varible();Getnexttoken();If(tokennotin!(||=|=)error;Getnexttoken();handle_varible();},,請(qǐng)寫(xiě)出for語(yǔ)句的遞歸下降的分析程序：,::=for:=todo::=||::=*|/|::=::=|::=:=::=………….,遞歸分析程序的優(yōu)點(diǎn),實(shí)現(xiàn)思想簡(jiǎn)單明了。程序結(jié)構(gòu)和語(yǔ)法規(guī)則直接對(duì)應(yīng)。因?yàn)槊總€(gè)過(guò)程表示一個(gè)非終結(jié)符號(hào)的處理，添加語(yǔ)義加工工作比較方便。需要書(shū)寫(xiě)程序的語(yǔ)言支持遞歸調(diào)用。如果遞歸調(diào)用機(jī)制是高效的，那么分析程序也是高效的。,4.5預(yù)測(cè)分析程序,遞歸下降分析法：采用遞歸過(guò)程。因此實(shí)現(xiàn)分析程序所使用的高級(jí)語(yǔ)言必須支持遞歸過(guò)程才行。預(yù)測(cè)分析法是自頂向下分析的另一種方法。使用下推自動(dòng)機(jī)的方式實(shí)現(xiàn)。使用一個(gè)二維分析表和棧聯(lián)合進(jìn)行控制來(lái)實(shí)現(xiàn)分析。,預(yù)測(cè)分析器模型,,分析表M:是一個(gè)從VN?(VT?{#})到產(chǎn)生式的映射。在分析時(shí)遇到A和a時(shí)，應(yīng)該選擇M[A,a]中存放的產(chǎn)生式。如果M[A,a]為空，表示出現(xiàn)語(yǔ)法錯(cuò)誤。分析表格式:,第1列為非終結(jié)符,第1行為終結(jié)符+’#’,每個(gè)元素為產(chǎn)生式或空,E?TEE?+TE|εT?FTT?*FT|εF?(E)|i,總控程序:,將’#’壓入堆棧中，將開(kāi)始符號(hào)S壓入堆棧中讀取第一個(gè)輸入符號(hào)到a；循環(huán)執(zhí)行下述操作：棧頂符號(hào)彈出放入X中；如果X為終結(jié)符號(hào)：如果X==a!=‘#’，表明成功匹配a符號(hào);讀取下一個(gè)符號(hào)到a，否則出錯(cuò)；如果X==‘#’如果X==a，分析結(jié)束，接受句子。如果X!=a，出錯(cuò)處理。如果X為非終結(jié)符號(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ò)程如下：,,構(gòu)造預(yù)測(cè)分析表,預(yù)測(cè)分析過(guò)程的總控程序是固定的。對(duì)于某個(gè)文法，分析表是分析過(guò)程的核心。表中M[A,a]=?A→X1X2…Xn?表示對(duì)應(yīng)于X1X2…Xn字的首終結(jié)符可以是a。就是說(shuō)X1X2…Xn=>aw?？梢酝ㄟ^(guò)這個(gè)方式來(lái)確定分析表中的值。(即：求首終結(jié)符),*,預(yù)測(cè)分析表的構(gòu)造算法,對(duì)文法的每個(gè)文法符號(hào)X構(gòu)造First(X)對(duì)于每一產(chǎn)生式A→α,對(duì)于每個(gè)終結(jié)符a∈First(α),將A→α填入M[A,a]；如果ε∈First(α)，則構(gòu)造Follow(A)，對(duì)任何元素b∈Follow(A)，將A→α填入M[A,b]；將所有無(wú)定義的M[A,a]標(biāo)上錯(cuò)誤標(biāo)志。,如果文法是LL(1)文法，其預(yù)測(cè)分析表中沒(méi)有多重定義的元素，可以進(jìn)行確定的分析。,例：求對(duì)應(yīng)于下述文法的預(yù)測(cè)分析表：,1.首先求first集,E?TEE?+TE|εT?FTT?*FT|εF?(E)|i,First(E)={(，i}First(E)={+，ε}First(T)={(，i}First(T)={*，ε}First(F)={(，i},2.由于ε?First(E),ε?First(T),求E和T的Follow集,Follow(E)={#，)}Follow(T)={#，)，+},3.根據(jù)集合的值填表，得到,綜合練習(xí),設(shè)文法G(S)：S→(L)|aS|aL→L，S|S(1)消除左遞歸和回溯；(2)計(jì)算每個(gè)非終結(jié)符的First和Follow集；(3)構(gòu)造預(yù)測(cè)分析表。,預(yù)測(cè)分析表,First(S)＝{(,a}Follow(S)＝{#,，,)}First(S)＝{(,a,ε}Follow(S)＝{#,，,)}First(L)＝{(,a}Follow(L)＝{)}First(L)＝{，,ε}Follow(L)＝{)},S→(L)|aSS→S|εL→SLL→,SL|ε,4.6自上而下語(yǔ)法分析程序的設(shè)計(jì),,,實(shí)現(xiàn)的語(yǔ)法成分包括：(1)帶類型的簡(jiǎn)單變量的說(shuō)明語(yǔ)句；(2)算術(shù)表達(dá)式和布爾表達(dá)式；(3)簡(jiǎn)單賦值語(yǔ)句；(4)各種控制語(yǔ)句：如if語(yǔ)句、while語(yǔ)句、repeat語(yǔ)句、for語(yǔ)句,源程序舉例：,programexample;consti＝5；vara,b,c:integer;x:char;beginif(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;untila>b;end.,,,,總控程序的框架,voidpaser()/*語(yǔ)法分析總控程序*/{token=getnexttoken();if(token不是“program”)error()；/*程序中缺少program*/token=getnexttoken();if(token不是標(biāo)識(shí)符)error()；/*program后應(yīng)跟程序名*/token=getnexttoken();if(token不為’;’或’(’)error();/*程序也可不帶(input,output)*/token=getnexttoken();if(token是‘const’)handle_const(token);/*調(diào)用常量說(shuō)明處理*/if(token是‘var’)handle_var(token)；/*調(diào)用變量說(shuō)明處理*/token=getnexttoken();if(token不是‘begin’)error();/*begin標(biāo)識(shí)可執(zhí)行程序開(kāi)始*/token=getnexttoken();ST_SORT(token);/*分類調(diào)用處理各個(gè)可執(zhí)行語(yǔ)句*/token=getnexttoken();if(token不是‘end.’)error()；/*end.標(biāo)識(shí)整個(gè)程序結(jié)束*/},語(yǔ)句分類函數(shù)ST_SORT(token),功能：根據(jù)傳遞的單詞判斷應(yīng)該調(diào)用哪個(gè)語(yǔ)句的處理函數(shù)。,ST_SORT(token){if(token是‘if’）ifs()；if(token是‘for’）fors()；if(token是‘while’）whiles()；if(token是‘repeat’）repeat()；if(token是標(biāo)識(shí)符）assigns()elseerror();},可執(zhí)行語(yǔ)句語(yǔ)法分析的實(shí)現(xiàn)舉例,→ifEthenS1elseS2;,,ifs(){/*當(dāng)讀取的首字符是if時(shí)，才調(diào)用該函數(shù)*/token=getnexttoken();/*讀下一個(gè)單詞，是E的一部分*/BEXP();/*調(diào)用布爾表達(dá)式的語(yǔ)法分析程序*/token=getnexttoken();/*讀下一個(gè)單詞*/if(token!="then")error;token=getnexttoken();ST_SORT();/*用ST_SORT()分類處理then后的不同語(yǔ)句*/token=getnexttoken();if(token=="else"){/*if–then--else結(jié)構(gòu)時(shí)處理else部分*/token=getnexttoken();ST_SORT();/*處理else后的可執(zhí)行語(yǔ)句*/}elseif(token!=";")error;/*無(wú)else的if--then結(jié)構(gòu)，后必有；*/},