編譯原理期末復(fù)習(xí)

期 末 復(fù)鑒于編譯原理馬上就要期末考試，我將手中集中的一些資料上的題目進(jìn)行了整理歸類，每種類型題目給出了所涉及到的基本知識，然后對每類題目中的第一道例題進(jìn)行了做法進(jìn)行了講解，剩下的例題請給大家作為練習(xí)，答案也都給出，希望對大家復(fù)習(xí)有所幫助，最后由于時(shí)間很緊，整理的有些倉促，整理中難免有遺漏或錯誤，請大家見諒。注：下面出現(xiàn)的字母中，若無特別說明，小寫英文字母為終結(jié)符，大寫英文字母為非終結(jié)符，希臘字母為終結(jié)符與非終結(jié)符的任意組合。1、簡答題（或者名詞解釋）下面涉及到的概念中，加下劃線的都是在以往一些試卷中出現(xiàn)的原題，務(wù)必掌握。注：這類題目老師說答案不會超過一百個字，否則寫的再多也不給分，有些點(diǎn)到即可，不要重復(fù)啰嗦。（1）簡述編譯程序的概念及其構(gòu)成答：1）編譯程序：它特指把某種高級程序設(shè)計(jì)語言翻譯成等價(jià)的低級程序設(shè)計(jì)語言的翻譯程序。表格管理程芳2）構(gòu)成:出惜處一理程序表格管理程芳2）構(gòu)成:出惜處一理程序（2）簡述詞法分析階段的主要任務(wù)（也有可能問語法分析階段主要任務(wù)）答：詞法分析的任務(wù)是輸入源程序，對源程序進(jìn)行掃描，識別其中的單詞符號，把字符串形式的源程序轉(zhuǎn)換成單詞符號形式的源程序。語法分析的主要任務(wù)是對輸入的單詞符號進(jìn)行語法分析（根據(jù)語法規(guī)則進(jìn)行推導(dǎo)或者歸約），識別各類語法單位，判斷輸入是不是語法上正確的程序（3）簡述編譯程序的構(gòu)造過程（這個大家看看，是對（ 1）和（2）的綜合）答：1）構(gòu)造詞法分析器：用于輸入源程序進(jìn)行詞法分析，輸出單詞符號；2）構(gòu)造語法分析器：對輸入的單詞符號進(jìn)行語法分析，識別各類語法單位，判斷輸入是不是語法上正確的程序3） 構(gòu)造語義分析和中間代碼產(chǎn)生器：按照語義規(guī)則對已歸約出的語法單位進(jìn)行語義分析并把它們翻譯成中間代碼。4） 構(gòu)造優(yōu)化器：對中間代碼進(jìn)行優(yōu)化。5） 構(gòu)造目標(biāo)代碼生成器：把中間的代碼翻譯成目標(biāo)程序。6） 構(gòu)造表格管理程序：登記源程序的各類信息和編譯各階段的進(jìn)展情況。7） 構(gòu)造錯誤處理程序：對出錯進(jìn)行處理。（4）說明編譯和解釋的區(qū)別：1） 編譯要程序產(chǎn)生目標(biāo)程序，解釋程序是邊解釋邊執(zhí)行，不產(chǎn)生目標(biāo)程序；2） 編譯程序運(yùn)行效率高而解釋程序便于人機(jī)對話。（5）文法：描述語言語法結(jié)構(gòu)的形式規(guī)則，一般用一個四元式表示： G=（Vt，VN，S，P），其中Vt：終結(jié)符集合（非空）VN：非終結(jié)符集合（非空），且Vty二S:文法的幵始符號，S*P:產(chǎn)生式集合（有限）。（6） 二義性文法：一個文法中存某個句子，它有兩個不同的最左（或者最右推導(dǎo)），則稱該文法是二義性的。例子如文法GStifexprthenS|other

