《《編譯原理課程教案》第4章：自上而下語法分析.ppt》由會員分享，可在線閱讀，更多相關《《編譯原理課程教案》第4章：自上而下語法分析.ppt（74頁珍藏版）》請在裝配圖網上搜索。

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