編譯原理復(fù)習(xí)題集與答案解析(整理后)

..第一章1、將編譯程序分成若干個(gè)"遍"是為了。a．提高程序的執(zhí)行效率b．使程序的結(jié)構(gòu)更加清晰c．利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率d．利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2、構(gòu)造編譯程序應(yīng)掌握。 a．源程序 b．目標(biāo)語言c．編譯方法 d．以上三項(xiàng)都是3、變量應(yīng)當(dāng)。a．持有左值 b．持有右值c．既持有左值又持有右值 d．既不持有左值也不持有右值4、編譯程序絕大多數(shù)時(shí)間花在上。 a．出錯(cuò)處理 b．詞法分析c．目標(biāo)代碼生成 d．管理表格5、不可能是目標(biāo)代碼。 a．匯編指令代碼 b．可重定位指令代碼c．絕對(duì)指令代碼 d．中間代碼6、使用可以定義一個(gè)程序的意義。a．語義規(guī)則 b．語法規(guī)則c．產(chǎn)生規(guī)則 d．詞法規(guī)則7、詞法分析器的輸入是。a．單詞符號(hào)串 b．源程序c．語法單位 d．目標(biāo)程序8、中間代碼生成時(shí)所遵循的是-。a．語法規(guī)則 b．詞法規(guī)則c．語義規(guī)則 d．等價(jià)變換規(guī)則9、編譯程序是對(duì)。a．匯編程序的翻譯 b．高級(jí)語言程序的解釋執(zhí)行c．機(jī)器語言的執(zhí)行 d．高級(jí)語言的翻譯10、語法分析應(yīng)遵循。 a．語義規(guī)則 b．語法規(guī)則c．構(gòu)詞規(guī)則 d．等價(jià)變換規(guī)則二、多項(xiàng)選擇題1、編譯程序各階段的工作都涉及到。 a．語法分析 b．表格管理 c．出錯(cuò)處理d．語義分析 e．詞法分析2、編譯程序工作時(shí),通常有階段。 a．詞法分析 b．語法分析 c．中間代碼生成d．語義檢查 e．目標(biāo)代碼生成三、填空題1、解釋程序和編譯程序的區(qū)別在于。2、編譯過程通?？煞譃?個(gè)階段,分別是、語法分析、代碼優(yōu)化和目標(biāo)代碼生成。 3、編譯程序工作過程中,第一段輸入是,最后階段的輸出為程序。4、編譯程序是指將程序翻譯成程序的程序。單選解答1、將編譯程序分成若干個(gè)"遍"是為了使編譯程序的結(jié)構(gòu)更加清晰,故選b。2、構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語言及編譯方法等三方面的知識(shí),故選d。3、對(duì)編譯而言,變量既持有左值又持有右值,故選c。4、編譯程序打交道最多的就是各種表格,因此選d。5、目標(biāo)代碼包括匯編指令代碼、可重定位指令代碼和絕對(duì)指令代碼3種,因此不是目標(biāo)代碼的只能選d。6、詞法分析遵循的是構(gòu)詞規(guī)則,語法分析遵循的是語法規(guī)則,中間代碼生成遵循的是語義規(guī)則,并且語義規(guī)則可以定義一個(gè)程序的意義。因此選a。7、b8、c9、d10、c多選解答1．b、c2.a、b、c、e填空解答是否生成目標(biāo)程序2、詞法分析中間代碼生成3、源程序 目標(biāo)代碼生成 4、源程序目標(biāo)語言 第二章一、單項(xiàng)選擇題1、文法G：S→xSx|y所識(shí)別的語言是。 a.xyx b.<xyx>* c.xnyxn<n≥0> d.x*yx*2、文法G描述的語言L<G>是指。a.L<G>={α|Seq\o<\s\up3<+>,\s\do1<?>>α,α∈VT*} b.L<G>={α|Seq\o<\s\up3<*>,\s\do1<?>>α,α∈VT*}c.L<G>={α|Seq\o<\s\up3<*>,\s\do1<?>>α,α∈<VT∪VN*>} d.L<G>={α|Seq\o<\s\up3<+>,\s\do1<?>>α,α∈<VT∪VN*>} 3、有限狀態(tài)自動(dòng)機(jī)能識(shí)別。a.上下文無關(guān)文法 b.上下文有關(guān)文法c.正規(guī)文法 d.短語文法 4、設(shè)G為算符優(yōu)先文法,G的任意終結(jié)符對(duì)a、b有以下關(guān)系成立。a.若f<a>>g<b>,則a>b b.若f<a><g<b>,則a<bc.a~b都不一定成立 d.a~b一定成立 5、如果文法G是無二義的,則它的任何句子α。 a.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同b.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同c.最左推導(dǎo)和最右推導(dǎo)必定相同d.可能存在兩個(gè)不同的最左推導(dǎo),但它們對(duì)應(yīng)的語法樹相同 6、由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是。a.短語 b.句柄 c.句型 d.句子 7、文法G：E→E+T|TT→T*P|PP→<E>|I則句型P+T+i的句柄和最左素短語為。a.P+T和i b.P和P+T c.i和P+T+i d.P和T8、設(shè)文法為：S→SA|AA→a|b則對(duì)句子aba,下面是規(guī)范推導(dǎo)。a.STSATSAATAAATaAATabATabab.STSATSAATAAATAAaTAbaTabac.STSATSAATSAaTSbaTAbaTabad.STSATSaTSAaTSbaTAbaTaba9、文法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歸約,其值為。a.23B.42c.30d.1714、規(guī)范歸約指。a.最左推導(dǎo)的逆過程 b.最右推導(dǎo)的逆過程 c.規(guī)范推導(dǎo)d.最左歸約的逆過程 二、多項(xiàng)選擇題1、下面哪些說法是錯(cuò)誤的。 a.有向圖是一個(gè)狀態(tài)轉(zhuǎn)換圖 b.狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖c.有向圖是一個(gè)DFA d.DFA可以用狀態(tài)轉(zhuǎn)換圖表示2、對(duì)無二義性文法來說,一棵語法樹往往代表了。a.多種推導(dǎo)過程 b.多種最左推導(dǎo)過程 c.一種最左推導(dǎo)過程d.僅一種推導(dǎo)過程 e.一種最左推導(dǎo)過程3、如果文法G存在一個(gè)句子,滿足下列條件之一時(shí),則稱該文法是二義文法。a.該句子的最左推導(dǎo)與最右推導(dǎo)相同b.該句子有兩個(gè)不同的最左推導(dǎo)c.該句子有兩棵不同的最右推導(dǎo)d.該句子有兩棵不同的語法樹e.該句子的語法樹只有一個(gè)4、有一文法G：S→AB A→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、對(duì)正規(guī)文法描述的語言,以下有能力描述它。a.0型文法 b.1型文法 c.上下文無關(guān)文法 d.右線性文法 e.左線性文法三、填空題1、文法中的終結(jié)符和非終結(jié)符的交集是。詞法分析器交給語法分析器的文法符號(hào)一定是,它一定只出現(xiàn)在產(chǎn)生式的部。2、最左推導(dǎo)是指每次都對(duì)句型中的非終結(jié)符進(jìn)行擴(kuò)展。3、在語法分析中,最常見的兩種方法一定是分析法,另一是分析法。4、采用語法分析時(shí),必須消除文法的左遞歸。5、樹代表推導(dǎo)過程,樹代表歸約過程。6、自下而上分析法采用、歸約、錯(cuò)誤處理、等四種操作。7、Chomsky把文法分為種類型,編譯器構(gòu)造中采用和文法,它們分別產(chǎn)生和語言,并分別用和自動(dòng)機(jī)識(shí)別所產(chǎn)生的語言。四、判斷題1、文法S→aS|bR|ε描述的語言是<a|bc>* <>R→cS2、在自下而上的語法分析中,語法樹與分析樹一定相同。 〔3、二義文法不是上下文無關(guān)文法。 〔4、語法分析時(shí)必須先消除文法中的左遞歸?！?、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程?！?、一個(gè)文法所有句型的集合形成該文法所能接受的語言?！参?、簡答題1、句柄 2、素短語 3、語法樹 4、歸約 5、推導(dǎo)六、問答題1、給出上下文無關(guān)文法的定義。2、文法G[S]：S→aSPQ|abQQP→PQbP→bbbQ→bccQ→cc〔1它是Chomsky哪一型文法？〔2它生成的語言是什么？3、按指定類型,給出語言的文法。L={aibj|j＞i≥1}的上下文無關(guān)文法。4、有文法G：S→aAcB|Bd