StStifexprthenSelseS句子ifelthenife2thensielses2是二義性的。文法的形式(注：文法的形式一定要牢記，特別是2型和3型文法一定要牢記，不僅在概念題中有用，在下面的根據(jù)語言寫文法題中也有重要作用，如果所寫的文法形式不對，一切都是無用功)*0型文法(短語文法，圖靈機(jī))：產(chǎn)生式形式為： ，其中：(VtVN)且至少含有一個非終結(jié)符；(VtVn)*1型(上下文有關(guān)文法，線性界限自動機(jī))：產(chǎn)生式形式為: 其中：|||| ，僅S例外但是S不得出現(xiàn)在任何產(chǎn)生式右部。2型文法(上下文無關(guān)文法，非確定下推自動機(jī))：產(chǎn)生式形式為：P，PVn，(VtVn)*。3型文法(正規(guī)文法，有限自動機(jī))：右線性文法：產(chǎn)生式形如： AB或A其**中：Vt；A,BVN 左線性文法：產(chǎn)生式形如： AB或A其中：Vt；A，BU例題：設(shè)G=(V-，gS,P)是一個上下文無關(guān)文法，產(chǎn)生集合 P中的任一個產(chǎn)生式應(yīng)具有什么樣的形式若G是1型文法呢若G是正則文法呢上下文無關(guān)文法， 產(chǎn)生式形式為：P，PVn，(VtV)*。1型文法：產(chǎn)生式形式為: 其中：||||，僅S例外。*正則文法：右線性文法：產(chǎn)生式形如： AB或A其中：Vt；A，BU左線性文法：產(chǎn)生式形如： AB或A其中：V一：ABV什么是PDA下推自動機(jī))—答：PDA是下推自動機(jī)，PDAM用一個七元組表示(K,工,f,H,hO,S,Z)K:有窮狀態(tài)集 ：輸入字母表(有窮)H:下推棧符號的有窮字母表hO:H中的初始符號f:K(工{})H->KH*S:屬于K是初始狀態(tài)。乙包含于K,是終結(jié)狀態(tài)集合。什么是DFA(有窮狀態(tài)自動機(jī))自動機(jī)M是一個五元式M=(S,,f,So,F),其中：1)S:有窮狀態(tài)集，2):輸入字母表(有窮)，f:狀態(tài)轉(zhuǎn)換函數(shù)，為SS的單值部分映射，f(s，a)=s'表示：當(dāng)現(xiàn)行狀態(tài)為s，輸入字符為a時(shí)，將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s'。我們把s'稱為s的一個后繼狀態(tài)。SoS是唯一的一個初態(tài)； 5)FS:終態(tài)集(可空)。推導(dǎo)：所謂推導(dǎo)就是對于一個含非終結(jié)符A的符號串，利用規(guī)則A^a,把A替換成a得到新符號串的過程。最左推導(dǎo)：在推導(dǎo)的每一步，選擇符號串最左邊的非終結(jié)符進(jìn)行替換。最右推導(dǎo)：在推導(dǎo)的每一步，選擇符號串最右邊的非終結(jié)符進(jìn)行替換。歸約：歸約是推倒的逆過程，即用產(chǎn)生式的左部非終結(jié)符替換右部符號串。什么是句型什么稱為句子什么是語言句型：從文法的起始符號出發(fā)，經(jīng)過有限步的推導(dǎo)能夠推導(dǎo)出來的符號稱為句子。句子：只由終結(jié)符構(gòu)成的句型稱為句子。語言：所有句子的集合構(gòu)成該文法描述的語言。什么是短語什么是直接短語(也稱為簡單短語)什么是句柄什么是素短語什么是最左素短語(以下幾個概念一定要理解，考試中肯定會考哪些是短語，直接短語，句柄等，具體方法請參見后面的)*短語：如果存在某個文法非終結(jié)符P,滿足SBPy,并且Pa則稱a為句型B口丫相對于非終結(jié)符P的短語。直接短語：如果Pa,即從P出發(fā)一步推出a，則a稱為直接短語

