編譯原理復(fù)習(xí)試題

...wd......wd......wd...一、單項選擇題概述局部1．構(gòu)造編譯程序應(yīng)掌握。DA.源程序B.目標(biāo)語言C.編譯方法D.以上三項都是2．編譯程序絕大多數(shù)時間花在上。DA.出錯處理B.詞法分析C.目標(biāo)代碼生成D.表格管理3．編譯程序是對。DA.匯編程序的翻譯B.高級語言程序的解釋執(zhí)行C.機器語言的執(zhí)行D.高級語言的翻譯4.將編譯程序分成假設(shè)干“遍〞，是為了。BA.提高程序的執(zhí)行效率B.使程序的構(gòu)造更為清晰C利用有限的機器內(nèi)存并提高機器的執(zhí)行效率D.利用有限的機器內(nèi)存但降低了機器的執(zhí)行效率詞法分析局部1．DFAM(見圖1-1)承受的字集為。D圖1-1圖1-1XY0011B.以0結(jié)尾的二進(jìn)制數(shù)組成的集合C.含奇數(shù)個0的二進(jìn)制數(shù)組成的集合D.含偶數(shù)個0的二進(jìn)制數(shù)組成的集合2．詞法分析器的輸出結(jié)果是。CA.單詞的種別編碼B.單詞在符號表中的位置C.單詞的種別編碼和自身值D.單詞自身值3．正規(guī)式M1和M2等價是指。CA.M1和M2的狀態(tài)數(shù)相等B.M1和M2的有向邊條數(shù)相等C.M1和M2所識別的語言集相等D.M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等4．詞法分析器的加工對象是。CA．中間代碼 B．單詞 C．源程序 D．元程序5．同正規(guī)式〔a|b〕*等價的正規(guī)式為。DA．(a|b)+ B．a(chǎn)*|b* C．(ab)* D．(a*|b*)+6.兩個DFA等價是指：。DA.這兩個DFA的狀態(tài)數(shù)一樣B.這兩個DFA的狀態(tài)數(shù)和有向弧條數(shù)都相等C.這兩個DFA的有向弧條數(shù)相等D.這兩個DFA承受的語言一樣7.以下符號串不可以由符號集S＝{a,b}上的正閉包運算產(chǎn)生的是：〔A〕A.εB.aC.aaD.ab8．稱有限自動機A1和A2等價是指________。DA．A1和A2都是定義在一個字母表上的有限自動機B．A1和A2狀態(tài)數(shù)和有向邊數(shù)相等C．A1和A2狀態(tài)數(shù)或有向邊數(shù)相等D．A1和A2所能識別的字符串集合相等9．同正規(guī)式〔a|b〕+等價的正規(guī)式是_______。BA．〔a|b〕*B．〔a|b〕〔a|b〕*C．〔ab〕*〔ab〕D．〔a|b〕|〔a|b〕*語法分析1．在標(biāo)準(zhǔn)歸約中，用來刻畫可歸約串。BA.直接短語B.句柄C.最左素短語D.素短語2．假設(shè)B為非終結(jié)符，則A→α·Bβ為工程。DA.歸約 B.移進(jìn)C.承受 D.待約3．如果文法G是無二義的，則它的任何句子α。AA.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定一樣B.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C.最左推導(dǎo)和最右推導(dǎo)必定一樣D.可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹一樣4．以下動作中，不是自下而上分析動作的是：。BA.移進(jìn) B.展開C.承受D.報錯6．假設(shè)a為終結(jié)符，則A→α·aβ為工程。BA.歸約B.移進(jìn)C.承受 D.待約7．語法分析時所依據(jù)的是。AA.語法規(guī)則B.詞法規(guī)則C.語義規(guī)則D.等價變換規(guī)則8．文法G：S→xSx|y所識別的語言是。CA.xyxB.(xyx)* C.xnyxn(n≥0)D.x*yx*9．以下動作中，不是自上而下分析動作的是：。CA.匹配 B.展開C.移進(jìn)D.報錯10．假設(shè)A為非終結(jié)符，則A→α·為工程。AA.歸約 B.移進(jìn)C.承受 D.待約11．文法G：S→xSx|xS|y所識別的語言是。AA.xmyxn(m≥n≥0)B.(xyx)* C.xnyxn(n≥0)D.x*yx*13．由文法的開場符號出發(fā)經(jīng)過假設(shè)干步〔包括0步〕推導(dǎo)產(chǎn)生的文法符號序列稱為______。BA．語言B．句型C．句子D．句柄14．在自上而下的語法分析中，應(yīng)從開場分析。CA．句型 B．句子 C．文法開場符號 D．句柄15．一個文法G，假設(shè)________，則稱它是LL〔1〕文法。CA．G中不含左遞歸B．G無二義性C．G的LL〔1〕分析表中不含多重定義的條目D．G中產(chǎn)生式不含左公因子16．工程S’→S.為。DA.歸約工程B.移進(jìn)工程C.待約工程D.承受工程17.語法分析器的輸入是：。AA.Token序列B.源程序C.目標(biāo)程序D.符號表18.在LR〔0〕的Action表中，如果某行中存在標(biāo)記為“rj〞的欄，則：。AA.該行必定填滿“rj〞B.該行未必填滿“rj〞C.其他行可能也有“rj〞D.goto表中也可能有“rj〞19.LR分析過程中棧內(nèi)存儲的是。AA.活前綴B.前綴C.歸約活前綴D.工程20.文法G：S→xxS|y所識別的語言是。DA．xxynB．(xxy)nC．xxnyxD．(xx)ny21.假設(shè)狀態(tài)k含有工程“A→α.〞，對任意非終結(jié)符a，都用規(guī)則“A→α〞歸約的語法分析方法是。BA．LALR分析法 B．LR(0)分析法C．LR(1)分析法 D．SLR(1)分析法22.在SLR〔1〕的Action表中，如果某行中存在標(biāo)記為“rj〞的欄，則：。BA.該行必定填滿“rj〞B.該行未必填滿“rj〞C.其他行可能也有“rj〞D.goto表中也可能有“rj〞23.一個指明了在LR分析過程中的某個時刻所能看到產(chǎn)生式多大一局部。DA.活前綴B.前綴C.歸約活前綴D.工程24.假設(shè)狀態(tài)k含有工程“A→α.〞，且僅當(dāng)輸入符號a∈FOLLOW(A)時，才用規(guī)則“A→α〞歸約的語法分析方法是。DA．LALR分析法 B．LR(0)分析法C．LR(1)分析法 D．SLR(1)分析法25．設(shè)有文法G[T]:T→T*F|FF→F↑P|PP→(T)|a該文法句型T*P↑(T*F)的句柄是以下符號串。CA.〔T*F〕B.T*FC.PD.P↑(T*F)26．LR分析表中的轉(zhuǎn)移表〔goto〕是以作為列標(biāo)題的。BA．終結(jié)符B．非終結(jié)符C．終結(jié)符或非終結(jié)符D．表示狀態(tài)的整形數(shù)27．編譯程序的語法分析器必須輸出的信息是。AA．語法錯誤信息 B．語法規(guī)則信息C．語法分析過程 D．語句序列28．以下工程中為可移進(jìn)工程的是。CA．E′→E.B．L→.C．L→.-LD．F→L*F.29．LR分析表中的動作表〔action〕是以作為列標(biāo)題的。DA．終結(jié)符B．非終結(jié)符C．終結(jié)符或非終結(jié)符D．終結(jié)符和完畢符#30．以下工程中為可歸約工程的是。BA．E′→.EB．L→.C．L→-.LD．F→L*.F33．LR分析器的核心局部是一張分析表，該表由_________組成。DA．ACTION表B．GOTO表C．預(yù)測分析表D．ACTION表和GOTO表34．在遞歸下降子程序方法中，假設(shè)文法存在左遞歸，則會使分析過程產(chǎn)生_______。DA．回溯B．非法調(diào)用C．有限次調(diào)用D．無限循環(huán)35．最左簡單子樹的葉結(jié)點，自左至右排列組成句型的________。CA．短語B．句型C．句柄D．間接短語36．由文法的開場符號出發(fā)經(jīng)過假設(shè)干步〔包括0步〕推導(dǎo)產(chǎn)生的文法符號序列中，如果只含有終結(jié)符，則文法符號序列稱為________。CA．語言B．句型C．句子D．句柄37．LL〔1〕分析法中“1〞的含義是在輸入串中查看一個輸入符號，其目的是________。CA．確定最左推導(dǎo)B．確定句柄C．確定使用哪一個產(chǎn)生式進(jìn)展展開D．確定是否推導(dǎo)語義分析1.表達(dá)式〔┐a∨b〕∧〔e∨f〕的逆波蘭表示為。BA．┐ab∨∧ef∨ B．a(chǎn)┐b∨ef∨∧C．a(chǎn)b∨┐ef∨∧D．a(chǎn)┐b∨∧ef∨2．中間代碼生成時所依據(jù)的是。CA．詞法規(guī)則B．語法規(guī)則C．語義規(guī)則D．等價變換規(guī)則3．-a-(b*c/(c-d)+(-b)*a)的逆波蘭表示是。(@代表后綴式中的求負(fù)運算符)CA.abc*cd-b@a*+/-@B.a@bc*cd-b@a*+/-C.a@bc*cd-/b@a*+-D.a@bc*/cd-b@a*+-4．有文法G及其語法制導(dǎo)翻譯如下所示〔語義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運算符〕：E→E(1)∧T{E.val=E(1).val*T.val}E→T{E.val=T.val}T→T(1)#n{T.val=T(1).val+n.val}T→n{T.val=n.val}則分析句子1∧2∧3#4其值為。CA.10B.34C.14D.545．有文法G及其語法制導(dǎo)翻譯如下所示〔語義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運算符〕：E→E(1)∧T{E.val=E(1).val*T.val}E→T{E.val=T.val}T→T(1)#n{T.val=T(1).val+n.val}T→n{T.val=n.val}則分析句子2∧3#4其值為。CA.10B.21C.14D.246．間接三元式表示法的優(yōu)點為。AA.采用間接碼表，便于優(yōu)化處理 B.節(jié)省存儲空間，不便于表的修改C.便于優(yōu)化處理，節(jié)省存儲空間D.節(jié)省存儲空間，不便于優(yōu)化處理7．文法G[S]及其語法制導(dǎo)翻譯定義如下：產(chǎn)生式 語義動作S’→S print(S.num)S→(L) S.num=L.num+1S→a S.num=0L→L(1),S L.num=L(1).num+S.numL→S L.num=S.num假設(shè)輸入為(a,(a))，且采用自底向上的分析方法，則輸出為。CA．0 B．1 C．2 D．48．四元式之間的聯(lián)系是通過____________實現(xiàn)的。BA．指示器B．臨時變量C．符號表D．程序變量9．表達(dá)式〔┐a∨b〕∧〔c∨d〕的逆波蘭表示為。BA．┐ab∨∧cd∨ B．a(chǎn)┐b∨cd∨∧C．a(chǎn)b∨┐cd∨∧ D．a(chǎn)┐b∨∧cd∨10．表達(dá)式a+b+c+d的逆波蘭表示為。BA．a(chǎn)+bc+d+ B．a(chǎn)b+c+d+C．a(chǎn)b+cd++ D．a(chǎn)bc+d++11.有文法G及其語法制導(dǎo)翻譯如下所示〔語義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運算符〕：E→E(1)∧T{E.val=E(1).val*T.val}E→T{E.val=T.val}T→T(1)#n{T.val=T(1).val+n.val}T→n{T.val=n.val}則分析句子3∧3#4其值為。BA.10B.21C.14D.2412．表達(dá)式a+b+c的逆波蘭表示為。BA．a(chǎn)+bc+ B．a(chǎn)b+c+C．+abc+ D．a(chǎn)bc++13.文法G[S]及其語法制導(dǎo)翻譯定義如下：產(chǎn)生式 語義動作S’→S print(S.num)S→(L) S.num=L.num+1S→a S.num=0L→L(1),S L.num=L(1).num+S.numL→S L.num=S.num假設(shè)輸入為(a,a)，且采用自底向上的分析方法，則輸出為。BA．0 B．1 C．2 D．414．有一語法制導(dǎo)翻譯定義如下：S→bAbprint“1〞A→〔Bprint“2〞A→aprint“3〞B→aA)print“4〞假設(shè)輸入序列為b〔a〔a〔aa〕〕〕b，且采用自底向上的分析方法，則輸出序列為。BA．32224441 B．34242421C．12424243 D．3444221215．賦值語句X:=-(a+b)/(c-d)-(a+b*c)的逆波蘭表示是。CXab+cd-/-bc*a+-:=Xab+/cd-bc*a+--:=Xab+-cd-/abc*+-:=Xab+cd-/abc*+--:=16．有一語法制導(dǎo)翻譯定義如下，其中+表示符號連接運算：S→B printB.versB→a B.vers=aB→b B.vers=bB→Ba B.vers=a+B.versB→Bb B.vers=b+B.vers假設(shè)輸入序列為abab，且采用自底向上的分析方法，則輸出序列為。DA．a(chǎn)abb B．a(chǎn)bab C．bbaa D．baba17．編譯程序不能檢查、處理的錯誤是程序中的________。BA．靜態(tài)語義檢查B．動態(tài)語義檢查C．語法錯誤D．詞法錯誤〔優(yōu)化、存儲、錯誤管理〕1.在編譯過程中，如果遇到錯誤應(yīng)該。CA.把錯誤理解成局部的錯誤B.對錯誤在局部范圍內(nèi)進(jìn)展糾正，繼續(xù)向下分析C.當(dāng)發(fā)現(xiàn)錯誤時，跳過錯誤所在的語法單位繼續(xù)分析下去D.當(dāng)發(fā)現(xiàn)錯誤時立即停頓編譯，待用戶改正錯誤后再繼續(xù)編譯二、填空題概述局部：1．編譯程序的開發(fā)常常采用自編譯、穿插編譯、自展和移植等技術(shù)實現(xiàn)。2．解釋程序和編譯程序的區(qū)別在于是否生成目標(biāo)程序。3．如果編譯程序生成的目標(biāo)程序是匯編語言程序，則源程序的執(zhí)行分為3個階段：編譯階段、匯編階段和運行階段。4．編譯程序工作過程中，第一階段輸入是源程序，最后階段的輸出為目標(biāo)程序。5．編譯過程通?？煞譃?個階段詞法分析階段、語法分析階段、語義分析和中間代碼生成階段、優(yōu)化階段和目標(biāo)代碼生成階段。6．如果編譯階段生成的目標(biāo)程序是某特定計算機系統(tǒng)的機器代碼程序，則源程序的執(zhí)行分為兩大階段：編譯階段和運行階段。7．對編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是目標(biāo)程序。8．貫穿于編譯程始終的工作有符號表處理和出錯處理。詞法分析局部：1．詞法分析的工作是將源程序中的字符串變換成單詞符號流的過程，所遵循的是語言的構(gòu)詞規(guī)則。2．假設(shè)兩個正規(guī)式所表示的正規(guī)集一樣，則認(rèn)為二者是等價的。3．假設(shè)兩個正規(guī)式所表示的正規(guī)集一樣，則認(rèn)為二者是等價的。4．正規(guī)式R1和R2等價是指_______表示一樣的正規(guī)集。5．詞法分析器的輸入是源程序字符串，輸出構(gòu)造是二元式〔單詞種別，單詞自身的值〕。詞法分析所遵循的是語言的構(gòu)詞規(guī)則。6．確定的有限自動機是一個五元組，包含的五個元分別是：狀態(tài)集合、字母表、初態(tài)、終態(tài)集、狀態(tài)轉(zhuǎn)換函數(shù)集合。7．有限自動機是更一般化的狀態(tài)轉(zhuǎn)換圖，它分為確定的有限自動機DFA和非確定的有限自動機NFA兩種。8．NFA和DFA的區(qū)別主要有兩點：其一是NFA可以有假設(shè)干個初始狀態(tài)，而DFA僅有一個初始狀態(tài)；其二是NFA的狀態(tài)轉(zhuǎn)換函數(shù)f不是單值函數(shù)，而是一個多值函數(shù)。語法分析局部：〔基本概念、LL〔1〕、LR〔0〕、SLR〔1〕、遞歸下降子程序〕語法分析的方法通常分為兩類：自上而下分析方法和自下而上分析方法。2．文法中的終結(jié)符集和非終結(jié)符集的交集是空集。3．一個句型的最左直接短語稱為該句型的___句柄________________。4．標(biāo)準(zhǔn)歸約是最右推導(dǎo)的逆過程。5．自下而上語法分析中分析器的動作有_移進(jìn)、____歸約、__承受_、__報錯__。6．自上而下語法分析中分析器的動作有___匹配終結(jié)符____、__展開非終結(jié)符_、__分析成功、報錯__。7．常用的自上而下語法分析方法有遞歸下降子程序方法和預(yù)測分析表方法〔LL〔1〕方法〕。8．常用的自下而上語法分析方法有算符優(yōu)先分析法和LR分析法。9．一個LL(1)分析器由一張LL(1)分析表〔預(yù)測分析表〕、一個先進(jìn)后出分析棧和一個控制程序〔表驅(qū)動程序〕組成。10．一個LR分析器由分析棧、分析表和總控程序三個局部組成。11．LR(0)分析法的名字中，“L〞表示自左至右分析輸入串，“R〞表示采用最右推導(dǎo)的逆過程即最左歸約?！?〞表示向右查看0個字符。12．LL(1)分析法中，第一個L的含義是從左到右掃描輸入串；第二個L的含義是分析過程中采用最左推導(dǎo)；“1〞的含義是只需向右查看一個符號就可以決定若何推導(dǎo)。13．LR(1)文法的含義是：L說明_____自左至右掃描輸入串__，R說明___采用最右推導(dǎo)的逆過程〔最左歸約〕方法進(jìn)展分析__。14．一個上下文無關(guān)文法是LL(1)文法的充分必要條件是：對每一個非終結(jié)符A的任何兩個不同產(chǎn)生式A→α|β，有下面的條件成立：〔1〕FIRST(α)∩FIRST(β)=?；〔2〕假假設(shè)，則有FIRST(α)∩FOLLOW(A)=?。15．對于LL〔1〕文法中的任何產(chǎn)生式A→α|β，則需要滿足__First(_α)∩First(β)=Φ、_假設(shè)_β=>*ε,則_First(_α)∩__Follow(A)=_Φ_。16．LR分析器的核心局部是一張分析表，該表包括動作〔ACTION〕表和狀態(tài)轉(zhuǎn)換〔GOTO〕表等兩個子表。17．關(guān)于非終結(jié)符A的直接左遞歸產(chǎn)生式：A→Aα|β，其中α、β是任意的符號串且β不以A開頭，則可以將A的產(chǎn)生式改寫為右遞歸的形式為：A→βA’,A’→αA’|ε。18．在消除回溯，提取公共左因子時，關(guān)于A的產(chǎn)生式A→δβ1|δβ2|…|δβi|βi+1|…|βj，可以改寫為：A→δA’|βi+1|…|βj，A’→β1|…|βi。19．設(shè)G[S]是一文法，如果符號串x是從識別符號推導(dǎo)出來的，即有x，則稱x是文法G[S]的____句型__，假設(shè)x僅由終結(jié)符號組成，即，則稱x為文法G[S]的__句子。20．文法G[S]:S→eT|RTT→DR|εR→dR|εD→a|bd求FIRST(S)={e，d，a，b，ε}______；FOLLOW(D)=_{d，#}。語義處理局部：1．文法符號的屬性有兩種，一種稱為繼承屬性，另一種稱為綜合屬性。2．編譯過程中，常見的中間語言形式有逆波蘭表示法、抽象語法樹、三元式、四元式。3．語法制導(dǎo)翻譯的方法就是為每個產(chǎn)生式配上一個翻譯子程序〔語義動作或語義子程序〕，并在語法分析的同時執(zhí)行它們。4．編譯過程中，常見的中間語言形式有逆波蘭表示法、抽象語法樹、三元式、四元式。6．文法符號的屬性有兩種，一種稱為繼承屬性，另一種稱為綜合屬性。7．四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的。8．在屬性文法中，終結(jié)符只有____綜合屬性。10．語法制導(dǎo)翻譯的方法就是為每個產(chǎn)生式配上一個翻譯子程序〔語義動作或語義子程序〕，并在語法分析的同時執(zhí)行它們。11．目前較常見的語言語義的描述形式是__屬性文法______，并使用__語法制導(dǎo)翻譯方法完成對語法成分的翻譯?！矁?yōu)化、存儲、錯誤管理〕1.代碼優(yōu)化的含義是：對代碼進(jìn)展等價變換，使得變換后的代碼具有更高的時間效率和空間效率。2.按照優(yōu)化對象所涉及的程序范圍，優(yōu)化分為局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。3.基本塊，是指程序中—順序執(zhí)行的語句序列，其中只有一個入口和一個出口。4.從編譯角度看，分配目標(biāo)程序數(shù)據(jù)空間的基本策略有：靜態(tài)分配策略、棧式動態(tài)分配策略和堆式動態(tài)分配策略。三、判斷題1．設(shè)r和s分別為正規(guī)式，則有L(r|s)=L(r)|L(s).。(×)2．一個文法的所有句型的集合形成該文法所能承受的語言。(×)3．語法分析之所以采用上下文無關(guān)文法是因為它的描述能力最強。(×)4．由于LR(0)分析表構(gòu)造簡單，所以它的描述能力強，適用面寬；LR(1)分析表因構(gòu)造復(fù)雜而描述能力弱，適用面窄。(×)5．逆波蘭表示法表示表達(dá)式時無需使用括號。(√)6．自動機M和M’的狀態(tài)個數(shù)不同，則二者必不等價。(×)7．LL(1)文法一定不含左遞歸和二義性。(√)8．所有LR分析器的總控程序都是一樣的，只是分析表各有不同。(√)9．無論是三元式表示還是間接三元式表示的中間代碼，其三元式在三元式表中的位置一旦確定就很難改變。(√)10．三地址語句類似于匯編語言代碼，可以看成中間代碼的一種抽象形式。(√)11．最左推導(dǎo)也被稱為標(biāo)準(zhǔn)推導(dǎo)?！病痢?2．運算對象排列的先后順序在后綴式和中綴式中不同?！病痢?3．出現(xiàn)在移進(jìn)-歸約分析器棧中的內(nèi)容被稱為文法G的活前綴?！病獭?4．LR方法可以分析含有左遞歸的文法?！病獭?5．三元式的編號具有雙重含義，既代表此三元式，又代表三元式存放的結(jié)果?！病獭?6．語義規(guī)則中的屬性有兩種：綜合屬性與繼承屬性?！病獭?7．移進(jìn)-歸約分析器的格局中棧的內(nèi)容一般是文法符號與狀態(tài)?！病獭?8．由于遞歸下降子程序方法較LL〔1〕方法簡單，因此它要求文法不必是LL〔1〕文法?！病痢?9．四元式的編號具有雙重含義，既代表此四元式，又代表四元式存放的結(jié)果?！病痢?0．用高級語言編寫的源程序必須經(jīng)過編譯，產(chǎn)生目標(biāo)程序后才能運行?！病痢?1．源程序到目標(biāo)程序的變換是等價變換，即兩者構(gòu)造不同，但語義是一致的?！病獭?2．對于任何一個正規(guī)式e，都存在一個DFAA，使得L〔e〕=L〔A〕?！病獭?3．最小化的DFA，它的狀態(tài)數(shù)最小。〔√〕24．NFA確實定化算法具有消除ε邊的功能?！病獭?5．每個非終結(jié)符產(chǎn)生的終結(jié)符號串都是該語言的子集。〔×〕26．一個語言的文法是不唯一的?！病獭?7．語法錯誤校正的目的是為了把錯誤改正過來?！病痢?8．源程序和目標(biāo)程序是等價關(guān)系?！病獭?9．編譯程序中錯誤處理的任務(wù)是對檢查出的錯誤進(jìn)展修改。〔×〕30．使用有限自動機可以實現(xiàn)單詞的識別。〔√〕31．一個非確定的有限自動機NFA可以通過多條路徑識別同一個符號串。〔√〕32．最小化的DFA所識別承受的正規(guī)集最小?！病痢?3．一個語言〔如C語言〕的句子是有窮的?！病痢?4．LL〔1〕方法又稱為預(yù)測分析方法。〔√〕35．一個LL〔1〕文法是無二義和無回溯方法?！病獭?6．語法分析器可以檢查出程序中的所有錯誤?！病痢?7．LR分析法是自上而下的語法分析方法?！病痢橙?、多項選擇題1.編譯器的各個階段的工作都涉及到〔AE〕A.表格處理B.詞法分析C.語法分析D.語義分析E.出錯處理2.令＝{a,b}，則上的符號串的全體可用下面的正規(guī)式表示?！睞BE〕A.(a|b)*B.(a*|b*)*C.(a|b)+D.(ab)*E.(a*b*)*3.自上而下的分析方法有：〔AD〕A.遞歸下降分析法B.LR〔0〕分析法C.LALR〔1〕分析法D.LL〔1〕分析法E.SLR〔1〕分析法4.文法G：G[S]：S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD是〔A〕。A.0型文法B.1型文法C.2型文法D.3型文法E.上下文有關(guān)文法5.對LR分析表的構(gòu)造，有可能存在的動作沖突有：〔AD〕A.移進(jìn)/歸約沖突B.移進(jìn)/移進(jìn)沖突C.歸約沖突D.歸約/歸約沖突E.移進(jìn)沖突6.一個編譯器可能有的階段為〔ABCDE〕A.詞法分析B.語法分析C.語義分析D.中間代碼生成E.目標(biāo)代碼生成7令＝{a,b}，則上的所有以b開頭，后跟假設(shè)干個〔可為0個〕ab的符號串的全體可用下面的正規(guī)式表示。〔AB〕A.b(ab)*B.(ba)*bC.b(a|b)+D.(ba)+bE.b(a|b)*8.自下而上的分析方法有：〔BCE〕A.遞歸下降分析法B.LR〔0〕分析法C.LALR〔1〕分析法D.LL〔1〕分析法E.SLR〔1〕分析法9.一般來說，編譯器可分為前端和后端，以下編譯階段可被劃分為編譯的前端的有：〔ABCDE〕A.詞法分析B.語法分析C.語義分析D.中間代碼生成E.中間代碼優(yōu)化10．令＝{a,b}，則上的符號串的全體可用下面的正規(guī)式表示?！睞BE〕A.(a|b)*B.(a*|b*)*C.(a|b)+D.(ab)*E.(a*b*)*11．以下符號串是符號集＝{a,b}上的正規(guī)式的有：〔ABCDE〕A.εB.aC.abD.(ab｜a)(ab｜a)E.ab｜ab12．正規(guī)式服從的代數(shù)規(guī)律有：〔ABDE〕A.“或〞運算服從交換律B.“或〞運算服從結(jié)合律C.“連接〞運算服從交換律D.“連接〞運算服從結(jié)合律E.“連接〞運算可對“或〞運算進(jìn)展分配13．令＝{a,b}，則上的所有以b開頭，后跟假設(shè)干個〔可為0個〕ab的符號串的全體可用下面的正規(guī)式表示。〔AB〕A.b(ab)*B.(ba)*bC.b(a|b)+D.(ba)+bE.b(a|b)*14．一個LR分析器包括：〔ADE〕A.一個總控程序B.一個工程集C.一個活前綴D.一個分析棧E.一張分析表15．LR分析器的核心局部是一張分析表，該表包括〔DE〕等子表。A.LL〔1〕分析表B.LR〔1〕分析表C.SLR〔1〕分析表D.Action表E.goto表16．Action表中的每一項Action[S,a]所表示的動作可能為：〔ABCD〕A.移進(jìn)B.承受C.歸約D.出錯E.待約五．簡答題1．構(gòu)造正規(guī)表達(dá)式((a|b)*|aa)*b的NFA。解：2．設(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} 試構(gòu)造相應(yīng)確實定有限自動機M′。解：對照自動機的定義M=(S,Σ,f,So,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動機。 先畫出NFAM相應(yīng)的狀態(tài)圖，如以以以下圖所示。用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣，如下表所示。將轉(zhuǎn)換矩陣中的所有子集重新命名，形成下表所示的狀態(tài)轉(zhuǎn)換矩陣，即得到 M′=({0,1,2},{a,b},f,0,{1,2})，M′狀態(tài)轉(zhuǎn)換圖如以以以下圖所示?！沧⒁猓捍祟}由于集合的命名和先后順序不同，可能最終結(jié)果不同?！?．畫出編譯程序的總體構(gòu)造圖，簡述各局部的主要功能。解：編譯程序的總體框圖如下所示：〔1〕詞法分析器，又稱掃描器，它承受輸入的源程序，對源程序進(jìn)展詞法分析，識別出一個個單詞符號，其輸出結(jié)果是二元式(單詞種別，單詞自身的值)流。〔2〕語法分析器，對單詞符號串進(jìn)展語法分析〔根據(jù)語法規(guī)則進(jìn)展推導(dǎo)或歸約〕，識別出程序中的各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的句子?！?〕語義分析及中間代碼生成器，按照語義規(guī)則對語法分析器歸約出〔或推導(dǎo)出〕的語法單位進(jìn)展語義分析并把它們翻譯成一定形式的中間代碼。編譯程序可以根據(jù)不同的需要選擇不同的中間代碼形式，有的編譯程序甚至沒有中間代碼形式，而直接生成目標(biāo)代碼?！?〕優(yōu)化器對中間代碼進(jìn)展優(yōu)化處理。一般最初生成的中間代碼執(zhí)行效率都對比低，因此要做中間代碼的優(yōu)化，其過程實際上是對中間代碼進(jìn)展等價替換，使程序在執(zhí)行時能更快，并占用更小的空間?！?〕目標(biāo)代碼生成器，把中間代碼翻譯成目標(biāo)程序。中間代碼一般是一種與機器無關(guān)的表示形式，只有把它再翻譯成與機器硬件直接相關(guān)的機器能識別的語言，即目標(biāo)程序，才能在機器上運行。〔6〕表格管理模塊保持一系列的表格，登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。編譯程序各個階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需要的信息也大多從表格中獲取，整個編譯過程都在不斷和表格打交道?！?〕出錯處理程序?qū)Τ霈F(xiàn)在源程序中的錯誤進(jìn)展處理。如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤，把有關(guān)錯誤信息報告給用戶。編譯程序的各個階段都有可能發(fā)現(xiàn)錯誤，出錯處理程序要對發(fā)現(xiàn)的錯誤進(jìn)展處理、記錄，并反映給用戶。4．構(gòu)造一個DFA，它承受Σ={0,1}上所有滿足如下條件的字符串：每個1后面都有0直接跟在右邊。解：〔1〕0*(0|10)*0*或者(0|10)*〔2〕=1\*GB3①NFA〔2分〕XX0εY0ε10201ε03ε=2\*GB3②子集法確定化II0I1{X,0,1,3,Y}{0,1,3,Y}{2}{0,1,3,Y}{0,1,3,Y}{2}{2}{1,3,Y}-{1,3,Y}{1,3,Y}{2}重新命名狀態(tài)，即得：S0112322334-443=3\*GB3③最小化首先分為終態(tài)集和非終態(tài)集{3}{1,2,4}因為10=220=240=4狀態(tài)均屬于集合{1,2,4}，所以對于輸入符號0不能區(qū)分開1，2，4三個狀態(tài)；11=321=341=3狀態(tài)均屬于集合{3}，所以對于輸入符號1也不能區(qū)分開1，2，4三個狀態(tài)；因此最終的狀態(tài)劃分即為:{3}{1,2,4}，其對應(yīng)的DFA如以以以下圖所示：0001105．寫出C語言標(biāo)識符集〔字母或下劃線開頭的由字母、數(shù)字、下劃線構(gòu)成的串〕的正規(guī)式。解答：用D表示數(shù)字0-9，用L表示字母a-z|A-Z，則C語言標(biāo)識符的正規(guī)式為：〔L|_〕〔L|D|_〕*語法分析局部：6．構(gòu)造一文法，使其描述的語言L={ω|ω∈(a,b)*，且ω中含有一樣個數(shù)的a和b}。解：S→ε|aA|bBA→b|bS|aAAB→a|aS|bBB7．對于文法G(S)：S→(L)|aS|aL→L,S|S(1)畫出句型(S,(a))的語法樹。(2)寫出上述句型的所有短語、直接短語和句柄。解：(1)句型(S,(a))的語法樹如以以以下圖所示：(2)從語法樹中可以找到〔3分〕短語：a;(a);S;S,(a);(S,(a))直接短語：a;S句柄：S8．令文法G[N]為G[N]:N→D|NDD→0|1|2|3|4|5|6|7|8|9給出句子568的最左、最右推導(dǎo)。解：最左推導(dǎo)：NNDNDDDDD5DD56D568最右推導(dǎo)：NNDN8ND8N68D685688．文法G[A]:A→aABl|aB→Bb|d 試給出與G[A]等價的LL(1)文法G[A′]；解：G[A′]：A→aA′A′→ABl|εB→dB′B′→bB′|ε9．試構(gòu)造下述文法的SLR(1)分析表。G[A]:A→aABl|aB→Bb|d解：拓廣文法〔0〕S→A〔1〕A→aABl〔2〕A→a〔3〕B→Bb〔4〕B→dFirst〔A〕={a}follow〔A〕={#，d}First〔B〕=4c2ymwafollow〔B〕={l}SLR〔1〕分析表如下：abdl#AB0S211ACC2S2R2R233S454R45S7S66R1R17R310.試構(gòu)造下述文法的LL(1)分析表。G[S]:S→〔L〕|aL→L，S|S解：消除左遞歸：G(S):S(L)|a LSL’ L’,SL’|ε構(gòu)造FIRST集，如下： 〔1〕FIRST(S)={(,a} 〔2〕FIRST(L)={(,a}〔3〕FIRST(L’)={,,ε}構(gòu)造FOLLOW集如下：〔1〕FOLLOW(S)={#,,,)}〔2〕FOLLOW(L)={)}〔3〕FOLLOW(L’)={)}LL(1)分析表()a,#SS(L)SaLLSL’LSL’L’L’εL’,SL’11．文法G[S]:S→aSbS|bSaS|ε 試證明G[S]是二義文法證明：該文法產(chǎn)生的語言是a的個數(shù)和b的個數(shù)相等的串的集合。該文法二義，例如句子abab有兩種不同的最左推導(dǎo)。SaSbSabSabaSbSababSababSaSbSabSaSbSabaSbSababSabab12．文法Ｇ：