A→AaB|c

B→bScA|b〔1試求句型aAaBcbbdcc和aAcbBdcc的句柄；〔2寫出句子acabcbbdcc的最左推導(dǎo)過程。5、對(duì)于文法G[S]：S→〔L|aS|aL→L,S|S〔1畫出句型〔S,〔a的語法樹?！?寫出上述句型的所有短語、直接短語、句柄和素短語。6、考慮文法G[T]： T→T*F|F F→F↑P|P P→〔T|i證明T*P↑〔T*F是該文法的一個(gè)句型,并指出直接短語和句柄。單選[解答]1、選c。2、選a。3、選c。4、雖然a與b沒有優(yōu)先關(guān)系,但構(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)系：故選c。EE+FEE+FE+TPTiP#<·+·>+<·i·>#圖2-8-1句型P+T+I的語法及優(yōu)先關(guān)系6、選c。7、由圖2-8-1的語法樹和優(yōu)先關(guān)系可以看出應(yīng)選b。8、規(guī)范推導(dǎo)是最左推導(dǎo),故選d。9、由T→T,…和T→<…得FIRSTVT<T>>={<,,>}；由T→S得FIRSTVT<S>?FIRSTVT<T>,而FIRSTVT<S>={b,∧,<}；即 FIRSTVT<T>={b,∧,<,,}；因此選c。10、d11、c12、b13、b14、b多選解答1、e、a、c2、a、c、e3、b、c、d4、a、c5、b、c6、a、b、c、d、e填空解答1、空集終結(jié)符右2、最左3、自上而上自下而上4、自上而上5、語法分析6、移進(jìn)接受7、42型3型上下文無關(guān)語言正規(guī)語言下推自動(dòng)機(jī)有限判斷解答1、對(duì)2、錯(cuò)3、錯(cuò)4、錯(cuò)5、錯(cuò)6、錯(cuò)簡答[解答]1、句柄：一個(gè)句型的最左直接短語稱為該句型的句柄。2、素短語：至少含有一個(gè)終結(jié)符的素短語,并且除它自身之外不再含任何更小的素短語。3、語法樹：滿足下面4個(gè)條件的樹稱之為文法G[S]的一棵語法樹。①每一終結(jié)均有一標(biāo)記,此標(biāo)記為VN∪VT中的一個(gè)符號(hào)；②樹的根結(jié)點(diǎn)以文法G[S]的開始符S標(biāo)記；③若一結(jié)點(diǎn)至少有一個(gè)直接后繼,則此結(jié)點(diǎn)上的標(biāo)記為VN中的一個(gè)符號(hào)；④若一個(gè)以A為標(biāo)記的結(jié)點(diǎn)有K個(gè)直接后繼,且按從左至右的順序,這些結(jié)點(diǎn)的標(biāo)記分別為X1,X2,…,XK,則A→X1,X2,…,XK,必然是G的一個(gè)產(chǎn)生式。4、歸約：我們稱αγβ直接歸約出αAβ,僅當(dāng)A→γ是一個(gè)產(chǎn)生式,且α、β∈<VN∪VT>*。歸約過程就是從輸入串開始,反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào),直至文法開始符。5、推導(dǎo)：我們稱αAβ直接推出αγβ,即αAβTαγβ,僅當(dāng)A→γ是一個(gè)產(chǎn)生式,且α、β∈<VN∪VT>*。如果α1Tα2T…Tαn,則我們稱這個(gè)序列是從α1至α2的一個(gè)推導(dǎo)。若存在一個(gè)從α1αn的推導(dǎo),則稱α1可推導(dǎo)出αn。推導(dǎo)是歸約的逆過程。問答1[解答]一個(gè)上下文無關(guān)文法G是一個(gè)四元式〔VT,VN,S,P,其中：●VT是一個(gè)非空有限集,它的每個(gè)元素稱為終結(jié)符號(hào)；●VN是一個(gè)非空有限集,它的每個(gè)元素稱為非終結(jié)符號(hào),VT∩VN=Φ；●S是一個(gè)非終結(jié)符號(hào),稱為開始符號(hào)；●P是一個(gè)產(chǎn)生式集合〔有限,每個(gè)產(chǎn)生式的形式是P→α,其中,P∈VN,α∈<VT∪VN>*。開始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。2[解答]〔1由于產(chǎn)生式左部存在終結(jié)符號(hào),且所有產(chǎn)生式左部符號(hào)的長度均小于等于產(chǎn)生式右部的符號(hào)長度,所以文法G[S]是Chomsky1型文法,即上下文有關(guān)文法?！?按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級(jí)由高到低〔否則無法推出句子,我們可以得到：STabQTabcSTaSPQTaabQPQTaabPQQTaabbQQTaabbcQTaabbccSTaSPQTaaSPQPQTaaabQPQPQTaaabPQQPQTaaabPQPQQTaaaPPQQQTaaabbPqqqTaaabbQQQTaaabbbcQQTaaabbbccQTaaabbbccc……于是得到文法G[S]生成的語言L={anbncn|n≥1}3[解答]〔1由L={aibj|j＞i≥1}知,所求該語言對(duì)應(yīng)的上下文無關(guān)文法首先應(yīng)有S→aSb型產(chǎn)生式,以保證b的個(gè)數(shù)不少于a的個(gè)數(shù)；其次,還需有S→Sb或S→bS型的產(chǎn)生式,用以保證b的個(gè)數(shù)多于a的個(gè)數(shù)；也即所求上下文無關(guān)文法G[S]為：G[S]：S→aSb|Sb|b4[解答]〔1分別畫出對(duì)應(yīng)兩句型的語法樹,如圖2-8-2所示句柄:AaBBdSSa