句柄：一個句型的最左直接短語稱為該句型的句柄素短語：至少含有一個終結(jié)符的短語，并且除了自身外，不包含更小的素短語。最左素短語：句型中最左邊的素短語。（14）自頂向下的語法分析方法中需要解決的主要問題什么如何表示答：1）主要需要解決回溯和左遞歸問題。2 ）表示方式，回溯：文法中存在形如A^ai|a2|…|an,即產(chǎn)生式右部存在多個候選，導(dǎo)致推導(dǎo)時(shí)不能確定到底應(yīng)該選擇哪個候選式。左遞歸：文法中存在形女口PtPa的形式，推導(dǎo)時(shí)會導(dǎo)致推導(dǎo)過程無休止的進(jìn)行下去。注：解決方法，對回溯采取的是提取左公因子，對左遞歸使消除左遞歸（包括直接左遞歸和間接左遞歸）。（15）內(nèi)情向量：一般編譯程序?qū)?shù)組說明的處理是把數(shù)組的有關(guān)信息匯集在一個叫做“內(nèi)情向量”或“信息向量”的表格中，以便以后計(jì)算數(shù)組元素的地址時(shí)引用這些信息。每個數(shù)組有一個內(nèi)情向量。其中的信息包括，數(shù)組的類型，維數(shù)，各維的上、下界，以及數(shù)組的首地址（16）C語言的活動記錄:（16）C語言的活動記錄:topsp臨時(shí)單元內(nèi)情向量局部變量形式單元參數(shù)個數(shù)返回地址OldSP2、最左最右推導(dǎo)，畫語法樹，找短語、直接短語、句柄等。這種題目很簡單，送分題，一定不能丟分!考題：1）文法G[S]為：S—SdT|TTT<G|G（S）|a試給出句型（SdG）va的推導(dǎo)過程及語法樹，并找出(SdG)va的短語，直接(簡單)短語、句柄和最左素短語。分析：(1)推導(dǎo)和畫語法樹這些都很簡單，不再贅述。(2)根據(jù)所畫出的語法樹，可以很快的找出短語，直接短語，句柄和最左素短語等，先講一個簡單子樹的概念，所謂簡單子樹是指僅具有單層分支的子樹。具體方法如下：短語：任一子樹的樹葉全體(具有共同祖先的葉節(jié)點(diǎn)符號串)皆為短語；直接短語：任一簡單子樹的樹葉全體(具有共同父親的葉節(jié)點(diǎn)符號串)皆為簡單短語；句柄：最左邊的直接短語；素短語：至少含有一個終結(jié)符的短語，并且除了自身外，不包含更小的素短語。最左素短語：最左邊的素短語。答：(1)STT<GG<G(S)vG(SdT)vG(SdG)vG(SdG)va語法樹：I短語：G,SdG,(SdG),a,(SdG)<a 直接短語：G,a句柄：G最左素短：a注:還有一份試卷將句型改為adTv(S)，與這個類似，大家自己做做，答案是短語：a,(S),T<(S),adT<(S) 直接短語：a,(S)句柄：a最左素短語：SdG下面兩道例題大家看看，一定要會找短語，直接短語，句柄等考題：2)文法G[E]的產(chǎn)生式為1E+T|TTT*F|FFT|(E)對于句型(i+i)*i ，給出最左最右推導(dǎo)及相應(yīng)的推導(dǎo)樹列出句型的所有短語、簡單短語。(還有一份試卷上是出句型 F+T*F的所有短語、簡單短語和句柄，大家自己做做)答：(1)最左推導(dǎo)：ETT*FF*F(E)*F(E+T)*F(T+T)*F(F+T)*F(i+T)*F(i+F)*F(i+i)*F(i+i)*i最右推導(dǎo)ETT*FT*iF*i(E)*i(E+T)*i(E+F)*i(E+i)*i(T+i)*i(F+i)*i(i+i)*i推導(dǎo)樹如下：短語;i,i+i,(i+i),(i+i)*i 直接短語：i句柄：i3、根據(jù)語言推文法這類題目首先要看清題目，指定的是什么文法，一般都是2型(上下無關(guān)文法)或者3型(正規(guī)文法)，這兩類文法形式一定要記住，具體請參見第 2頁的文法分類。掌握幾個基本形式｛an|n>0｝對應(yīng)文法StaS|a如果是n>=0則為aS|￡(￡是空字){anbn|n>0}對應(yīng)文法StaSb|ab

F面這四道題目老是在試卷中重復(fù)出現(xiàn)，所以大家好好看看考題1、按指定類型給出下列語言的文2、按指定類型給出下列語言的文法,并指出語言的類型。（10分）法。（10分）(1)L1={anbmcn|n>0,m>0}(1)L1={candb]n>0,m>0}用正二型文法：StaSc|BBtbB|b規(guī)文法。⑵L2={0na1nbmcm|n>0,m>0}StcAAtaA|dBBtbB|b二型文法：StABAt0A1|0a1(2)L2={0na1匕匕]n>0,m>0}用BtbBc|e二型文法。StAB at0A1|0a1BtbBc|e3、按指定的類型給出下列語言的文4、按指定的類型給出下列語言的文法（10分）法（10分）(1)L1={canbm|n>0,m>0}用正規(guī)(1)L1={anbmc|n>=0,m>0}用正文法。規(guī)文法StcAAtaA|BBtbB|bStaS|AAtbA|bBBtc(2)L2={0na1nbm|n>0,m>0}用(2)L2二{aOWbd]n>0,m>0}用二二型文法。型文法StAB at0A1|0a1StABAtaTTt0T1|01BtbB|eBtbDDtdD|d這是書P36第11題的答案如下：大家作為練習(xí)，可以發(fā)現(xiàn)比上述題目簡單的多了G3:G1:G2:G4:StACStABStABSt1S0|A

