編譯原理習題(后)

第一章1、將編譯程序分紅若干個“遍”是為了。a．提升程序的履行效率b．使程序的結(jié)構(gòu)更為清楚c．利用有限的機器內(nèi)存并提升機器的履行效率d．利用有限的機器內(nèi)存但降低了機器的履行效率2、結(jié)構(gòu)編譯程序應(yīng)掌握。a．源程序b．目口號言c．編譯方法d．以上三項都是3、變量應(yīng)該。a．擁有左值b．擁有右值c．既擁有左值又擁有右值d．既不擁有左值也不擁有右值4、編譯程序絕大部分時間花在上。a．犯錯辦理b．詞法剖析c．目標代碼生成d．管理表格5、不行能是目標代碼。a．匯編指令代碼b．可重定位指令代碼c．絕對指令代碼d．中間代碼6、使用能夠定義一個程序的意義。a．語義規(guī)則b．語法例則c．產(chǎn)生規(guī)則d．詞法例則7、詞法剖析器的輸入是。a．單詞符號串b．源程序c．語法單位d．目標程序8、中間代碼生成時所依照的是-。a．語法例則b．詞法例則c．語義規(guī)則

d．等價變換規(guī)則9、編譯程序是對

。a．匯編程序的翻譯

b．高級語言程序的解說履行c．機器語言的履行

d．高級語言的翻譯10、語法剖析應(yīng)依照

。a．語義規(guī)則

b．語法例則c．構(gòu)詞規(guī)則

d．等價變換規(guī)則二、多項選擇題1、編譯程序各階段的工作都波及到a．語法剖析b．表格管理d．語義剖析e．詞法剖析2、編譯程序工作時，往常有階段。a．詞法剖析b．語法剖析d．語義檢查e．目標代碼生成

。

c．犯錯辦理c．中間代碼生成三、填空題成。

1、解說程序和編譯程序的差別在于2、編譯過程往?？煞譃?個階段，分別是3、編譯程序工作過程中，第一段輸入是

。

、語法剖析、代碼優(yōu)化和目標代碼生，最后階段的輸出為程序。4、編譯程序是指將程序翻譯成程序的程序。單項選擇解答1、將編譯程序分紅若干個“遍”是為了使編譯程序的結(jié)構(gòu)更為清楚，應(yīng)選b。2、結(jié)構(gòu)編譯程序應(yīng)掌握源程序、目口號言及編譯方法等三方面的知識，應(yīng)選d。3、對編譯而言，變量既擁有左值又擁有右值，應(yīng)選c。4、編譯程序打交道最多的就是各樣表格，所以選

d。5、目標代碼包含匯編指令代碼、可重定位指令代碼和絕對指令代碼

3種，所以不是目標代碼的只好選d。6、詞法剖析依照的是構(gòu)詞規(guī)則，語法剖析依照的是語法例則，中間代碼生成依照的是語義規(guī)則，而且語義規(guī)則能夠定義一個程序的意義。所以選a。7、b8、c9、d10、c多項選擇解答1．b、c2.a、b、c、e填空解答能否生成目標程序

2、詞法剖析

中間代碼生成

3、源程序目標代碼生成

4、源程序