A

c

B

A

a

BbScABdcb<a>SSaAcBBScABd

c<b>圖2-8-2語法樹〔2句子acabcbbdcc的最左推導(dǎo)如下：STaAcBTaAaBcBTacaBcBTacabcBTacabcbScATacabcbBdcATacabcbbdcATacabcbbdccS〔LS〔LL,S

S

<L>Sa圖2-8-3句型〔S,〔a的語法樹〔1句型〔S,〔a的語法樹如圖2-8-3所示〔2由圖2-8-3可知：①短語：S、a、<a>、S,<a>、<S,<a>>；②直接短語：a、S；③句柄：S；④素短語：素短語可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得,即；##·〔·,

·〔

·a···#因此素短語為a。

T

T*F

F

↑

P

P〔

T

T*F圖2-8-4句型T*P↑〔T*F的語法樹首先構(gòu)造T*P↑〔T*F的語法樹如圖2-8-4所示。由圖2-8-4可知,T*P↑〔T*F是文法G[T]的一個(gè)句型。直接短語有兩個(gè),即P和T*F；句柄為P。第三章一、單項(xiàng)選擇題1、詞法分析所依據(jù)的是。a.語義規(guī)則 b.構(gòu)詞規(guī)則 c.語法規(guī)則 d.等價(jià)變換規(guī)則2、詞法分析器的輸出結(jié)果是。a.單詞的種別編碼 b.單詞在符號(hào)表中的位置c.單詞的種別編碼和自身值 d.單詞自身值3、正規(guī)式M1和M2等價(jià)是指。a.M1和M2的狀態(tài)數(shù)相等 b.M1和M2的有向弧條數(shù)相等c.M1和M2所識(shí)別的語言集相等 d.M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等4、狀態(tài)轉(zhuǎn)換圖〔見圖3-6-1接受的字集為。00