或者G4:4、詞法分析 正規(guī)式、 NFA和DFA之間的轉(zhuǎn)化：這類題目一般是三者之間的轉(zhuǎn)換， 正規(guī)式TNFL確定化的DFA^最小化的DFA有時(shí)已經(jīng)給出NFA了，則只需要確定化為DFA和最小化就行了，一般每一步都是五分。具體怎么轉(zhuǎn)換請參照我期中考試時(shí)整理的提綱，主要就是下面這幅關(guān)系對照圖，因時(shí)間和篇幅限制不再追溯。注意優(yōu)先級關(guān)系，閉包運(yùn)算*最高，連接運(yùn)算.次之，或運(yùn)算|最低。⑶考題1:1)構(gòu)造正則式a*b|(ab)*b對應(yīng)的DFA(15分)畫出NFAXIaIXIaIb{X,1,2,3,4{1,2,5}{Y}}{1,2,5}{1,2}{3,4,Y}{Y}--{1,2}{1,2}{Y}{3,4,Y}{5}{Y}{5}-{3,4}{3,4}{5}{Y}確定化DFA注：C和E是終態(tài)XIalbABCBDEC--DDCEFCF-GGFC最小化DFA首先將集合分為{A,B,D,F,G},{C,E} 。{A,B,D,G}都有a,b作為條件輸出，F(xiàn)只有b輸出，所以分為{A,B,D,G}和{F}同理{C,E}分為{C},{E}。{A,B,D}a={B,D}{G}a={F}所以{A,B,D,G}分為{A,B,D}和{G}。{A}b={C}{B,D}a={D}所以分為{A}{B,D}綜上所述：劃分的結(jié)果為{A},{B,D},{C},{E},{G}.考題2：將NFA確定化為DFA（10分）laIb{X,0,1,3}laIb{X,0,1,3}{021,3}{3,丫}{0,2,1,3}{021,3}{1,3,Y}{3,丫}①{Y}{1,3,Y}{2}{Y}{2}①{1,3}{Y}①①{1,3}{2}{Y}NFA: DFA:含有Y的狀態(tài)子集為DFA的終態(tài),上例中的終態(tài)有B,C,E.abSABAACB①ECDE題目中要求是確定化，沒有要求最小化，如若最小化，劃分的集合為 {S,A},{B,C}{F},{D},{E} 然后再畫出最小化后的DFA這里不再贅述?？碱}3:構(gòu)造奇數(shù)個0和奇數(shù)個1組成的自動機(jī)。（10分）狀態(tài)1:偶數(shù)個0偶數(shù)個1狀態(tài)2:奇數(shù)個0偶數(shù)個1狀態(tài)3:奇數(shù)個0奇數(shù)個1狀態(tài)4:偶數(shù)個0奇數(shù)個1如果題目改成偶數(shù)個0，奇數(shù)個1，只要將狀態(tài)4轉(zhuǎn)換成終態(tài)即可，其他類似。5、語法分析——自頂向下分析法（LL（1）分析法和遞歸向下構(gòu)造子程序法）注：自頂向下分析法本質(zhì)是由開始符號，按照產(chǎn)生式逐步推導(dǎo)看能否產(chǎn)生需要分析的句子。TOC\o"1-5"\h\z（1）自頂向下分析中存在的問題左遞歸和回溯（具體請參見簡答題中的第（ 14）題）（2）消除回溯——提取公因子法提取公共左因子:假定關(guān)于A的規(guī)則Al1|2|-|n| 1|2|…|?其中，每個不以幵頭）那么，可以把這些規(guī)則改寫成A^A| 1|2|-|mA^1I2| …|n（3）消除左遞歸1） 消除直接左遞歸：直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符 P的規(guī)則為…P|，其中不以P幵頭。我們可以把P的規(guī)則等價(jià)地改寫為如下的非直接左遞歸形式：P-P …P|注：一般而言，假定P關(guān)于的全部產(chǎn)生式是P^P1|P2|…|Pm|1|其中，每個都不等于，每個都不以 P幵頭那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成： P~1P|2P|…|nPPT1P|2P|…|P|例：文法G（E）:ETE＋TITTTT*FIFFT（E）Ii經(jīng)消去直接左遞歸后變成：ETTEET+TEI TTFTTT*FTIF T（E）Ii2） 消除間接左遞歸這個請參見我期中整理的提綱篇幅較多，這里不再重復(fù)贅述，請參照下面的考題2考題1：將文法G[S]改寫為等價(jià)的G'[S],使得G'[S]不含左遞歸和左公因子。St[AAfB]|ASBfaB|a答：消除左遞歸和左公因子后的文法為：Sf[AAfB]A'A'fSA'|BfaB'B'fB|考題2：寫出文法G[A]:AfBa|Cb|cBfdA|Ae|fCfBg|h消除左遞歸后的文法。答：(1)經(jīng)分析發(fā)現(xiàn)文法G[A]并無直接左遞歸；(2)消除間接左遞歸：將A,B,C按照B,C,A排序(建議將A放在最后)由于出現(xiàn)CtBg形式，將B代入C得：SdAg|Aeg|fg|h又由于A出現(xiàn)atBaAfCb將B,C帶入A得到：atdAa|Aea|fa|dAgb|Aegb|fgb|hb|c 等價(jià)于atAea|Aegb|dAa|fa|dAgb|fgb|hb|c將A消除直接左遞歸atdAaA|faA|dAgbA'|fgbA'|hbA|cAA'teaA'|egbA'|此時(shí)，對于BtdA|Ae|f，CtdAg|Aeg|fg|h 由于未在任何產(chǎn)生式的右部出現(xiàn)，所以是多余的。綜上所述:消除遞歸后的文法為：AtdAaA'|faA'|dAgbA'|fgbA'|hbA'|cA'A'teaA'|egbA'|LL(1)分析法1)含義：LL(1)分析方法(也叫預(yù)測分析法)：是指從左到右掃描、最左推導(dǎo)(LL)和只查看一個當(dāng)前符號(括號中的1)。2)判斷一個文法是否是LL(1)文法的充要條件：文法不含左遞歸，對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若A^i|2|???|n貝9FIRST(i)nFIRST(j)=(ij)對文法中的每個非終結(jié)符 A,若它存在某個候選首符集包含，則 FIRST(i)nFOLLOW(A)二i=1,2,...,n 如果一個文法G滿足以上條件，則稱該文法G為LL(1)文法。LL(1)文法分析表的構(gòu)造與運(yùn)用這類題目，主要就是判斷文法是否滿足LL(1)文法的三個充要條件，分為以下幾步：首先將文法分解，判斷是否有左遞歸好，有的話肯定不是 LL(1)文法；算非終結(jié)符的First集合和Follow集合，具體方法請參見期中考試的提綱，其*實(shí)最本質(zhì)的要抓住first集合是Ua…，F(xiàn)ollow集合石…Ua…即可。算Select集合，書上沒有提到Select集合，計(jì)算Select集合實(shí)質(zhì)就是計(jì)算First()，當(dāng)然考試時(shí)不一定非要寫成Select集合形式，可以直接計(jì)算First()來判斷交集是否為空，從而是否為LL(1)文法，請看考題1。至于判斷一個句子的分析過程，大家注意一下，所給的句子不一定是能通過該文法分析出來的，實(shí)際上在分析之前可以自己根據(jù)文法推推看，請看考題1.分析表中沒有填的空格代表出錯，如果分析時(shí)遇到了代表該句子不符合該文法?？碱}1：判斷下面文法是否為LL(1)文法，若是，請構(gòu)造相應(yīng)的LL(1)分析表并分析句子aabe的分析過程。(15分)StaDD^STe|￡ T^bMMRbHHRM|￡分析：判斷一個文法是否為LL(1)文法是否為LL(1)文法，主要就是判斷是否滿足LL(1)文法的充要條件，有一個不滿足就不是LL(1)文法。對于aabe根據(jù)文法