目口號言第二章一、單項選擇題1、文法G：S→xSx|y所識其余語言是。a.xyxb.(xyx)*c.xnyxn(n≥0)d.x*yx*2、文法G描繪的語言L(G)是指。a.L(G)={α|S+α,α∈VT*}b.L(G)={α|S*α,α∈Vc.L(G)={α|S*α,α∈(VTNd.L(G)={α|S+α,α∈(VTN∪V*)}∪V*)}3、有限狀態(tài)自動機能辨別。a.上下文沒關(guān)文法b.上下文有關(guān)文法c.正規(guī)文法d.短語文法4、設(shè)G為算符優(yōu)先文法，G的隨意終結(jié)符對a、b有以下關(guān)系成立。a.若f(a)>g(b)，則a>bb.若f(a)<g(b)，則a<bc.a~b都不必定成立d.a~b必定成立5、假如文法G是無二義的，則它的任何句子α。最左推導和最右推導對應(yīng)的語法樹必然同樣最左推導和最右推導對應(yīng)的語法樹可能不一樣最左推導和最右推導必然同樣可能存在兩個不一樣的最左推導，但它們對應(yīng)的語法樹同樣6、由文法的開始符經(jīng)0步或多步推導產(chǎn)生的文法符號序列是a.短語b.句柄c.句型d.句子7、文法G：E→E+T|T

。T→T*P|PP→(E)|I則句型P+T+i的句柄和最左素短語為。+T和ib.P和P+Tc.i和P+T+i8、設(shè)文法為：S→SA|AA→a|b則對句子aba，下邊是規(guī)范推導。

和

TSSASAAAAAaAAabAabaSSASAAAAAAAaAbaabaSSASAASAaSbaAbaabaSSASaSAaSbaAbaaba9、文法G：S→b|∧(T)T→T,S|S則FIRSTVT(T)。a.{b,∧,(}b.{b,∧,)}c.{b,∧,(,，}d.{b,∧,),，}10、產(chǎn)生正規(guī)語言的文法為。a.0型b.1型c.2型d.3型11、采納自上而下剖析，一定。a.除去左遞歸b.除去右遞歸c.除去回溯d.提取公共左因子12、在規(guī)范歸約中，用來刻畫可歸約串。a.直接短語b.句柄c.最左素短語d.素短語13、有文法G：E→E*T|TT→T+i|i句子1+2*8+6按該文法G歸約，其值為。14a.23B.42c.30d.17、規(guī)范歸約指。a.最左推導的逆過程b.最右推導的逆過程c.規(guī)范推導d.最左歸約的逆過程二、多項選擇題1、下邊哪些說法是錯誤的。a.有向圖是一個狀態(tài)變換圖b.狀態(tài)變換圖是一個有向圖c.有向圖是一個DFA能夠用狀態(tài)變換圖表示2、對無二義性文法來說，一棵語法樹常常代表了。a.多種推導過程b.多種最左推導過程c.一種最左推導過程d.僅一種推導過程e.一種最左推導過程3、假如文法G存在一個句子，知足以下條件之一時，則稱該文法是二義文法。該句子的最左推導與最右推導同樣該句子有兩個不一樣的最左推導該句子有兩棵不一樣的最右推導該句子有兩棵不一樣的語法樹e.該句子的語法樹只有一個4、有一文法G：S→ABA→aAb|εB→cBd|ε它不產(chǎn)生下邊

會合。a.{anbmcndm|n,m

≥0}

b.{anbncmdm|n,m>0}c.{anbmcmdn|n,m

≥0}

d.{anbncmdm|n,m

≥0}e.{anbncndn|n

≥0}5、自下而上的語法剖析中，應(yīng)從開始剖析。a.句型b.句子c.以單詞為單位的程序d.文法的開始符e.句柄6、對正規(guī)文法描繪的語言，以下有能力描繪它。型文法型文法c.上下文沒關(guān)文法d.右線性文法e.左線性文法三、填空題1、文法中的終結(jié)符和非終結(jié)符的交集是。詞法剖析器交給語法剖析器的文法符號必定是，它必定只出此刻產(chǎn)生式的部。2、最左推導是指每次都對句型中的非終結(jié)符進行擴展。3、在語法剖析中，最常有的兩種方法必定是剖析法，另一是剖析法。4、采納語法剖析時，一定除去文法的左遞歸。5、樹代表推導過程，樹代表歸約過程。6、自下而上剖析法采納、歸約、錯誤辦理、等四種操作。7、Chomsky把文法分為種種類，編譯器結(jié)構(gòu)中采納和文法，它們分別產(chǎn)生和語言，并分別用和自動機辨別所產(chǎn)生的語言。四、判斷題1、文法S→aS|bR|ε描繪的語言是(a|bc)*()R→cS2、在自下而上的語法剖析中，語法樹與剖析樹必定同樣。（）3、二義文法不是上下文沒關(guān)文法。（）4、語法剖析時一定先除去文法中的左遞歸。（）5、規(guī)范歸約和規(guī)范推導是互逆的兩個過程。（）6、一個文法全部句型的會合形成該文法所能接受的語言。（）五、簡答題1、句柄

2、素短語

3、語法樹

4、歸約

5、推導六、問答題1、給出上下文沒關(guān)文法的定義。2、文法G[S]：S→aSPQ|abQQP→PQbP→bbbQ→bccQ→c1）它是Chomsky哪一型文法2）它生成的語言是什么3、按指定種類，給出語言的文法。L={aibj|j＞i≥1}的上下文沒關(guān)文法。4、有文法G：S→aAcB|BdA→AaB|cB→bScA|b1）試求句型aAaBcbbdcc和aAcbBdcc的句柄；2）寫出句子acabcbbdcc的最左推導過程。5、對于文法G[S]：S→（L）|aS|aL→L,S|S（1）畫出句型（S,（a））的語法樹。（2）寫出上述句型的全部短語、直接短語、句柄和素短語。6、考慮文法G[T]：T→T*F|FF→F↑P|PP→（T）|i證明T*P↑（T*F）是該文法的一個句型，并指出直接短語和句柄。單項選擇[解答]1、選c。2、選a。3、選c。4、固然a與b沒有優(yōu)先關(guān)系，但結(jié)構(gòu)優(yōu)先函數(shù)后，a與b就必定存在優(yōu)先關(guān)系了。所以，由f(a)>g)(b)或f(a)<g(b)其實不可以判斷本來的a與b之間能否存在優(yōu)先關(guān)系：應(yīng)選c。5、假如文法G無二義性，則最左推導是先生長右側(cè)的枝葉：對于d，假如有兩個不一樣的是了左推導，則必然有二義性。應(yīng)選a。6、選c。E7、由圖2-8-1的語法樹和優(yōu)先關(guān)系能夠看出應(yīng)選b。E+FE+TPTiP#<·+·>+<·i·>#圖2-8-1句型P+T+I的語法及優(yōu)先關(guān)系8、規(guī)范推導是最左推導，應(yīng)選d。9、由T→T,和T→(得FIRSTVT(T))={(,，)}；由T→S得FIRSTVT(S)FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即10、d