10圖3-6-1Ya.以0開頭的二進(jìn)制數(shù)組成的集合b.以0結(jié)尾的二進(jìn)制數(shù)組成的集合c.含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合d.含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合5、詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序結(jié)構(gòu)更加簡潔、明確,因此,。a.詞法分析器應(yīng)作為獨(dú)立的一遍b.詞法分析器作為子程序較好c.詞法分析器分解為多個(gè)過程,由語法分析器選擇使用d.詞法分析器并不作為一個(gè)獨(dú)立的階段二、多項(xiàng)選擇題1、在詞法分析中,能識(shí)別出。a.基本字 b.四元式 c.運(yùn)算符d.逆波蘭式 e.常數(shù)2、令∑={a,b},則∑上所有以b開頭,后跟若干個(gè)ab的字的全體對(duì)應(yīng)的正規(guī)式為。a.b<ab>* b.b<ab>+ c.<ba>*bd.<ba>+b e.b<a|b>三、填空題1、確定有限自動(dòng)機(jī)DFA是的一個(gè)特例。2、若二個(gè)正規(guī)式所表示的相同,則認(rèn)為二者是等價(jià)的。3、一個(gè)字集是正規(guī)的,當(dāng)且僅當(dāng)它可由所。四、判斷題1、一個(gè)有限狀態(tài)自動(dòng)機(jī)中,有且僅有一個(gè)唯一終態(tài)。 〔2、設(shè)r和s分別是正規(guī)式,則有L〔r|s=L<r>|L<s>。 〔3、自動(dòng)機(jī)M和M′的狀態(tài)數(shù)不同,則二者必不等價(jià)。 〔4、確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。 〔5、對(duì)任意一個(gè)右線性文法G,都存在一個(gè)NFAM,滿足L<G>=L<M>。 〔6、對(duì)任意一個(gè)右線性文法G,都存在一個(gè)DFAM,滿足L<G>=L<M>。 〔7、對(duì)任何正規(guī)表達(dá)式e,都存在一個(gè)NFAM,滿足L<G>=L<e>。 〔8、對(duì)任何正規(guī)表達(dá)式e,都存在一個(gè)DFAM,滿足L<G>=L<e>。 〔五、基本題1、設(shè)M＝〔{x,y},{a,b},f,x,{y}為一非確定的有限自動(dòng)機(jī),其中f定義如下：f〔x,a＝{x,y} f〔x,b＝{y}f〔y,a＝φ f〔y,b＝{x,y}試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M′。2、對(duì)給定正規(guī)式b*〔d|ad〔b|ab+,構(gòu)造其NFAM；單選解答1、b2、c3、c4、d5、b多選解答1、a、c、e2、a、b、d填空解答1、NFA2、正規(guī)集3、DFA〔NFA所識(shí)別判斷解答1、2、3、錯(cuò)4、5、6、7、8、正確aabbb圖3-6-2NFAMXY基本1解答：對(duì)照自動(dòng)機(jī)的定義M=<S,Σ,f,S0,Z>aabbb圖3-6-2NFAMXY用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表3-6-3所示。IIaIb{x}{x,y}{y}{y}—{x,y}{x,y}{x,y}{x,y}將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態(tài)轉(zhuǎn)換矩陣。表3-6-4狀態(tài)轉(zhuǎn)換矩陣ab0211—2222aa,bbb圖3-6-5DFAM′aa,bbb圖3-6-5DFAM′021aa,bb圖3-6-6化簡后的DFAM′01將圖3-6-5的DFAM′最小化。首先,將M′的狀態(tài)分成終態(tài)組{1,2}與非終態(tài)組{0}；其次,考察{1,2}。由于{1,2}a={1,2}b={2}?aa,bb圖3-6-6化簡后的DFAM′01aadεεb*b*<d|ad><b|ab><b|ab>*aadεεb*b*<d|ad><b|ab><b|ab>*XYX123YX4135Y678<d|ad><b|ab><b|ab>*2εdbadabεεb|abbX4135Y2bεdbεεbabb圖3-6-7的NFAM第四章1、構(gòu)造下面文法的LL〔1分析表。D→TLT→int|realL→idRR→,idR|ε2、下面文法G[S]是否為LL〔1文法？說明理由。S→AB|PQxA→xy B

→bcP

→dP|ε Q