SaDaSTeaaDTeaaTeaabM由于M不能為空字￡，所以最后肯定推不出來，也就是該句子不能由該文法推出，出錯。當(dāng)然一般題目都是LL(1)文法，否則題目就不好往下做，沒有意義答：(1)經(jīng)分析該文法無左遞歸；(2)①非終結(jié)符的First和Follow集合如下表所示非終結(jié)符XFirst(X)Follow(X)Sa#bD￡a#bTbeMbeH￡be②將文法分解為： S—aDD—SteDT—bMM—bHH—MH依次計(jì)算:First(aD)二{a}First(Ste)二{a}Follow(D)={#b}First(bM)=First(bH)=First(M)=Follow(H)={e}■/First(Ste)AFollow(D)=①First(M)AFollow(H)=①???該文法是LL(1)文法LL(1)分析表如下：abe#SS—aDDD—STeD^￡D^￡

TTtbMMMTbHHHTM⑶aabe的分析過程如下:步驟符號棧輸入串所用產(chǎn)生式0#saabe#1#Daaabe#StaD2#Dabe#3#eTSabe#DTSTe4#eTDaabe#5#eTDbe#6#eTbe#D^e7#eMbbe#TtbM8#eMe#出錯考題2:判斷下面文法是不是 LL(1)文法，若是請構(gòu)造相應(yīng)的 LL(1)分析表，寫出aaabd的分析過程。StaHHtaMd|dMAb|AaM|e答：(1)可以判斷該文法無左遞歸。將文法分解為分解： StaHHtaMdHtdMtAbMtataMAte求First和Follow集合非終結(jié)符XFirst(X)Follow(X)sa#

Ha,d#M,a,ed,bAa,eb求Select集合Select(S—aH)二First(aH)二{a}Select(H —aMd)二First(aMd)二{a}Select(H—d)=3hv7onjSelect(M—Ab)=First(Ab)={a,e}Select(M—)=First()UFollow(M)二Follow(M)二{d,b}Select(A—aM)=First{aM}={a}Select( A—e)=First(e)={e}■/Select(H—aMd)ASelect(H—d)=①Select(M—Ab)ASelect(M—e)=①Select(A—aM)ASelect(A—e)=①???該文法是LL⑴文法。(3)LL(1)分析表如下:adbeSS—aHHaMddMM—AbM—M—AbAA—aMA—eaaabd#的分析過程如下:步驟符號棧輸入串所用產(chǎn)生式0#Saaabd#1#Haaaabd#S—aH

