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

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