→aQ|ε3、設(shè)有以下文法：G[S]：S→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|ε〔1求出該文法的每一個(gè)非終結(jié)符U的FOLLOW集。〔2該文法是LL〔1文法嗎？〔3構(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方法進(jìn)行語法分析,如何得到該文法的LL〔1分析表？〔3若輸入符號(hào)串"aaaa",請(qǐng)給出語法分析過程。1解答：LL〔1分析表見表4-3-1分析雖然這個(gè)文法很簡單,我們還是從求開始符號(hào)集合和后繼符號(hào)集合開始。FIRST〔D=FIRST〔T={int,real}FOLLOW〔D=FOLLOW〔L={#}FIRST〔L={id} FOLLOW〔T={id}FIRST〔R={,,ε} FOLLOW〔R={#}有了上面每個(gè)非終結(jié)符的FIRST集合,填分析表時(shí)要計(jì)算一個(gè)產(chǎn)生式右部α的FIRST〔α就不是件難事了。填表時(shí)唯一要小心的時(shí),ε是產(chǎn)生式R→ε右部的一個(gè)開始符號(hào),而#在FOLLOW〔R中,所以R→ε填在輸入符號(hào)#的欄目中。表4-3-1LL〔1分析表非終結(jié)符輸入符號(hào)intrealid,#DD→TLD→TLTT→intT→realLL→idRRR→,idRR→ε2解答：該文法不是LL〔1文法,見下面分析中的說明。分析只有三個(gè)非終結(jié)符有兩個(gè)選擇。1、P的兩個(gè)右部dP和ε的開始符號(hào)肯定不相交。2、Q的兩個(gè)右部aQ和ε的開始符號(hào)肯定不相交。3、對(duì)S來說,由于x∈FIRST<AB>,同時(shí)也有x∈FIRST<PQx>〔因?yàn)镻和Q都可能為空。所以該文法不是LL〔1文法。3解答：〔1求文法的每一個(gè)非終結(jié)符U的FOLLOW集的過程如下：因?yàn)椋孩賁是識(shí)別符號(hào),且有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#}②又因?yàn)锳→BSD和D→ε,所以FOLLOW中還包含F(xiàn)OLLOW<A>。因?yàn)镾→aAbDe和B→SAc,所以FOLLOW〔A=FIRST〔bDe∪FIRST〔c={b,c}綜合①、②得FOLLOW〔S={a,d,c,e,#}∪{a,b,c,d,e,#}因?yàn)锳→BSD,所以FOLLOW〔B=FIRST〔SD={a,d}因?yàn)镾→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}〔2G[S]不是LL〔1文法。因?yàn)楫a(chǎn)生式B→SAc|cD|ε中FIRST〔SAc∩FOLLOW〔B={a,d}≠?〔3構(gòu)造G[S]的LL〔1分析表。按照LL〔1分析表的構(gòu)造算法構(gòu)造方法G[S]的LL〔1分析表如表4-3-2所示。表4-3-2G[S]的LL〔1分析表abcde#SaAbDedABSDBSDBSDeBSac/εcDSac/εDSe/εεεSe/εε4解答：對(duì)文法G[V]提取公共左因子后得到文法：G′[V]：V→NAA→ε|[E]E→VBB→ε|+EN→i求出文法G′[V]中每一個(gè)非終結(jié)符號(hào)的FIRST集： FIRST<V>={i} FIRST<A>={[,ε} FIRST<E>={i} FIRST<B>={+,ε} FIRST<N>={i}求出文法G′[V]中每一個(gè)非終結(jié)符號(hào)的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>={[,],+,#}可以看到,對(duì)文法G′[V]的產(chǎn)生式A→ε|[E],有FIRST<[E]>∩FOLLOW<A>={[}∩{+,],#}=?對(duì)產(chǎn)生式B→ε|+E,有FIRST<+E>∩FOLLOW<B>={+}∩{]}=?而文法的其他產(chǎn)生式都只有一個(gè)不為ε的右部,所以文法G′[V]是LL<1>文法。5解答：〔1因?yàn)楫a(chǎn)生式A→aAa|ε有空產(chǎn)生式右部,而FOLLOW<A>={#}∪FIRST<a>={a,#}造成FIRST<A>∩FOLLOW<A>={A,ε}∩{a,#}≠?所以該文法不是LL〔1文法?！?若采用LL〔1方法進(jìn)行語法分析,必須修改該文法。因該文法產(chǎn)生偶數(shù)〔可以為0個(gè)a,所以得到文法G′[A]： A→aaA|ε此時(shí)對(duì)產(chǎn)生式A→aaA|ε,有FOLLOW<A>={#}∪FOLLOW<A>={#},因而FIRST<A>∩FOLLOW<A>={a,ε}∩{#}=?所以文法G′[A]是LL〔1文法,按LL〔1分析表構(gòu)造算法構(gòu)造該文法的LL〔1分析表如表4-3-3所示。表4-3-3 文法G′[A]的LL<1>分析表A#AA→aaAA→ε〔3若采用LL<1>方法進(jìn)行語法分析,對(duì)符號(hào)串"aaaa"的分析過程如表4-3-4所示。表4-3-4 對(duì)符號(hào)串"aaaa"的分析過程步驟分析棧輸入串產(chǎn)生式/動(dòng)作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完成下列算符優(yōu)先關(guān)系表,見表5-7-1,并判斷G[S]是否為算符優(yōu)先文法。表5-7-1算符優(yōu)先關(guān)系表ab<>d#a??b??<????>??d#????〔2給出句型〔SdSdS的短語、簡單短語、句柄、素短語和最左素短語。〔3給出輸入串〔adb#的分析過程。解答：〔1先求文法G[S]的FIRSTVT集和LASTVT集：由S→a|b|<A>得：FIRSTVT<S>={a,b,<>;由A→Sd…得：FIRSTVT<A>=gwkecsu;又由A→S…得：FIRSTVT<S>?FIRSTVT<A>,即FIRSTVT<A>={d,a,b,<};由S→a|b|<A>得；LASTVT<S>={a,b,}};由A→…dA得：LASTVT<A>=qq06m8k,又由A→S得：LASTVT<S>?LASTVT<A>,即LASTVT<A>={d,a,b,>}。構(gòu)造優(yōu)先關(guān)系表方法如下：①對(duì)P→…ab…,或P→…aQb…,有a?b;②對(duì)P→…aR…,而b∈FIRSTVT<R>,有a?b;③對(duì)P→…Rb…,而a∈FIRSTVT<R>,有a?b。由此得到：①由S→<A>得：<?>;②由S→<A…得：<?FIRSTVT<A>,即：<?d,<?a,<?b,<?<;由A→…dA得：d?FIRSTVT<A>,即：d?d,d?a,d?b,d?<;③由S→A>得,LASTVT<A>?>,即：d?>,a?>,b?>,>?>;由A→Sd…得：LASTVT<S>?d,即：a?d,b?d,>?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#a???b???<????>???d??????#????由表5-7-2可以看出,任何兩個(gè)終結(jié)符之間至少只滿足?、?、?三種優(yōu)先關(guān)系之一,故G[S]為算符優(yōu)先文法。SASASASASd〔ASd圖5-7-3句型〔SdSdS的語法樹短語：S,SdS,SdSdS,〔SdSdS簡單短語〔即直接短語：S句柄〔即最左直接短語：S素短語：SdS,它同時(shí)也是該句型的最左素短語?！?輸入串〔adb#的分析過程見表5-7-4表5-7-4輸入串〔adb#的分析過程符號(hào)棧輸入串說明#<adb>#移進(jìn)#〔adb>#移進(jìn)#〔adb>#用S→a歸約#〔Sdb>#移進(jìn)#〔Sdb>#移進(jìn)#〔Sdb>#用S→b歸約#〔SdS>#用A→S歸約#〔SdA>#用A→SdA歸約#〔A>#移進(jìn)#〔A#用S→〔A歸約#S#分析成功第六章一、單項(xiàng)選擇題1、若a為終結(jié)符,則A→α·aβ為項(xiàng)目a.歸約 b.移進(jìn) c.接受 d.待約2、若項(xiàng)目集Ik含有A→α·,則在狀態(tài)k時(shí),僅當(dāng)面臨的輸入符號(hào)a∈FOLLOW<A>時(shí),才采取"A→α·"動(dòng)作的一定是。a.LALR文法 b.LR〔0文法 c.LR〔1文法 d.SLR〔1文法3、就文法的描述能力來說,有。a.SLR〔1?LR〔0b.LR〔1?LR〔0c.SLR〔1?LR〔1d.無二義文法?LR〔14、在LR〔0的ACTION子表中,如果某一行中存在標(biāo)記"rj"的欄,則。a.該行必定填滿rjb.該行未填滿rjc.其他行也有rjd.goto子表中也有rj5、一個(gè)指明了在分析過程中的某時(shí)刻所能看到產(chǎn)生式多大一部分。a.活前綴 b.前綴 c.項(xiàng)目 d.項(xiàng)目集二、多項(xiàng)選擇題1、一個(gè)LR分析器包括。a.一個(gè)總控程序 b.一個(gè)項(xiàng)目集 c.一個(gè)活前綴d.一張分析表 e.一個(gè)分析棧2、LR分析器核心部分是一張分析表,該表包括等子表。a.LL<1>分析 b.優(yōu)先關(guān)系 c.GOTOd.LR e.ACTION3、每一項(xiàng)ACTION[S,a]所規(guī)定的動(dòng)作包括。a.移進(jìn) b.比較 c.接受 d.歸約 e.報(bào)錯(cuò)4、對(duì)LR分析表的構(gòu)造,有可能存在動(dòng)作沖突。a.移進(jìn) b.歸約 c.移進(jìn)/歸約 d.移進(jìn)/移進(jìn) e.歸約/歸約5、就文法的描述能力來說,有。a.SLR〔1?LR〔1 b.LR〔1?SLR〔1 c.LR〔0?LR〔1d.LR〔1?無二義文法 e.SLR〔1?無二義文法6、對(duì)LR分析器來說,存在等分析表的構(gòu)造方法。a.LALR b.LR〔0 c.SLR〔1 d.SLR〔0 e.LR〔17、自上而下的語法分析方法有。a.算符優(yōu)先分析法 b.LL〔1分析法 c.SLR〔1分析法d.LR〔0分析法 e.LALR〔1分析法三、填空題1、對(duì)于一個(gè)文法,如果能夠構(gòu)造。使得它的均是唯一確定的,則稱該文法為LR文法。2、字的前綴是指該字的。3、活前綴是指的一個(gè)前綴,這種前綴不含之后的任何符號(hào)。4、在LR分析過程中,只要的已掃描部分保持可歸約成一個(gè),則掃描過的部分正確。5、將識(shí)別的NFA確定化,使其成為以為狀態(tài)的DFA,這個(gè)DFA就是建立的基礎(chǔ)。6、A→α·稱為項(xiàng)目；對(duì)文法開始符S′→α·為項(xiàng)目；若a為終結(jié)符,則稱A→α·aβ為項(xiàng)目；若B為非終結(jié)符,則稱A→α·aβ為項(xiàng)目。7、LR〔0分析法的名字中"L"表示,"R"表示,"0"表示。四、綜合題1、對(duì)于文法G[S]：S→AS|bA→SA|a〔1列出所有LR〔0項(xiàng)目〔2列出構(gòu)成文法LR〔0項(xiàng)目集規(guī)范族。單項(xiàng)解答：1、A→α·稱為歸約項(xiàng)目,對(duì)文法開始符S′的歸約項(xiàng)目,如S′→α·稱為接受項(xiàng)目,A→α·aβ〔a為終結(jié)符稱為移進(jìn)項(xiàng)目。在此選b.2、當(dāng)用產(chǎn)生式A→α歸約時(shí),LR〔0無論面臨什么輸入符號(hào)都進(jìn)行歸約；SLR〔1則僅當(dāng)面臨的輸入符號(hào)a∈FOLLOW<A>時(shí)進(jìn)行歸約；LR〔1則當(dāng)在把α歸約為A的規(guī)范句型的前綴βAa前提下,當(dāng)α后跟終結(jié)符a時(shí),才進(jìn)行歸約；因此選d。3、由于LR〔0?SLR〔1?LR〔1?無二義文法,故選c。4、選a。5、選c。多選解答：1、一個(gè)LR分析器包括一個(gè)總控程序和一張分析表,選a、d。2、選c、e。3、選a、c、d、e。4、在LR分析表的構(gòu)造中有可能存在"移進(jìn)"/"歸約"和"歸約"/"歸約"沖突；故選c、e。5、選a、b、c、d、e。6、選a、b、c、e。7、選a、c、d、e。填空解答：1、一張分析表每個(gè)入口2、任意首部3、規(guī)范句型句柄4、輸入串活前綴5、活前綴項(xiàng)目集合LR分析算法6、歸約接受移進(jìn)待約7、自左至右分析采用最右推導(dǎo)的逆過程即最左歸約向右查看0個(gè)字符綜合解答：首先將文法G拓廣為G[S′]：S′→SS→AS|b A→SA|a〔1文法G[S′]的LR〔0項(xiàng)目是：1、S′→·S 5、S→AS· 9、A→S·A 2、S′→S· 6、S→·b 10、A→SA· 3、S→·AS 7、S→b· 11、A→·a 4、S→A·S 8、A→·SA 12、A→a·2、列出構(gòu)成文法LR〔0項(xiàng)目集規(guī)范族。用ε-CLOSURE〔閉包辦法構(gòu)造文法G′的LR〔0項(xiàng)目集規(guī)范族如下：I0：1、S′→·S I3： 9、A→S·A I6：12、A→a·3、S→·AS 8、A→·SA I7：7、S→b·8、A→·SA 3、S→·AS 11、A→·a 6、S→·b6、S→·b 11、A→·aI1：2、S′→S· I4：10、A→SA·9、A→S·A 4、S→A·S 8、A→·SA 3、S→·AS11、A→·a 6、S→·b3、S→·AS 8、A→·SA 6、S→·b 11、A→·aI2：4、S→A·S I5： 5、S→AS·3、S→·AS 9、A→S·A 6、S→·b 8、A→·SA 8、A→·SA 11、A→·a11、A→·a 3、S→·AS 6、S→·b注意：I1中的S′→S·和A→·SA是由狀態(tài)I0中的1和3讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目；,而I4中的A→SA和A→A·S則是由I3中的9和3讀入一個(gè)A字符后得到的下一個(gè)項(xiàng)目；I5中的S→AS·和A→S·A 則是由I4中的4和8讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目。狀態(tài)全體構(gòu)成了文法G′的LR〔0規(guī)范族。第七章一、單項(xiàng)選擇題1、中間代碼生成所依據(jù)的是。a.語法規(guī)則 b.詞法規(guī)則 c.語義規(guī)則 d.等價(jià)變換規(guī)則2、四元式之間的聯(lián)系是通過實(shí)現(xiàn)的。a.指示器 b.臨時(shí)變量 c.符號(hào)表 d.程序變量3、后綴式ab+cd+/可用表達(dá)式來表示。a.a+b/c+d b.<a+b>/<c+d> c.a+b/<c+d> d.a+b+c/d4、表達(dá)式〔┓A∨B∧〔C∨D的逆波蘭表示為。a.┓AB∨∧CD∨b.A┓B∨CD∨∧c.AB∨┓CD∨∧d.A┓B∨∧CD∨5、中間代碼的樹型表示++A++ABCD+a.A+B+C+D b.A+<B+C>+D c.<A+B>+C+D d.<A+B>+<C+D>6、四元式表示法的優(yōu)點(diǎn)為。a.不便于優(yōu)化處理,但便于表的更動(dòng) b.不便于優(yōu)化處理,但節(jié)省存儲(chǔ)空間c.便于優(yōu)化處理,也便于表的更動(dòng) d.便于表的更動(dòng),也節(jié)省存儲(chǔ)空間7、終結(jié)符具有屬性。a.傳遞 b.繼承 c.抽象 d.綜合二、多頂選擇題1、中間代碼主要有。a．四元式 b．二元式 c．三元式 d．后綴式 e．間接三元式2、下面中間代碼形式中,能正確表示算術(shù)表達(dá)式a+b+c的有。+a+a+bc++caba．a(chǎn)b+c+ b．a(chǎn)bc++ c． d．e．a(chǎn)+b+c3、在下面的語法制導(dǎo)翻譯中,采用拉鏈-回填技術(shù)。a．賦值語句 b．goto語句c．條件語句 d．循環(huán)語句4、下列中間代碼形式有益于優(yōu)化處理。 a．三元式 b．四元式 c．間接三元式 d．逆波蘭表示法 e．樹形表示法5、在編譯程序中安排中間代碼生成的目的是。a．便于進(jìn)行存儲(chǔ)空間的組織 b．利于目標(biāo)代碼的優(yōu)化c．利于編譯程序的移植 d．利于目標(biāo)代碼的移植e．利于提高目標(biāo)代碼的質(zhì)量+a*ab*+c+a*ab*+caba．a(chǎn)b+c* b．a(chǎn)bc*+ c．a(chǎn)+b*c d．e．7、三地址代碼語句具體實(shí)現(xiàn)通常有表示方法。a．逆波蘭表示 b．三元式 c．間接三元式 d．樹形表示 e．四元式三、填空題1、中間代碼有等形式,生成中間代碼主要是為了使。2、語法制導(dǎo)翻譯既可以用來產(chǎn)生代碼,也可以用來產(chǎn)生指令,甚至可用來對(duì)輸入串進(jìn)行。 3、當(dāng)源程序中的標(biāo)號(hào)出現(xiàn)"先引用后定義"時(shí),中間代碼的轉(zhuǎn)移地址須持時(shí)才能確定,因而要進(jìn)行。 4、文法符號(hào)的屬性有兩種,一種稱為,另一種稱為。5、后綴式abc-/所代表的表達(dá)式是,表達(dá)式<a-b>*c可用后綴式表示。 6、用一張輔以的辦法來表示中間代碼,這種表示法稱為間接三元式。四、綜合題1、給出下列表達(dá)式的逆波蘭表示〔后綴式：①a*<-b+c>②<A∨B>∧<C∨┑D∧E>2、寫出算術(shù)表達(dá)式：A+B*<C-D>+E/<C-D>↑N的①四元式序列；②三元式序列；③間接三元式序列單選解答1、選c。2、四元式之間的聯(lián)系是通過臨時(shí)變量實(shí)現(xiàn)的,故選b。3、選b。4、選b。5、選d。6、四元式表示法的優(yōu)點(diǎn)與間接三元式相同,故選c。7、選d。多選解答1、選a、c、d、e。2、b、d的中間代碼不能正確表示a+b+c,而e不是中間代碼：故選a、c。3、凡涉及到跳轉(zhuǎn)的語句都需要采用拉鏈——回填技術(shù),故選b、c、d。4、選b、c。5、選b、d。6、選b、e。7、選b、c、e。填空解答1、逆波蘭記號(hào)、樹形表示、三元式、四元式 目標(biāo)代碼的優(yōu)化容易實(shí)現(xiàn)2、中間 目標(biāo) 解釋執(zhí)行3、標(biāo)號(hào)定義 回填4、繼承屬性 綜合屬性5、a/<b-c> ab-c*6、間接碼表 三元式表綜合解答1、①abc+*;②AB∨CD┑E∧∨∧22、①表達(dá)式的四元式序列： ②表達(dá)式的三元式序列③間接三元式序列 〔1<-,C,D,T1> 〔1<-,C,D>⑴〔1<-,C,D> 〔2<*,B,T1,T2> 〔2<*,B,<1>>⑵〔2<*,B,<1>> 〔3<+,A,T2,T3> 〔3<+,A,<2>>⑶〔3<+,A,<2>> 〔4<-,C,D,T4> 〔4<-,C,D>⑴⑷<↑,<1>,N> 〔5<↑,T4,N,T5> 〔5<↑,<4>,N>⑷⑸</,E,<4>>⑹</,E,T5,T6>⑹</,E,<5>>⑸⑹<+,<3>,<5>>⑺<+,T3,T6,T7>⑺<+,<3>,<6>>⑹第八章一、單項(xiàng)選擇題1、編譯程序使用區(qū)別標(biāo)識(shí)符的作用域。a.說明標(biāo)識(shí)符的過程或函數(shù)名 b.說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次c.說明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層次d.標(biāo)識(shí)符的行號(hào)2、在目標(biāo)代碼生成階段,符號(hào)表用于。a.目標(biāo)代碼生成 b.語義檢查 c.語法檢查 d.地址分配3、過程信息表不包含。a.過程入口地址 b.過程的靜態(tài)層次 c.過程名 d.過程參數(shù)信息4、下列關(guān)于標(biāo)識(shí)符和名字?jǐn)⑹鲋?正確的是。a.標(biāo)識(shí)符有一定的含義 b.名字是一個(gè)沒有意義的字符序列c.名字有確切的屬性 d.a~c都不正確二、多項(xiàng)選擇題1、符號(hào)表的每一項(xiàng)均包含。a.名字欄 b.類型欄 c.信息欄 d.值欄 e.a~d均包含2、對(duì)編譯程序所用到的符號(hào)表,涉及的操作有。a.填寫或更新信息欄內(nèi)容 b.填入新名 c.給定名字,訪問它的有關(guān)信息d.雜湊技術(shù) e.線性表和排序二叉樹3、源程序中的錯(cuò)誤一般有。a.詞法錯(cuò)誤 b.語法錯(cuò)誤 c.語義錯(cuò)誤d.編譯錯(cuò)誤 e.違反環(huán)境限制的錯(cuò)誤三、填空題1、符號(hào)表中名字欄內(nèi)容有兩種填寫方式,它們是填寫和填寫。2、詞法分析階段的錯(cuò)誤主要是,可通過的辦法糾正錯(cuò)誤。3、符號(hào)表中名字的有關(guān)信息在和過程中陸續(xù)填入。4、在目標(biāo)代碼生成階段,符號(hào)表是的依據(jù)。四、問答題：1、在編譯過程中為什么要建立符號(hào)表？單選解答：1、b2、d3、b4、c多選解答：1、a、c2、a、b、c3、a、b、c、e填空解答：1、標(biāo)識(shí)符標(biāo)識(shí)符地址及長度2、拼寫錯(cuò)誤最小距離匹配3、詞法分析語法語義分析4、地址分配問答題解答：在編譯過程中始終要涉及到對(duì)一些語法符號(hào)的處理,這就需要用到語法符號(hào)的相關(guān)屬性。為了在需要時(shí)能找到這些語法成分及其相關(guān)屬性,就必須使用一些表格來保存這些語法成分及其屬性,這些表格就是符號(hào)表。第九章一、單項(xiàng)選擇題1、程序所需的數(shù)據(jù)空間在程序運(yùn)行前可確定,稱為管理技術(shù)。a.動(dòng)態(tài)存儲(chǔ) b.棧式存儲(chǔ) c.靜態(tài)存儲(chǔ) d.堆式存儲(chǔ)2、堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守原則。a.先請(qǐng)先放 b.先請(qǐng)后放 c.后請(qǐng)先放 d.任意3、靜態(tài)分配允許程序出現(xiàn)。a.遞歸過程 b.可變體積的數(shù)據(jù)項(xiàng)目 c.靜態(tài)變量 d.待定性質(zhì)的名字4、在編譯方法中,動(dòng)態(tài)存儲(chǔ)分配的含義是。a.在運(yùn)行階段對(duì)源程序中的數(shù)組、變量、參數(shù)等進(jìn)行分配b.在編譯階段對(duì)源程序中的數(shù)組、變量、參數(shù)進(jìn)行分配c.在編譯階段對(duì)源程序中的數(shù)組、變量、參數(shù)等進(jìn)行分配,在運(yùn)行時(shí)這些數(shù)組、變量、參數(shù)的地址可根據(jù)需要改變d.以上都不正確5、在編譯時(shí)有傳名功能的高級(jí)程序語言是。a.Fortran b.Basic c.Pascal d.ALGOL6、棧式動(dòng)態(tài)分配與管理在過程返回時(shí)應(yīng)做的工作有。a.保護(hù)SP b.恢復(fù)SP c.保護(hù)TOP d.恢復(fù)TOP二、多項(xiàng)選擇題1、下面需要在運(yùn)行階段分配存儲(chǔ)空間。a.數(shù)組 b.指針變量 c.動(dòng)態(tài)數(shù)組d.靜態(tài)變量 e.動(dòng)態(tài)變量2、棧式動(dòng)態(tài)分配允許。a.遞歸過程 b.分程序結(jié)構(gòu) c.動(dòng)態(tài)