2#Haabd#3#dMaaabd#HTaMd4#dMabd#5#dbAabd#MTAb6#dbMaabd#AtaM7#dbMbd#8#dbbd#MT9#dd#10##考題3:構(gòu)造LL(1)分析方法的總控流程圖6、構(gòu)造遞歸下降識別程序這類題目首先看文法有無左遞歸和左公因子，有的話一定要消除，我期中給大家的答案錯了，考題1為更正后的答案?？碱}1:為文法G[E]:ETV|V+EVTN|N[E]Ni構(gòu)造遞歸下降識別程序(10分)解：(1)提取左公因子:解：(1)提取左公因子:EtVEE'T+E|VTNVV'T[E]|構(gòu)造遞歸下降識別程序PROCEDURE；BEGINV；PROCEDURE；BEGINV； E'END;PROCEDURE;IFSYM二’+'THENBEGINADVANC；PROCEDUREV;BEGINN;V'END;ENDPROCEDURE；PROCEDURE；FPROCEDURE；NIFSYM=‘IFSYM=‘['THENIFSYM‘=i'THENBEGINADVANCEADVANCE;ELSEERROR;E；IFSYM=‘]'THENADVANCEELSEERRORENDELSEERROR;考題2:為文法G[E]:EtE+T|TTT*F|FF(E)|i構(gòu)造遞歸下降識別程序解：(1)消除左遞歸：EtTE Et+TE| TtFT Tt*FT| Ft(E)|i(2)構(gòu)造遞歸下降識別程序PROCEDURE；EPROCEDURE；EBEGINT ；EEND；PROCEDURE；EIFSYM=‘+'PROCEDURE；TBEGINF；TENDPROCEDURE；TIFSYM=‘*PROCEDURE；FIFSYM=‘i'THENADVANCEELSEIFSYM=‘('THENTHENTHENBEGIN

