編譯原理模擬試題和答案編譯原理模擬試題和答案d

【題型】簡答題題干】現(xiàn)有文法G[S]：BTidt|￡請問aidtccb是句型還是句子，為什么？STaAbATBcA|B【答案】S=aAb=aBcAb=aidtcAb=aidtcBcAb=aidtc￡cAb=aidtccAb=aidtccBb=aidtcc￡b=aidtccb是句型，也是句子。【題型】簡答題題干】設(shè)有文法G1[S]：〈S〉f〈N〉〈N〉f〈D〉|〈N〉〈D〉〈D—0|l|2??|9試寫出028的最左推導(dǎo)過程。【答案】028的最左推導(dǎo)：〈S〉=〉〈N〉=〉〈N〉〈D〉=〉〈N〉〈D〉〈D〉=〉〈D〉〈D〉〈D〉=〉0〈D〉〈D〉=〉02〈D〉=〉02&題型】填空題【題干】遞歸下降法不允許任一非終結(jié)符是直接 遞歸的。【答案】左;題型】填空題【題干】在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部 錯誤和部分語義錯誤?！敬鸢浮空Z法;題型】填空題【題干】把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由 完成的?！敬鸢浮繀R編器;題型】填空題【題干】語法分析器的輸出是 ?！敬鸢浮空Z法單位;7題干】循環(huán)優(yōu)化的三種重要技術(shù)包括刪除歸納變量、代碼外提和 ?！敬鸢浮繌姸认?8題干】寫出表達式(a+b)/(a-b)-a(a+b*c)的三元式序列及四元式序列。【答案】三元式：(l).(+,a,b)(2).(-,a,b)⑶.(/，⑴,⑵)⑷.(*,b,c)(5).(+,a,⑷)(6).(—,⑶，⑸)四元式：(l).(+,a,b,Tl)(2).(-,a,b,T2)⑶.(/,T1,T2,T3)⑷.(*,b,c,T4)⑸.(+,a,T4,T5)(6).(-,T3,T5,T6)9題干】什么是句子？什么是語言？【答案】設(shè)G是一個給定的文法，S是文法的開始符號，如果S—x(其中xGVT*)，則稱x是文法的一個句子。(2)設(shè)G[S]是給定文法，則由文法G所定義的語言L(G)可描述為：L(G)={x|S—x,xWVT*}。10型】簡答題【題干】為表達式w+(a+b)*(c+d/(e-10)+8)寫出相應(yīng)的逆波蘭表示?！敬鸢浮縲ab+cde10-/+8+*+11干】現(xiàn)有文法G[S]：STaAbATBcA|BBTidt|e請問aidtcBcAb是句型還是句子，為什么？【答案】S=aAb=aBcAb=aidtcAb=aidtcBcAb是句型但不是句子。12干】構(gòu)造正規(guī)式相應(yīng)的NFA:1(0|1)*101?！敬鸢浮?(0|1)*101對應(yīng)的NFA為題型】簡答題13干】簡述DFA與NFA有何區(qū)別？【答案】DFA與NFA的區(qū)別表現(xiàn)為兩個方面:一是NFA可以若干個開始狀態(tài)，而DFA僅只一個開始狀態(tài)。另一方面，DFA的映象M是從KXE到K,而NFA的映象M是從KXE到K的子集，即映象M將產(chǎn)生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。14簡答題【題干】試寫出VT={0,1}上下述集合的正則表達式：集合：所有以1開始和結(jié)束的符號串?！敬鸢浮?（0|1）*1|115【題型】簡答題【題干】現(xiàn)有文法G[S]：STaAbATBcA|BB-Tidt|￡請問ab是句型還是句子，為什么？【答案】S=aAb=aBb=a￡b=ab是句型，是句子?！绢}型】簡答題16干】寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭?！敬鸢浮课姆℅（N）：N—AB|BA—AC|DB-l|3|5|7|9D-B|2|4|6|8C-O|D【題型】簡答題17干】常見的存儲分配策略有幾種？它們都適合于什么性質(zhì)的語言？【答案】有三種分配存儲空間的方式：（1） 靜態(tài)分配：若在編譯階段就能確定源程序中各個數(shù)據(jù)實體的存儲空間大小，則可以采用較簡單的靜態(tài)存儲管理。適合靜態(tài)管理的語言應(yīng)具備條件：數(shù)組上下界是常數(shù)、過程調(diào)用不允許遞歸、不允許動態(tài)建立數(shù)據(jù)實體。（2） 棧式分配：適用于允許遞歸調(diào)用的程序設(shè)計語言；（3） 堆式分配：對于允許程序在運行時為變量動態(tài)申請和釋放存儲空間的語言，采用堆式分配是最有效的解決方案。18何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？【答案】優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標代碼三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。19【題型】填空題【題干】掃描器的任務(wù)是從源程序中識別出一個個 ?！敬鸢浮繂卧~符號;型】填空題【題干】若源程序是用高級語言編寫的， 是機器語言程序或匯編程序?！敬鸢浮磕繕顺绦?【題型】填空題TOC\o"1-5"\h\z干】若源程序是用高級語言編寫的，則其翻譯程序稱為 ?！敬鸢浮烤幾g程序;干】編譯方式與解釋方式的根本區(qū)別在于 ?！敬鸢浮渴欠裆赡繕舜a;23對編譯程序而言，輸入數(shù)據(jù)是 ?！敬鸢浮吭闯绦?24干】產(chǎn)生式是用于定義 的一種書寫規(guī)則?！敬鸢浮空Z法成分;25干】對編譯程序而言，輸出結(jié)果是 ?！敬鸢浮磕繕顺绦?26【題干】語法分析最常用的兩類方法是自上而下和 分析法?！敬鸢浮孔韵露?27干】語法分析器可以發(fā)現(xiàn)源程序中的 。語法錯誤;28編譯程序是一種 程序。【答案】解釋;29干】后綴式abc-/所代表的表達式是 。【答案】a/(b-c);30自頂向下的語法分析方法的基本思想是：從文法的開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進行 ，試圖推導(dǎo)出文法的句子，使之與給定的輸入串匹配?！敬鸢浮恐苯油茖?dǎo);31自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進行 ，力求歸約到文法的開始符號?！敬鸢浮恐苯託w約;32【題干】常用的參數(shù)傳遞方式有 ，傳值和傳名?！敬鸢浮總鞯刂?33【題干】一個句型中的最左 稱為該句型的句柄?！敬鸢浮亢唵味陶Z;34TOC\o"1-5"\h\z通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分，還應(yīng)包括 。【答案】35設(shè)G是一個給定的文法，S是文法的開始符號，如果S—x(其中xWV*),則稱x是文法G的一個 ?！敬鸢浮烤湫?36語法分析器的輸入是 ?！敬鸢浮繂卧~符號串;37四元式之間的聯(lián)系是通過 實現(xiàn)的。臨時變量;38對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為 。語義規(guī)則;39四種形式語言文法中，1型文法又稱為 文法。上下文有關(guān)文法;40文法分為四種類型，即0型、1型、2型、3型。其中2型文法是 。上下文無關(guān)文法;41由規(guī)范推導(dǎo)所得的句型稱為 。規(guī)范句型;42一個典型的編譯程序中，不僅包括詞法分析、語法分析、 、代碼優(yōu)化、目標代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。中間代碼生成;43從功能上說，程序語言的語句大體可分為 語句和說明性語句兩大類。執(zhí)行性;44【題干】已知文法G(S)：S-a|A|(T)T7S|S寫出句子((a,a),a)的規(guī)范歸約過程及每一步的句柄?！敬鸢浮烤湫蜌w約規(guī)則句柄((aa),a)S—aa((Sa),a)T-SS((Ta),a)S—aa((TS)a)T—T,ST,S((T),a)S—(T)(T)(S,a)T—SS(T,a)S—aa(T,S)T—T,ST,S(T)S一(T)(T)S45】設(shè)文法G(S)：STSiAlAATA+BIBBT)A*|(構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)?！敬鸢浮績?yōu)先關(guān)系表i+()*i><<<+>><<>(>>>)<<<*>>>優(yōu)先函數(shù)：i+()*f26616g1466146型】綜合題【題干】設(shè)有非確定的有限自動機NFAM=({A,B,C},{0,1},6,{A},{C}),其中：5(A,0)={C}6(A,1)={A,B}6(B,1)={C}6(C,1)={C}。請畫出狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖。答案】狀態(tài)轉(zhuǎn)換距陣為：601ACA,BB0CC0C狀態(tài)轉(zhuǎn)換圖為47已知文法G[S]%S—aSb|Sb|b，試證明文法G[S]為二義文法。【答案】由文法G[S]：S—aSb|Sb|b，對句子aabbbb對應(yīng)的兩棵語法樹為:因此，文法G[S]為二義文法。48型】綜合題【題干】設(shè)文法G