S→(L|a

L→S,L|)判斷是不是LL〔1〕文法，如果是請構(gòu)造文法Ｇ的預(yù)測分析表，如果不是請說明理由。【解】1〕求各非終結(jié)符的FISRT集和FOLLOW集： First〔S〕={(,a} FIRST(L)={〕}FIRST(S)={(,),a} FOLLOW(S)={,#} FOLLOW(L)=FOLLOW(S)={,#}FIRST((L)∩{a}=ΦFIRST(S,L)∩{)}=Φ所以是LL〔1〕文法2〕預(yù)測分析表：(a,}#SS→(LS→aLL→S,LL→S,LL→)13．文法 SAa|bAc|dc|bdaAd構(gòu)造識別活前綴的DFA。請根據(jù)這個DFA來判斷該文法是不是SLR(1)文法并說明理由。【解】S’S’.SS.AaS.bAcS.dcS.bdaA.dI0Sb.AcSb.daA.dI3daSd.cAd.I4AS’S.I1SSA.aI2ASAa.I5bSbA.cI6dSdc.I8Sbd.aAd.I7cSbAc.I9Sbda.I10caFollow(S)={#}Follow(A)={a,c}I4存在沖突且Follow(A)∩{c}={c}I7存在沖突且Follow(A)∩{a}={a}所以不是SLR(1)文法14．設(shè)有文法G[S]:S→S*S|S+S|(S)|i該文法是否為二義文法,并說明理由【解】該文法是二義文法，因為該文法存在句子i*i+i,該句子有兩棵不同的語法樹如以以下圖。15.構(gòu)造下面文法的LL〔1〕分析表。G[D]:DTLTint|realLidRR,idR|【解】FIRST(T)={intreal}FOLLOW(T)={id}FIRST(L)={id}FOLLOW(L)={#}FIRST(R)={,}FOLLOW(R)={#}FIRST(D)={intreal}FOLLOW(D)={#}因為FIRST(int)∩FIRST(real)=ΦFIRST(,idR)∩FOLLOW(R)=Φ所以是LL〔1〕文法，LL〔1〕分析表如下：intrealid,#DDTLDTLTTintTrealLLidRRR,idRR16．給定文法S→aS|bS|a，下面是拓廣文法和識別該文法所產(chǎn)生的活前綴的DFA。判斷該文法是否是SLR(1)文法：如果是構(gòu)造其SLR(1)分析表，如果不是請說明理由。 (1)將文法G(S)拓廣為G(S’)：(0)S’→S(1)S→aS(2)S→bS(3)S→a(2)識別該文法所產(chǎn)生的活前綴的DFA如圖1所示?！窘狻孔⒁獾綘顟B(tài)I1存在“移進(jìn)-歸納〞沖突，計算S的FOLLOW集合：FOLLOW(S)={#}{a}∩∩FOLLOW(R)=Φ可以采用SLR沖突消解法，得到如下的SLR分析表。從分析表可以看出，表中沒有沖突項，所以該文法是SLR(1)文法。表1SLR分析表ACTIONGOTO狀態(tài)ab#S0S1S231S1S2r342S1S253acc4r15r217．證明下面文法S→AaAb|BbBaA→εB→ε，是LL〔1〕文法，但不是SLR〔1〕文法。證明：〔1〕first〔AaAb〕={a}first〔BbBb〕=，有first〔AaAb〕∩first〔BbBb〕=Φ所以根據(jù)LL〔1〕文法的定義，該文法是LL〔1〕文法?！?〕為了構(gòu)造識別活前綴的DFA，初態(tài)集包含如下四個工程：S→.AaAbS→.BbBaA→.B→.但該工程中有兩個可歸約工程：A→.B→.，產(chǎn)生歸約-歸約沖突，而follow〔A〕={a，b}，follow〔B〕={a，b}，有follow〔A〕∩follow〔B〕≠Φ，所以使用向前看一個終結(jié)符的方法不能解決此沖突，所以該文法不是SLR〔1〕文法。18．文法G(S)：S→S*aP|aP|*aPP→+aP|+a(1)將文法G(S)改寫為LL(1)文法G’(S)；(2)寫出文法G’(S)的預(yù)測分析表。解：〔1〕消除左遞歸，文法變?yōu)椋篠→aPS’|*aPS’S’→*aPS’|εP→+aP|+a提取公共左因子，文法變?yōu)镚’(S)：S→aPS’|*aPS’S’→*aPS’|εP→+aP’P’→P|ε〔2〕計算每個非終結(jié)符的FIRST集和FOLLOW集：FIRST(S)={a,*} FOLLOW(S)={#}FIRST(S’)={*,ε} FOLLOW(S’)={#}FIRST(P)={+} FOLLOW(P)={*,#}FIRST(P’)={+,ε} FOLLOW(P’)={*,#}構(gòu)造該文法的預(yù)測分析表如下：*+a#SS→*aPS’S→aPS’S’S’→*aPS’→εPP→+aP’P’P’→εP’→PP’→ε19．文法G(S)：S→aS|bS|a(1)構(gòu)造識別該文法所產(chǎn)生的活前綴的DFA；(2)判斷該文法是LR(0)還是SLR(1)，并構(gòu)造所屬文法的LR分析表。解：〔1〕將文法G(S)拓廣為G’(S’)：(0)S’→S(1)S→aS(2)S→bS(3)S→a識別該文法所產(chǎn)生的活前綴的DFA：〔2〕在狀態(tài)I2存在“移近-歸約〞沖突，因此該文法不是LR(0)文法。計算S的FOLLOW集合：FOLLOW(S)={#}I2中的沖突用FOLLOW集合可以解決，所以該文法是SLR(1)文法。構(gòu)造SLR(1)分析表如下：狀態(tài)ACTIONGOTOab#S0s2s311acc2s2s3r343s2s354r15r220．構(gòu)造文法S→AaAb|BbBaA→εB→ε，的預(yù)測分析表。答：first〔S〕={a，b},First〔AaAb〕={a}，F(xiàn)irst〔BbBa〕=Follow〔A〕={a，b}Follow〔B〕={a，b}ab$SS→AaAbS→BbBaAA→εA→εBB→εB→ε21．設(shè)有如下文法：G[E]：E→EWT|TT→T/F|FF→〔E〕|a|b|cW→+|-證明符號串a(chǎn)/(b-c)是句子。解答：有推導(dǎo)ETT/FF/Fa/Fa/(E)a/(EWT)a/(TWT)a/(FWT)a/(bWT)a/(b-T)a/(b-c)，即從文法開場符號E能夠推導(dǎo)出a/(b-c)，所以a/(b-c)是文法G[E]的句子。55．對于以下文法G[S]：S→Sb|bAA→aA|a〔1〕構(gòu)造一個與G等價的LL〔1〕文法G′。〔2〕對于文法G′,構(gòu)造相應(yīng)的LL〔1〕分析表。解：〔1〕G′：S→bAS′S′→bS′|εA→aA′A′→A|ε〔2〕FIRST〔S〕=FIRST〔S′〕={b，ε}FIRST〔A〕={a}FIRST〔A′〕={a，ε}FOLLOW〔S〕={#}FOLLOW〔S′〕={#}FOLLOW〔A〕={b，#}FOLLOW〔A′〕=〔b，#〕LL〔1〕分析表：ab#SS→bAS′S′S′→bS′S′→εAA→aA′A′A′→AA′→εA′→ε22．文法G[S]如下：構(gòu)造該文法的LR〔0〕分析表。G[S]：S→BBB→aB|b解：拓廣文法：〔0〕S→S〔1〕S→BB〔2〕B→aB〔3〕B→b識別活前綴的DFA如下：LR(0)分析表如下：狀態(tài)ActionGotoab#SB0S3S4121acc2S3S453S3S464R3R3R35R1R1R16R2R2R2語義分析與中間代碼生成：23．給定文法：S→(L)|aL→L,S|S請書寫語義規(guī)則，求輸出句子中每一個a的括號嵌套深度。解：用繼承屬性depth表示嵌套深度，則 S’→S S.depth=0 S→(L) L.depth=S.depth+1 S→a print(S.depth) L→L(1),S L(1).depth=L.depth;S.depth=L.depth L→S S.dep