THENTHENBEGINBEGINADVANC；BEGINADVANC；ET ；EENDBEGINADVANCEF；TENDE；IFSYM‘=)'THENADVANCEELSEERRORENDELSEERROR;7、自底向上分析法一一LR(0)分析法注：自底向上分析法本質(zhì)是從輸入串開始，逐步進(jìn)行“歸約”，直到文法的開始符號,其關(guān)鍵問題是尋找句柄。自底向上分析法還有算符優(yōu)先分析法， SLR(1),LR(1)等等，老師那天重點(diǎn)講了一道LR(0)分析法的題目，他說算符優(yōu)先分析法A卷不考，但是補(bǔ)考的B卷會考，按照他的意思，這次期末考試LR(0)是考定的了，SLR(1),LR(1)應(yīng)該不考，因?yàn)長R(0)分析法個人感覺也是所有題目中最繁的了，下面已老師講的題目為例這，也是一份試卷上的考題，首先介紹一些相關(guān)知識。LR(0)項(xiàng)目：通俗點(diǎn)講，文法G中的任何一個產(chǎn)生式的右部的任何位置添加一個圓點(diǎn)就成了LR(0)項(xiàng)目，比如AtAb是產(chǎn)生式，則A-AbA^AbAAb都是該產(chǎn)生式對應(yīng)的全部項(xiàng)目。項(xiàng)目動態(tài)的表示歸約的一個階段：對于項(xiàng)目A-Ab,可以這樣理解它：“”之前的 A表示的是在識別Ab過程中已輸入到棧終的部分；“”之后的表示在識別Ab過程中期望出現(xiàn)的部分；“”表示則是在識別Ab過程中當(dāng)前的識別進(jìn)度的定位。項(xiàng)目 A-Ab已經(jīng)具備了識別Ab的一切條件，因此被稱為歸約項(xiàng)目項(xiàng)目可以分為以下四類：P^aaB稱為移進(jìn)項(xiàng)目其中,P~aXB稱為待約項(xiàng)目，其中X為非終結(jié)符，P^a稱為歸約項(xiàng)目，S'tS稱為接收項(xiàng)目LR(O)的分析棧可以看成兩部分狀態(tài)棧LR分析器的核心是一張分析表：ACTION[s,a]:當(dāng)狀態(tài)s面臨輸入符號a時(shí)，應(yīng)采取什么動作GOTO[sX]:狀態(tài)s面對文法符號X時(shí)，下一狀態(tài)是什么.F面幾張PPT大家看看，對基本概念有個印象:這一章的概念較多較抽象，我一時(shí)半會也講不完講不清楚，這里不再贅述，直接看題目，知道怎么做就行，下面以一道考題這也是老師講的原題為例講解如何做這類題目，首先一般這種題目分三步走：拓廣文法：假定文法G是一個以S為幵始符號的文法，我們構(gòu)造一個G,它包含了整個G,但它引進(jìn)了一個不出現(xiàn)在G中的非終結(jié)符S，并加進(jìn)一個新產(chǎn)生式StS,而這個S是G的幵始符號。那么，我們稱G是G的拓廣文法。這樣，便會有一個僅含項(xiàng)目StS.的狀態(tài)，這就是唯一的“接受”態(tài)。構(gòu)造識別文法活前綴的DFA:對于任意的項(xiàng)目即I,其閉包CLOSURE(I)計(jì)算方法如下，I中的所有項(xiàng)目都屬于CLOSURE(I);如果PTaXB,并且X為非終結(jié)符，貝V所有形如X-丫的項(xiàng)目也屬于CIOSURE(I)定義函數(shù)GO(I,X)，其中I是項(xiàng)目集，X是任意的文法符號(終結(jié)符，非終結(jié)符都可以),GO(I,X)=CLOSURE(J).J是從I中項(xiàng)目出發(fā)后讀取X后到達(dá)的后繼項(xiàng)目，即J={PfaXp|PfaXp€I}有了上述CLOSUR和GO的定以后，從CLOSURESfS})出發(fā)，利用GO函數(shù)，產(chǎn)生出它在每個可能的文法符號下，要轉(zhuǎn)移的項(xiàng)目集，再對新產(chǎn)生的項(xiàng)目集采取同樣的方法直到?jīng)]有新產(chǎn)生的項(xiàng)目集未被處理為止。根據(jù)計(jì)算出的項(xiàng)目集之間的關(guān)系畫出 DFA和LR(0)分析表，其中LR(0)構(gòu)造方法如下:對具體的句子運(yùn)用LR(0)分析的方法如下：每一項(xiàng)ACTION[s，a]所規(guī)定的四種動作:移進(jìn)把(s，a)的下一狀態(tài)s'和輸入符號a推進(jìn)棧，下一輸入符號變成現(xiàn)行輸入符號.歸約指用某產(chǎn)生式Afp進(jìn)行歸約.假若p的長度為r，歸約動作是，去除棧頂r個項(xiàng)，使?fàn)顟B(tài)sm-r變成棧頂狀態(tài)，然后把(sm-r,A)的下一狀態(tài)s'=GOTO[sm-r,A]和文法符號A推進(jìn)棧.接受(即acc)宣布分析成功，停止分析器工作.報(bào)錯考題：構(gòu)造文法G[E]的LR(0)分析表，并給出accd的分析過程。(0)SfE(1) EfaA (2) EfbB (3) AfcA (4)Afd (5) BfcB (6)Bfd分析：題中已經(jīng)進(jìn)行了推廣文法，所以第一步就不需要了，下面就是開始構(gòu)造識別活前綴的DFA然后構(gòu)造出LR(0)分析表，最后在進(jìn)行分析，實(shí)際上對于 accd我們自己可以先推一下，EaAacAaccAaccd所以該句子符合文法，那么最終構(gòu)造出的

LR(0)分析表對該句子進(jìn)行分析后必定得到 “acc”(接受的意思)，否則構(gòu)造的LR(0)分析表出錯。答：(1)構(gòu)造識別活前綴的DFA:I1=GO(I0,E)=Closure({S—E})={S—E}I2=GO(I0,a)=Closure({E—aA})={E—aA，A—cA，A—d}I3=GO(I0,b)=Closure({E—bB})={E—bB,B—cB，B—d}(為了方便，下面計(jì)算中的Closure不再寫了，直接給出答案,考試時(shí)可以不寫，Io=Closure({S^E})={S—E,1aA,1bB}當(dāng)然計(jì)算I0是必須要的)I4=GO(I2,A)={E—aA}I5=GO(I2,c)={A—cA，A—cA，A—d}I6=GO(I2,d)={A—d}I7=GO(I3,B)={E—bB}I8=GO(I3,c)={B—cB，B—cB，B—d} I9=GO(I3,d)={B—d}I10=GO(I5,A)={A—cA}GO(I5,c)=I5GO=I6I11=GO(I8,B){B—cB}GO(I8,c)=I8GO=I9畫出DFA:表(2)畫出LR(0)表(2)畫出LR(0)分析表注：至于怎么填這個表請參見上一頁中的跳轉(zhuǎn)到第i個狀態(tài)，ri代表選擇文法中第析成功。Goto表中數(shù)字i代表跳轉(zhuǎn)到第iPPT，這里不再贅述，Action表中si代表i條規(guī)則進(jìn)行歸約,acc代表接受，即分個狀態(tài)。對accd#進(jìn)行分析步驟分析棧輸入串操作1#0accd#s22#0a2ccd#s53#0a2c5cd#s54#0a2c5c5d#s65#0a2c5c5d6#r46#0a2c5c5A10#r37#0a2c5A10#r38#0a2A4#r19#0E1#acc8、寫出表達(dá)式或者程序的中間形式逆波蘭式和四元式是三地址代碼的兩種記錄表現(xiàn)形式，當(dāng)然表示形式還有三元式、間接三元式等等，根據(jù)老師的意思應(yīng)該不考，四元式和逆波蘭式必考。(1)逆波蘭表達(dá)式逆波蘭表達(dá)式即后綴表達(dá)式，就是中綴表達(dá)式(也就是我們一般看到的表達(dá)式形式)對應(yīng)的后續(xù)遍歷結(jié)果，這個方法有很多，個人認(rèn)為搞清楚運(yùn)算優(yōu)先級，觀察一下就可寫出，先算誰就將其對應(yīng)的操作數(shù)寫出，運(yùn)算符放在后面就行很簡單：例如：寫出下列各式的逆波蘭表示(1) -a-(b*c/(c-d)+(-b)*a)(2) -A+B*C(D/E)/F解：(1)a@bc*cd-/b@a*+- (2)A@BCDE/*F/+注：@代表負(fù)號“-”