FIRSTVT(T)={b,∧,(,，}；所以選c。11、c12、b13、b14、b多項選擇解答

1、e、a、c

2、a、c、e

3、b、c、d

4、a、c

5、b、c

6、a、b、c、d、e填空解答

1、空集

終結(jié)符

右2、最左3、自上而上自下而上4、自上而上5、語法剖析6、移進接受7、42型3型上下文沒關(guān)語言判斷解答1、對2、錯3、錯4、錯

正規(guī)語言5、錯6、錯

下推自動機

有限簡答[解答]1、句柄：一個句型的最左直接短語稱為該句型的句柄。2、素短語：起碼含有一個終結(jié)符的素短語，而且除它自己以外不再含任何更小的素短語。3、語法樹：知足下邊4個條件的樹稱之為文法G[S]的一棵語法樹。①每一終結(jié)均有一標志，此標志為VN∪VT中的一個符號；②樹的根結(jié)點以文法G[S]的開始符S標志；VN中的一個符號；③若一結(jié)點起碼有一個直接后繼，則此結(jié)點上的標志為④若一個以A為標志的結(jié)點有K個直接后繼，且按從左至右的次序，這些結(jié)點的標志分別為X12K12K,X,,X，則A→X,X,,X，必然是G的一個產(chǎn)生式。4、歸約：我們稱αγβ直接歸約出αAβ，僅當A→γ是一個產(chǎn)生式，且α、β∈NT(V∪V)*。歸約過程就是從輸入串開始，頻頻用產(chǎn)生式右部的符號替代成產(chǎn)生式左部符號，直至文法開始符。5、推導：我們稱αAβ直接推出αγβ，即αAβαγβ，僅當A→γ是一個產(chǎn)生式，且α、β∈(VN∪VT)*。假如α1α2αn，則我們稱這個序列是從α1至α2的一個推導。若存在一個從α1αn的推導，則稱α1可推導出αn。推導是歸約的逆過程。問答1[解答]G是一個四元式（VT,VN,S,P），此中：一個上下文沒關(guān)文法●TV是一個非空有限集，它的每個元素稱為終結(jié)符號；VT∩VN=Φ；●VN是一個非空有限集，它的每個元素稱為非終結(jié)符號，●S是一個非終結(jié)符號，稱為開始符號；●P是一個產(chǎn)生式會合（有限），每個產(chǎn)生式的形式是P→α，此中，P∈VN，α∈(VT∪VN)*。開始符號S起碼一定在某個產(chǎn)生式的左部出現(xiàn)一次。2[解答]1）因為產(chǎn)生式左部存在終結(jié)符號，且全部產(chǎn)生式左部符號的長度均小于等于產(chǎn)生式右部的符號長度，所以文法G[S]是Chomsky1型文法，即上下文有關(guān)文法。2）按產(chǎn)生式出現(xiàn)的次序規(guī)定優(yōu)先級由高到低（不然沒法推出句子），我們能夠獲得：SabQabcSaSPQaabQPQaabPQQaabbQQaabbcQaabbccSaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc于是獲得文法G[S]生成的語言L={anbncn|n≥1}3【解答】（1）由L={aibj|j＞i≥1}知，所求該語言對應(yīng)的上下文沒關(guān)文法第一應(yīng)有S→aSb型產(chǎn)生式，以保證b的個數(shù)許多于a的個數(shù)；其次，還需有S→Sb或S→bS型的產(chǎn)生式，用以保證b的個數(shù)多于a的個數(shù)；也即所求上下文沒關(guān)文法G[S]為：G[S]：S→aSb|Sb|b4【解答】（1）分別畫出對應(yīng)兩句型的語法樹，如圖2-8-2所示句柄:AaBBdSSaAcBaAcBAaBbScABd

c

BScBd

Acb(b)(a)圖2-8-2語法樹2）句子acabcbbdcc的最左推導以下：SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcAacabcbbdcAacabcbbdcc5【解答】S（1）句型（S,（a））的語法樹如圖2-8-3所示（L）L，SS(L)（2）由圖2-8-3可知：S①短語：S、a、(a)、S,(a)、(S,(a))；a②直接短語：a、S；圖2-8-3句型（S,（a））的語法樹③句柄：S；④素短語：素短語可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即；#·（·，·（·a·）·）·#所以素短語為a。6【解答】T第一結(jié)構(gòu)T*P↑（T*F）的語法樹如圖2-8-4所示。由圖2-8-4可知，T*P↑（T*F）是文法G[T]的一個句型。T*FF↑P直接短語有兩個，即P和T*F；句柄為P。P（T）T*F圖2-8-4句型T*P↑（T*F）的語法樹第三章一、單項選擇題1、詞法剖析所依照的是。a.語義規(guī)則b.構(gòu)詞規(guī)則c.語法例則d.等價變換規(guī)則2、詞法剖析器的輸出結(jié)果是。a.單詞的種別編碼b.單詞在符號表中的地點c.單詞的種別編碼和自己值d.單詞自己值3、正規(guī)式M1和M2等價是指。a.M1和M2的狀態(tài)數(shù)相等b.M1和M2的有向弧條數(shù)相等c.M1和M2所識其余語言集相等d.M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等4、狀態(tài)變換圖（見圖3-6-1）接受的字集為。0X1Y0圖3-6-1a.以0開頭的二進制數(shù)構(gòu)成的會合b.以0結(jié)尾的二進制數(shù)構(gòu)成的會合c.含奇數(shù)個0的二進制數(shù)構(gòu)成的會合d.含偶數(shù)個0的二進制數(shù)構(gòu)成的會合5、詞法剖析器作為獨立的階段使整個編譯程序結(jié)構(gòu)更為簡短、明確，所以，。a.詞法剖析器應(yīng)作為獨立的一遍b.詞法剖析器作為子程序較好c.詞法剖析器分解為多個過程，由語法剖析器選擇使用d.詞法剖析器其實不作為一個獨立的階段二、多項選擇題1、在詞法剖析中，能辨別出。a.基本字b.四元式c.運算符d.逆波蘭式e.常數(shù)2、令∑={a,b}，則∑上全部以b開頭，后跟若干個ab的字的全體對應(yīng)的正規(guī)式為。a.b(ab)*b.b(ab)+c.(ba)*bd.(ba)+be.b(a|b)三、填空題1、確立有限自動機DFA是的一個特例。2、若二個正規(guī)式所表示的同樣，則認為兩者是等價的。3、一個字集是正規(guī)的，當且僅當它可由所。四、判斷題1、一個有限狀態(tài)自動機中，有且僅有一個獨一終態(tài)。（）2、設(shè)r和s分別是正規(guī)式，則有L（r|s）=L(r)|L(s)。（）3、自動機M和M′的狀態(tài)數(shù)不一樣，則兩者必不等價。（）4、確立的自動機以及不確立的自動機都能正確地辨別正規(guī)集。（）5、對隨意一個右線性文法G，都存在一個NFAM，知足L(G)=L(M)。（）6、對隨意一個右線性文法G，都存在一個DFAM，知足L(G)=L(M)。（）7、對任何正規(guī)表達式e，都存在一個NFAM，知足L(G)=L(e)。（）8、對任何正規(guī)表達式e，都存在一個DFAM，知足L(G)=L(e)。（）五、基此題1、設(shè)M＝（{x,y},{a,b},f,x,{y}）為一非確立的有限自動機，此中f定義以下：f（x,a）＝{x,y}f（x,b）＝{y}f（y,a）＝φf（y,b）＝{x,y}試結(jié)構(gòu)相應(yīng)確實定有限自動機M′。2、對給定正規(guī)式b*（d|ad）（b|ab）+，結(jié)構(gòu)其NFAM；單項選擇解答1、b2、c3、c4、d5、b多項選擇解答1、a、c、e2、a、b、d填空解答1、NFA2、正規(guī)集3、DFA（NFA）所辨別判斷解答1、2、3、錯4、5、6、7、8、正確基本1解答：比較自動機的定義M=(S,Σ,f,S0的定義可知f(x,a)、f(y,b)均為多值函數(shù)，所以是一非確立有限自動機，先畫出NFAM相應(yīng)的狀態(tài)圖，如圖3-6-2所示。aa用子集法結(jié)構(gòu)狀態(tài)變換矩陣表3-6-3所示。XYIIabIbb{x}{x,y}{y}b{y}—{x,y}{x,y}{x,y}{x,y}將變換矩陣中的全部子集從頭命名而形成表3-6-4所示的狀態(tài)變換矩陣。表3-6-4狀態(tài)變換矩陣ab0211—2222即獲得M′=（{0,1,2},{a,b},f,0,{1,2}），其狀態(tài)變換圖如圖3-6-5所示。aa,b021bb將圖3-6-5的DFAM′最小化。第一，將M′的狀態(tài)分紅終態(tài)組{1，2}與非終態(tài)組{0}；其次，觀察{1,2}。因為{1,2}a={1,2}b={2}{1,2}，所以不再將其區(qū)分了，也即整個區(qū)分只有兩組{0}，{1,2}：令狀態(tài)1代表{1,2}，即把本來抵達2的弧都導向1，并刪除狀態(tài)2。最后，獲得如圖3-6-6所示化簡DFAM′。aa,b01b2解答：第一用A+=AA*改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)*；其次，結(jié)構(gòu)該正規(guī)式的NFAM，如圖3-6-7所示。Xb*(d|ad)(b|ab)(b|abYXb*1(d|ad2(b|ab3(b|ab)*Y))b|abbdbXε4ε123ε5εYbadabbdbXε4ε123ε5εYaaab7b86d圖3-6-7的NFAM第四章1、結(jié)構(gòu)下邊文法的LL（1）剖析表。D→TLT→int|realL→idRR→,idR|ε2、下邊文法G[S]能否為LL（1）文法說明原因。S→AB|PQxA→xyB→bcP→dP|εQ→aQ|ε3、設(shè)有以下文法：G[S]：S→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|ε（1）求出該文法的每一個非終結(jié)符U的FOLLOW集。2）該文法是LL（1）文法嗎3）結(jié)構(gòu)C[S]的LL（1）剖析表。4、將文法G[V]改造成為LL(1)的。G[V]：V→N|N[E]E→V|V+EN→i5、已知文法：G[A]：A→aAa|ε1）該文法是LL（1）文法嗎為何2）若采納LL（1）方法進行語法剖析，怎樣獲得該文法的LL（1）剖析表3）若輸入符號串“aaaa”，請給出語法剖析過程。1解答：LL（1）剖析表見表4-3-1剖析固然這個文法很簡單，我們?nèi)允菑那箝_始符號會合和后繼符號會合開始。FIRST（D）=FIRST（T）={int,real}FOLLOW（D）=FOLLOW（L）={#}FIRST（L）={id}FOLLOW（T）={id}FIRST（R）={，,}εFOLLOW（R）={#}有了上邊每個非終結(jié)符的FIRST會合，填剖析表時要計算一個產(chǎn)生式右部α的FIRST（α）就不是件難事了。填表時獨一要當心的時，ε是產(chǎn)生式R→ε右部的一個開始符號，而#在FOLLOW（R）中，所以R→ε填在輸入符號#的欄目中。表4-3-1LL（1）剖析表非終結(jié)符輸入符號intrealid，#DD→TLD→TLTT→intT→realLL→idRRR→,idRR→ε2解答：該文法不是LL（1）文法，見下邊剖析中的說明。剖析只有三個非終結(jié)符有兩個選擇。1、P的兩個右部dP和ε的開始符號必定不訂交。2、Q的兩個右部aQ和ε的開始符號必定不訂交。3、對S來說，因為x∈FIRST(AB)，同時也有x∈FIRST(PQx)（因為以該文法不是LL（1）文法。3解答：（1）求文法的每一個非終結(jié)符U的FOLLOW集的過程以下：

P和

Q都可能為空）。所因為：①S是辨別符號，且有A→BSD、B→SAc、D→Se，所以FOLLOW（S）應(yīng)包含F(xiàn)IRST(D)∪FIRST(Ac)∪FIRST(e)∪{#}={a,d}∪{a,d,c,e}∪{e}∪{#}={a,c,d,e#}②又因為A→BSD和D→ε，所以FOLLOW中還包含F(xiàn)OLLOW(A)。因為S→aAbDe和B→SAc,所以FOLLOW（A）=FIRST（bDe）∪FIRST（c）={b,c}綜合①、②得FOLLOW（S）={a,d,c,e,#}∪{a,b,c,d,e,#}因為A→BSD，所以FOLLOW（B）=FIRST（SD）={a,d}因為S→aAbDe|d、A→BSD|e和B→SAc|cD，所以FOLLOW（D）=FIRST（e）∪FOLLOW（A）∪FOLLOW（B）={e}∪{b,c}∪{a,d}={a,b,c,d,e}（2）G[S]不是LL（1）文法。因為產(chǎn)生式B→SAc|cD|ε中FIRST（SAc）∩FOLLOW（B）={a,d}≠（3）結(jié)構(gòu)G[S]的LL（1）剖析表。依照LL（1）剖析表的結(jié)構(gòu)算法結(jié)構(gòu)方法G[S]的LL（1）剖析表如表表4-3-2G[S]的LL（1）剖析表

4-3-2所示。a

b

c

d

e

#S

aAbDe

dA

BSD

BSD

BSD

eB

Sac/ε

cD

Sac/εD4解答：

Se/εεε對文法G[V]提取公共左因子后獲得文法：G′[V]：V→NA

Se/ε

εA→ε|[E]E→VBB→ε|+EN→i求出文法

G′[V]中每一個非終結(jié)符號的

FIRST集：FIRST(V)={i}

FIRST(A)={[,

ε}FIRST(E)={i}

FIRST(B)={+,ε}FIRST(N)={i}求出文法

G′[V]中每一個非終結(jié)符號的

FOLLOW集：FOLLOW(V)={#}∪FIRST(B)\{ε}∪FOLLOW(E)={#,+,]}FOLLOW(A)=FOLLOW(V)={+,,#}FOLLOW(E)=FIRST(])\{ε}∪FOLLOW(B)=FIRST(])\{ε}∪FOLLOW(E)={]}FOLLOW(B)=FOLLOW(E)={]}FOLLOW(N)=FIRST(A)\{ε}∪FOLLOW(V)={[,],+,#}能夠看到，對文法G′[V]的產(chǎn)生式A→ε|[E]，有FIRST([E])∩FOLLOW(A)={[}∩{+,],#}=對產(chǎn)生式B→ε|+E，有FIRST(+E)∩FOLLOW(B)={+}∩{]}=而文法的其余產(chǎn)生式都只有一個不為ε的右部，所以文法G′[V]是LL(1)文法。5解答：（1）因為產(chǎn)生式A→aAa|ε有空產(chǎn)生式右部，而FOLLOW(A)={#}∪FIRST(a)={a,#}造成FIRST(A)∩FOLLOW(A)={A,ε}∩{a,#}≠所以該文法不是LL（1）文法。2）若采納LL（1）方法進行語法剖析，一定改正該文法。因該文法產(chǎn)生偶數(shù)（能夠為0）個a，所以獲得文法G′[A]：A→aaA|ε此時對產(chǎn)生式A→aaA|ε，有FOLLOW(A)={#}∪FOLLOW(A)={#}，因此FIRST(A)∩FOLLOW(A)={a,ε}∩{#}=所以文法G′[A]是LL（1）文法，按LL（1）剖析表結(jié)構(gòu)算法結(jié)構(gòu)該文法的LL（1）剖析表如表4-3-3所示。表4-3-3文法G′[A]的LL(1)剖析表A#AA→aaAA→ε（3）若采納LL(1)方法進行語法剖析，對符號串“aaaa”的剖析過程如表4-3-4所示。表4-3-4對符號串“aaaa”的剖析過程步驟剖析棧輸入串產(chǎn)生式/動作1#Aaaaa#A→aaA2#Aaaaaaa#般配3#Aaaaa#般配4#Aaa#A→aaA5#Aaaaa#般配6#Aaa#般配7#A#A→ε8##接受第五章1.設(shè)有文法

G[S]為：S→a|b|(A)A→SdA|S（1）

達成以下算符優(yōu)先關(guān)系表，見表表5-7-1

5-7-1，并判斷G[S]能否為算符優(yōu)先文法。算符優(yōu)先關(guān)系表a

b

(

)

d

#ab()d#2）給出句型（SdSdS）的短語、簡單短語、句柄、素短語和最左素短語。3）給出輸入串（adb）#的剖析過程。解答：1）先求文法G[S]的FIRSTVT集和LASTVT集：由S→a|b|(A)得：FIRSTVT(S)={a,b,();由A→Sd得：FIRSTVT(A)=qvkvm1r;又由A→S得：FIRSTVT(S)FIRSTVT(A)，即FIRSTVT(A)={d,a,b,(};由S→a|b|(A)得；LASTVT(S)={a,b,}};由A→dA得：LASTVT(A)=0ikgqrt,又由A→S得：LASTVT(S)LASTVT(A)，即LASTVT(A)={d,a,b,)}。結(jié)構(gòu)優(yōu)先關(guān)系表方法以下：①對P→ab，或P→aQb，有ab;②對P→aR，而b∈FIRSTVT(R)，有ab;③對P→Rb，而a∈FIRSTVT(R)，有ab。由此獲得：由S→(A)得：();②由S→(A得：(FIRSTVT(A)，即：(d,(a,(b,((;由A→dA得：dFIRSTVT(A)，即：dd,da,db,d(;③由S→A)得，LASTVT(A))，即：d),a),b),));由A→Sd得：LASTVT(S)d，即：ad,bd,)d;其余，由#S#得：##；由#FIRSTVT(S)得：#a,#b,#(；脂由LASTVT(S)#得：d#,a#,b#,)#。最后獲得算符優(yōu)先關(guān)系表，見表5-7-2。表5-7-2算符優(yōu)先關(guān)系表ab()d#ab()d#由表5-7-2能夠看出，任何兩個終結(jié)符之間起碼只知足、、三種優(yōu)先關(guān)系之一，故G[S]為算符優(yōu)先文法。（2）為求出句型（SdSdS）的短語、簡單短語、句柄，我們先畫出該句型對應(yīng)的語法樹，如圖5-7-3所示。由圖5-7-3獲得：短語：S，SdS，SdSdS，（SdSdS）簡單短語（即直接短語）：S句柄（即最左直接短語）：S素短語：SdS，它同時也是該句型的最左素短語。

S（A）SdASdAS（3）輸入串（adb）#的剖析過程見表5-7-4圖5-7-3句型（SdSdS）的語法樹表5-7-4輸入串（adb）#的剖析過程符號棧輸入串說明#(adb)#移進#（adb)#移進#（adb)#用S→a歸約#（Sdb)#移進#（Sdb)#移進#（Sdb)#用S→b歸約#（SdS)#用A→S歸約#（SdA)#用A→SdA歸約#（A)#移進#（A）#用S→（A）歸約#S#剖析成功第六章一、單項選擇題1、若a為終結(jié)符，則A→α·aβ為項目a.歸約b.移進c.接受d.待約2、若項目集Ik含有A→α·，則在狀態(tài)k時，僅當面對的輸入符號a∈FOLLOW(A)時，才采納“→α·”動作的必定是。文法（0）文法（1）文法（1）文法3、就文法的描繪能力來說，有。a.SLR（1）LR（0）b.LR（1）LR（0）c.SLR（1）LR（1）d.無二義文法LR（1）4、在LR（0）的ACTION子表中，假如某一行中存在標志“rj”的欄，則。a.該行必然填滿rjb.該行未填滿rj

Ac.其余行也有rj子表中也有rj5、一個指了然在剖析過程中的某時刻所能看到產(chǎn)生式多大一部分。a.活前綴b.前綴c.項目d.項目集二、多項選擇題1、一個LR剖析器包含。a.一個總控程序b.一個項目集c.一個活前綴d.一張剖析表e.一個剖析棧2、LR剖析器核心部分是一張剖析表，該表包含等子表。(1)剖析b.優(yōu)先關(guān)系3、每一項ACTION[S，a]所規(guī)定的動作包含。a.移進b.比較c.接受d.歸約e.報錯4、對LR剖析表的結(jié)構(gòu)，有可能存在動作矛盾。a.移進b.歸約c.移進/歸約d.移進/移進e.歸約/歸約5、就文法的描繪能力來說，有。a.SLR（1）LR（1）b.LR（1）SLR（1）c.LR（0）LR（1）6、對LR剖析器來說，存在平剖析表的結(jié)構(gòu)方法。0）（1）（0）（1）7、自上而下的語法剖析方法有。a.算符優(yōu)先剖析法（1）剖析法（0）剖析法（1）剖析法

（1）剖析法三、填空題1、對于一個文法，假如能夠結(jié)構(gòu)

。使得它的

均是獨一確立的，則稱該文法為

LR文法。2、字的前綴是指該字的。3、活前綴是指的一個前綴，這類前綴不含以后的任何符號。4、在LR剖析過程中，只需的已掃描部分保持可歸約成一個，則掃描過的部分正確。5、將識其余NFA確立化，使其成為認為狀態(tài)的DFA，這個DFA就是成立的基礎(chǔ)。6、A→α·稱為項目；對文法開始符S′→α·為項目；若

a為終結(jié)符，則稱

A→α·

aβ為項目；若B為非終結(jié)符，則稱A→α·aβ為項目。7、LR（0）剖析法的名字中“

L”表示

，“R”表示

，“0”表示

。四、綜合題1、對于文法G[S]：S→AS|bA→SA|a1）列出全部LR（0）項目2）列出構(gòu)成文法LR（0）項目集規(guī)范族。單項解答：1、A→α·稱為歸約項目，對文法開始符S′的歸約項目，如S′→α·稱為接受項目，A→α·aβ（a為終結(jié)符）稱為移進項目。在此選b.2、當用產(chǎn)生式A→α歸約時，LR（0）不論面對什么輸入符號都進行歸約；SLR（1）則僅當面臨的輸入符號a∈FOLLOW(A)時進行歸約；LR（1）則當在把α歸約為A的規(guī)范句型的前綴βAa前提下，當α后跟終結(jié)符a時，才進行歸約；所以選d。3、因為LR（0）SLR（1）LR（1）無二義文法，應(yīng)選c。4、選a。5、選c。多項選擇解答：1、一個LR剖析器包含一個總控程序和一張剖析表，選a、d。2、選c、e。3、選a、c、d、e。4、在LR剖析表的結(jié)構(gòu)中有可能存在“移進”/“歸約”和“歸約”/“歸約”矛盾；應(yīng)選c、e。5、選a、b、c、d、e。6、選a、b、c、e。7、選a、c、d、e。填空解答：1、一張剖析表每個進口2、隨意首部3、規(guī)范句型句柄4、輸入串活前綴5、活前綴項目會合LR剖析算法6、歸約接受移進待約7、自左至右剖析采納最右推導的逆過程即最左歸約向右查察0個字符綜合解答：G拓廣為G[S′]：第一將文法S′→SS→AS|bA→SA|a（1）文法G[S′]的1、S′→·S2、S′→S·3、S→·AS4、S→A·S

LR（0）項目是：5、S→AS·6、S→·b7、S→b·8、A→·SA

9、A→S·A10、A→SA·11、A→·a12、A→a·2、列出構(gòu)成文法LR（0）項目集規(guī)范族。用ε-CLOSURE（閉包）方法結(jié)構(gòu)文法G′的LR（0）項目集規(guī)范族以下：I0：1、S′→·SI3：9、A→S·AI6：12、A→a·3、S→·AS8、A→·SAI7：7、S→b·8、A→·SA

3、S→·AS11、A→·a6、S→·b

6、S→·b11、A→·aI1：2、S′→S·

I4：10、A→SA·9、A→S·A

4、S→A·S8、A→·SA

3、S→·AS11、A→·a

6、S→·b3、S→·AS6、S→·b

8、A→·SA11、A→·aI2：4、S→A·S

I5：

5、S→AS·3、S→·AS

9、A→S·A6、S→·b8、A→·SA

8、A→·SA11、A→·a11、A→·a

3、S→·AS6、S→·b注意：I1中的S′→S·和A→·SA是由狀態(tài)I0中的1和3讀入一個S字符后獲得的下一個項目；，而I4中的A→SA和A→A·S則是由I3中的9和3讀入一個A字符后獲得的下一個項目；I5中的S→AS·和A→S·A則是由I中的4和8讀入一個S字符后獲得的下一個項目。4G′的LR（0）規(guī)范族。狀態(tài)全體構(gòu)成了文法第七章一、單項選擇題1、中間代碼生成所依照的是。a.語法例則b.詞法例則c.語義規(guī)則d.等價變換規(guī)則2、四元式之間的聯(lián)系是經(jīng)過實現(xiàn)的。a.指示器b.暫時變量c.符號表d.程序變量3、后綴式ab+cd+/可用表達式來表示。+b/c+db.(a+b)/(c+d)+b/(c+d)+b+c/d4、表達式（┓A∨B）∧（C∨D）的逆波蘭表示為。a.┓AB∨∧CD∨b.A┓B∨CD∨∧c.AB∨┓CD∨∧d.A┓B∨∧CD∨+++5、中間代碼的樹型表示ABCD所對應(yīng)的表達式為。+B+C+D+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D)6、四元式表示法的長處為。a.不便于優(yōu)化辦理，但便于表的更動b.不便于優(yōu)化辦理，但節(jié)儉儲存空間c.便于優(yōu)化辦理，也便于表的更動d.便于表的更動，也節(jié)儉儲存空間7、終結(jié)符擁有屬性。a.傳達b.繼承c.抽象d.綜合二、多頂選擇題1、中間代碼主要有。a．四元式b．二元式c．三元式d．后綴式e．間接三元式2、下邊中間代碼形式中，能正確表示算術(shù)表達式a+b+c的有。a．a(chǎn)b+c+b．a(chǎn)bc++c．+d．+e．a(chǎn)+b+c+ca+abbc3、在下邊的語法制導翻譯中，采納拉鏈-回填技術(shù)。a．賦值語句b．goto語句c．條件語句d．循環(huán)語句4、以下中間代碼形式有利于優(yōu)化辦理。a．三元式b．四元式c．間接三元式d．逆波蘭表示法e．樹形表示法5、在編譯程序中安排中間代碼生成的目的是。a．便于進行儲存空間的組織b．利于目標代碼的優(yōu)化c．利于編譯程序的移植d．利于目標代碼的移植e．利于提升目標代碼的質(zhì)量6、下邊的中間代碼形式中，

能正確表示算術(shù)表達式

a+b*c。題）*

+a．a(chǎn)b+c*

b．a(chǎn)bc*+

c．a(chǎn)+b*c

d．

+

c

e．

a

*7、三地點代碼語句詳細實現(xiàn)往常有

表示方法。a．逆波蘭表示b．三元式

c．間接三元式

d．樹形表示

e．四元式三、填空題1、中間代碼有等形式，生成中間代碼主假如為了使。2、語法制導翻譯既能夠用來產(chǎn)生代碼，也能夠用來產(chǎn)生指令，甚至可用來對輸入串進行。3、當源程序中的標號出現(xiàn)“先引用后定義”時，中間代碼的轉(zhuǎn)移地點須持時才能確立，因此要進行。4、文法符號的屬性有兩種，一種稱為，另一種稱為。5、后綴式abc-/所代表的表達式是，表達式(a-b)*c可用后綴式表示。6、用一張輔以的方法來表示中間代碼，這類表示法稱為間接三元式。四、綜合題1、給出以下表達式的逆波蘭表示（后綴式）：a*(-b+c)(A∨B)∧(C∨┑D∧E)2、寫出算術(shù)表達式：A+B*(C-D)+E/(C-D)↑N的①四元式序列；②三元式序列；③間接三元式序列單項選擇解答1、選c。2、四元式之間的聯(lián)系是經(jīng)過暫時變量實現(xiàn)的，應(yīng)選b。3、選b。4、選b。5、選d。6、四元式表示法的長處與間接三元式同樣，應(yīng)選c。7、選d。多項選擇解答1、選a、c、d、e。2、b、d的中間代碼不可以正確表示a+b+c，而e不是中間代碼：應(yīng)選a、c。3、凡波及到跳轉(zhuǎn)的語句都需要采納拉鏈——回填技術(shù)，應(yīng)選b、c、d。4、選b、c。5、選b、d。6、選b、e。7、選b、c、e。填空解答1、逆波蘭記號、樹形表示、三元式、四元式2、中間目標解說履行

目標代碼的優(yōu)化簡單實現(xiàn)3、標號定義4、繼承屬性

回填綜合屬性5、a/(b-c)

ab-c*6、間接碼表三元式表綜合解答1、①ab@c+*;AB∨CD┑E∧∨∧2、①表達式的四元式序列：②表達式的三元式序列③間接三元式序列（1）(-,C,D,T1)（1）(-,C,D)⑴（1）(-,C,D)（2）(*,B,T,T)（2）(*,B,(1))⑵（2）(*,B,(1))12（3）(+,A,T,T)（3）(+,A,(2))⑶（3）(+,A,(2))23（4）(-,C,D,T4)（4）(-,C,D)⑴⑷(↑,(1),N)第八章一、單項選擇題1、編譯程序使用差別表記符的作用域。a.說明表記符的過程或函數(shù)名c.說明表記符的過程或函數(shù)的動向?qū)哟?/p>

b.說明表記符的過程或函數(shù)的靜態(tài)層次d.表記符的行號2、在目標代碼生成階段，符號表用于。a.目標代碼生成b.語義檢查c.語法檢查d.地點分派3、過程信息表不包含。a.過程進口地點b.過程的靜態(tài)層次c.過程名d.過程參數(shù)信息4、以下對于表記符和名字表達中，正確的選項是。a.表記符有必定的含義b.名字是一個沒存心義的字符序列c.名字有切實的屬性d.a~c都不正確二、多項選擇題1、符號表的每一項均包含a.名字欄b.種類欄

。

c.信息欄

d.值欄

e.a~d均包含2、對編譯程序所用到的符號表，波及的操作有。a.填寫或更新信息欄內(nèi)容b.填入新名c.給命名字，接見它的有關(guān)信息d.雜湊技術(shù)e.線性表和排序二叉樹3、源程序中的錯誤一般有。a.詞法錯誤b.語法錯誤c.d.編譯錯誤e.違犯環(huán)境限制的錯誤

語義錯誤三、填空題1、符號表中名字欄內(nèi)容有兩種填寫方式，它們是填寫和填寫。2、詞法剖析階段的錯誤主假如，可經(jīng)過的方法糾正錯誤。3、符號表中名字的有關(guān)信息在和過程中陸續(xù)填入。4、在目標代碼生成階段，符號表是的依照。四、問答題：1、在編譯過程中為何要成立符號表單項選擇解答：1、b2、d3、b4、c多項選擇解答：1、a、c2、a、b、c3、a、b、c、e填空解答：1、表記符表記符地點及長度2、拼寫錯誤

最小距離般配

3、詞法剖析

語法語義剖析4、地點分派問答題解答：在編譯過程中一直要波及到對一些語法符號的辦理，這就需要用到語法符號的有關(guān)屬性。為了在需要時能找到這些語法成分及其有關(guān)屬性，就一定使用一些表格來保留這些語法成分及其屬性，這些表格就是符號表。第九章一、單項選擇題1、程序所需的數(shù)據(jù)空間在程序運轉(zhuǎn)前可確立，稱為a.動向儲存b.棧式儲存c.靜態(tài)儲存2、堆式動向分派申請和開釋儲存空間恪守原則。a.先請先放b.先請后放c.后請先放

管理技術(shù)。d.堆式儲存d.隨意3、靜態(tài)分派同意程序出現(xiàn)。a.遞歸過程b.可變體積的數(shù)據(jù)項目

c.靜態(tài)變量

d.待定性質(zhì)的名字4、在編譯方法中，動向儲存分派的含義是

。在運轉(zhuǎn)階段對源程序中的數(shù)組、變量、參數(shù)等進行分派在編譯階段對源程序中的數(shù)組、變量、參數(shù)進行分派在編譯階段對源程序中的數(shù)組、變量、參數(shù)等進行分派，在運轉(zhuǎn)時這些數(shù)組、變量、參數(shù)的地點可依據(jù)需要改變以上都不正確5、在編譯時有傳名功能的高級程序語言是。a.Fortran

b.Basic

c.Pascal

d.ALGOL6、棧式動向分派與管理在過程返回時應(yīng)做的工作有。a.保護SPb.恢復SPc.保護TOPd.恢復二、多項選擇題1、下邊需要在運轉(zhuǎn)階段分派儲存空間。a.數(shù)組b.指針變量c.動向數(shù)組d.靜態(tài)變量e.動向變量2、棧式動向分派同意。a.遞歸過程b.分程序結(jié)構(gòu)c.動向變量d.動向數(shù)組e.靜態(tài)數(shù)組

TOP3、動向儲存分派可采納的分派方案有a.隊式儲存分派b.棧式儲存分派d.堆式儲存分派e.線性儲存分派

。

c.鏈式儲存分派4、