2）四元式四元式形式如下(op,arg1,arg2,Result)從左至右分別代表運(yùn)算符，第一操作數(shù)，第二操作數(shù),運(yùn)算結(jié)果。如：A+B*(C-D)+E/(C-D)AN 對應(yīng)的四元式序列如下:四元式:(1)(-,C,D,T1) (2)(*,B,T1,T2)(+,A,T2,T3) (4)(-,C,D,T4)(5)(A,T4,N,T5) (6)(/,E,T5,T6)(7)(+,T3,T6,T7)注：T1,T2等等位存放結(jié)果的臨時(shí)變量。條件語句等四元式的表示jnz,jnz,a,--,p)表示ifagoto(jrop,x,y,p)(jrop,x,y,p)表示ifxropygotoprop代表關(guān)系運(yùn)算符，如<,>等等）表示goto四元式序列(j,--,---,p表示goto四元式序列例如：寫出條件語句IFa>0THENx:=x+1ELSEx:=4*(x-1)解：(1)(j>,a,0,(3))(2)(j,-,-,(6))(+,x,1,T1)(:=,T1,-,T2)(j,-,-,(9))(-,x,1,T3)⑺（*,4,T3,T4）（8） （:二,T4,-,x）（9）注意：（5）和（9）不能寫丟，否則一分沒有！上述四元式中第二第三個位置的“-”代表沒有元素。其實(shí)四元式就是對上述程序進(jìn)行解釋，如果滿足則跳轉(zhuǎn)到哪里執(zhí)行，不滿足則跳轉(zhuǎn)到哪里執(zhí)行，大家自己分析一下，應(yīng)該能夠看懂?？碱}：根據(jù)要求寫出下列表達(dá)式的中間形式。（1）5+6*（a+b）寫出表達(dá)式的逆波蘭式 逆波蘭表達(dá)式為：56ab+*+（2）答案（1）答案（2）ifx>ythen{(0)(j>,x,y,(2))100:ifx>ygotoy：=y-i;(1)(j,-,-,(8))102x :(2)(-,y,1,T1)101:goto108=y*z+10(3)(:=,T1,-,y)102:T1:=y-1}(4)(*,y,z,T2)103:y:=T1else(5)(+,T2,10,T3)104:T2:=y*zx:=z+(6)(:=,T3,-,x)105:T3:=T2+10y(7)(j,-,-,(10))106:x:=T3寫出上述代碼的四元式(8)(+,z,y,T4)107:goto110或者三址碼。(9)(:=,T4,-,x)108:T4:=z+y傳名傳遞時(shí)輸出結(jié)果為： 傳名傳遞時(shí)輸出結(jié)果為： 9(a=a+1 ；a=a+a+b;得到a=2+1=3;a=3+3+3=9)} cout?"lnmain"vvavvendl;} cout?"lnmain"vvavvendl;（有的試卷上冋法是與(10)109:x:=T4出下列表達(dá)式三地址形110:式的中間表示，答案一樣）注意：同上題，本題答案加紅色的部分此外上述編號隨意，從 0幵始也行從100幵始也行。不能丟，否則一分沒有！9、參數(shù)傳遞這種題目很簡單，是送分題，一定要做對！參數(shù)傳遞方式分為三種，值傳遞，地址傳遞和傳名。值傳遞過程中形參值的改變不會影響實(shí)參值的改變， 地址傳遞形參值的改變導(dǎo)致對應(yīng)是實(shí)參值的改變，傳名傳遞類似于C語言中的宏展幵，將實(shí)參原封不動的替換相應(yīng)的形參（文字替換）。請看下題：（1）高級語言程序中常用的