編譯基本知識(shí)期末試題(8套含答案解析大題集)

1、編譯原理期末試題（五）、單項(xiàng)選擇題（共10小題，每小題2分，共20分）1 .語(yǔ)言是A .句子的集合產(chǎn)生式的集合C.符號(hào)串的集合句型的集合2 .編譯程序前三個(gè)階段完成的工作是A .詞法分析、語(yǔ)法分析和代碼優(yōu)化B.代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成D .詞法分析、語(yǔ)法分析和代碼優(yōu)化3 .一個(gè)句型中稱為句柄的是該句型的最左A .非終結(jié)符號(hào)B .短語(yǔ)C.句子 D .直接短語(yǔ)下推自動(dòng)機(jī)識(shí)別的語(yǔ)言是0型語(yǔ)言B. 1型語(yǔ)言C.2型語(yǔ)言D . 3型語(yǔ)言5 .掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語(yǔ)法單位即字符B.單詞C .句子D .句型

2、6 .對(duì)應(yīng)Chomsky四種文法的四種語(yǔ)言之間的關(guān)系是Lo Li L2 L3B. L3L2 Li LoL3= L2 LiLoD. Lo LiL2= L37 .詞法分析的任務(wù)是C 識(shí)別句子D.生成目標(biāo)代碼8 .常用的中間代碼形式不含A .三兀式B.四元式C .逆波蘭式D .語(yǔ)法樹9 .代碼優(yōu)化的目的是A.節(jié)省時(shí)間B.節(jié)省空間C.節(jié)省時(shí)間和空間D .把編譯程序進(jìn)行等價(jià)交換10 .代碼生成階段的主要任務(wù)是A .把高級(jí)語(yǔ)言翻譯成匯編語(yǔ)言B .把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言C .把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼D .把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言二、填空題（本大題共5小題，每小題2分，共10 分）1 .編譯程

3、序首先要識(shí)別出源程序中每個(gè)（單詞），然后再分析每個(gè)（句子）并翻譯其意義。2 .編譯器常用的語(yǔ)法分析方法有 （自底向上）和（自頂向下）兩種。3 .通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語(yǔ)法和語(yǔ)義分析是對(duì)源程序（綜合）。主要分為兩大類，即（靜態(tài)的（分析），中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對(duì)源程序的4 .程序設(shè)計(jì)語(yǔ)言的發(fā)展帶來了日漸多變的運(yùn)行時(shí)存儲(chǔ)管理方案, 存儲(chǔ)分配）方案和（動(dòng)態(tài)存儲(chǔ)分配）方案。5 .對(duì)編譯程序而言，輸入數(shù)據(jù)是（源程序），輸出結(jié)果是（目標(biāo)程序）。三、名詞解釋題（共5小題，每小題4分，共20分）1 .詞法分析 詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào)，

4、按照詞法規(guī)則 從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位, 并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語(yǔ)法分析程序。2 . LL(1)文法若文法的任何兩個(gè)產(chǎn)生式 A I都滿足下面兩個(gè)條件:(1 ) FIRST( ) FIRST()=(2 )若，那么 FIRST( ) FOLLOW( A )=。我們把滿足這兩個(gè)條件的文法叫做LL(1)文法，其中的第一個(gè) L代表從左向右掃描輸入，第二個(gè) L表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號(hào)。除了沒有公共左因子外,LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3 .語(yǔ)法樹句子的樹結(jié)構(gòu)表示法稱為語(yǔ)法樹

5、(語(yǔ)法分析樹或語(yǔ)法推導(dǎo)樹 )。給定文法 G=(V N, Vt, P, S),對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹。這棵樹具有下列特征:(1)根節(jié)點(diǎn)的標(biāo)記是開始符號(hào)So(2)每個(gè)節(jié)點(diǎn)的標(biāo)記都是 V中的一個(gè)符號(hào)。(3)若一棵子樹的根節(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳1 A2-Ar，那么A A1 A2Ar一定是P中的一條產(chǎn)生式。若一標(biāo)記為A的節(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則AVn。用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫的程序，必須先送入計(jì)算機(jī)，經(jīng)過轉(zhuǎn)換成用機(jī)器的句型；若w中僅含終結(jié)符號(hào)，則 w為文法G所產(chǎn)生的句子。4 . LR(O)分析器所謂LR（O）分析，是指從左至右掃描和自底向上的語(yǔ)法

6、分析，且在分析的 每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號(hào)，并至多再 向前查看0個(gè)輸入符號(hào)，就能確定相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dòng)作移進(jìn)還是按某一產(chǎn)生式進(jìn)行歸約等）。5.語(yǔ)言和文法 文法就是語(yǔ)言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式:G=(V N, Vt, P, S)其中：VN是非空有窮集合，稱為非終結(jié)符號(hào)集合；VT是非空有窮集合, 稱為終結(jié)符號(hào)集合；P是產(chǎn)生式的集合（非空）；S是開始符號(hào)（或識(shí)別符號(hào)）。這里，Vn QVt= , S Vn。V=V n U Vt，稱為文法 G的字母表，它是出現(xiàn)

7、 文法產(chǎn)生式中的一切符號(hào)的集合。文法G所描述的語(yǔ)言用L（G）表示，它由文法 G所產(chǎn)生的全部句子組成，即L（G）=x| S *x，其中S為文法開始符號(hào)，且 x Vt _簡(jiǎn)單的說，文法描述的語(yǔ)言是該文法一切句子的集合。四、簡(jiǎn)答題（共4小題，每小題5分，共20分）1 編譯程序和高級(jí)語(yǔ)言有什么區(qū)別語(yǔ)言表示的目標(biāo)程序（這個(gè)過程即編譯），才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過程 的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語(yǔ)言源文件。編譯程序轉(zhuǎn) 換過的叫目標(biāo)程序，也就是機(jī)器語(yǔ)言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來 將匯編語(yǔ)言編寫的程序，按照一一對(duì)應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的程

8、序。解釋型編譯程序?qū)⒏呒?jí)語(yǔ)言程序的一個(gè)語(yǔ)句，先解釋成為一組機(jī)器語(yǔ)言的指令, 然后立即執(zhí)行，執(zhí)行完了，取下一組語(yǔ)句解釋和執(zhí)行，如此繼續(xù)到完成一個(gè)程序”對(duì)話”，隨時(shí)止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進(jìn)行人和計(jì)算機(jī)的可以修改高級(jí)語(yǔ)言的程序。BASIC語(yǔ)言就是解釋型高級(jí)語(yǔ)言。編譯型編譯程序?qū)?級(jí)語(yǔ)言編寫的程序，一次就會(huì)部翻譯成機(jī)器語(yǔ)言表示的程序，而且過程進(jìn)行很快,在過程中，不能進(jìn)行人機(jī)對(duì)話修改。FORTRAN 語(yǔ)言就是編譯型咼級(jí)語(yǔ)言。2 .編譯程序的工作分為那幾個(gè)階段詞法分析、語(yǔ)法分析和語(yǔ)義分析是對(duì)源程序進(jìn)行的分析（稱為編譯程序的前端）,而中間代碼生成、代碼優(yōu)化和代碼生成三個(gè)階段合稱為對(duì)源程序

9、進(jìn)行綜合（稱為編譯程序的后端），它們從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序。3 .簡(jiǎn)述自下而上的分析方法。所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)；或者說從語(yǔ)法樹的末端開始，步步向上“歸約”，直到根節(jié)點(diǎn)。4 簡(jiǎn)述代碼優(yōu)化的目的和意義。代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對(duì)程序代碼進(jìn)行一種等價(jià)變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標(biāo)程序運(yùn)行時(shí)所需要的時(shí)間短，同時(shí)所占用的存儲(chǔ)空間少。五、綜合應(yīng)用題（共3小題，每小題10分，共30分）1 .證明下述文法G :SaSbS|aS|d是二義性文法。解: 一個(gè)文法，如果存在某個(gè)句子有

10、不只一棵語(yǔ)法分析樹與之對(duì)應(yīng)，那么稱這個(gè) 文法是二義性文法。句子aadbd有兩棵語(yǔ)法樹。如下圖:(1)d由此可知，S aSbS|aS|d定義的文法是二義性文法。柄？2 .對(duì)于文法句型baSb解：baSb為句型baSb的相對(duì)于S的短語(yǔ)，ba 為句型 baSb 的相對(duì)于 A 的短語(yǔ)，Sb 為句型baSb的相對(duì)于B的短語(yǔ)，且為直接短語(yǔ)，a為句型baSb的相對(duì)于B的短語(yǔ)，且為直接 短語(yǔ)和句柄。3 .設(shè)有非確定的有自限動(dòng)機(jī)NFA M=(A , B, C, 0, 1, , A , C)，其中:(A , 0)=C (A , 1)=A , B (B , 1)=C (C, 1)=C。請(qǐng)畫出狀態(tài)轉(zhuǎn)換距陣和狀 態(tài)轉(zhuǎn)換

11、圖。解：狀態(tài)轉(zhuǎn)換距陣為:狀態(tài)轉(zhuǎn)換圖為A 0AA1ACA, BBCCC11.編譯原理期末試題(六)編譯原理型文法也稱為正規(guī)文法。B 1C 2文法不是LL(1)的。遞歸 B右遞歸C 2 型樣題D 3D含有公共左因子的文法Ef E+E|E*E|i的句子i*i+i*i的不同語(yǔ)法分析樹的總數(shù)為B3C5D7四元式之間的聯(lián)系是通過實(shí)現(xiàn)。A臨時(shí)變量 B指示器 C符號(hào)表D程序變量】5.同心集合并可能會(huì)產(chǎn)生的新沖突為A二義 B移進(jìn)/移進(jìn)C移進(jìn)/歸約D歸約/歸約【】6.代碼優(yōu)化時(shí)所依據(jù)的是A語(yǔ)法規(guī)則B詞法規(guī)則C等價(jià)變換規(guī)則D語(yǔ)義規(guī)則【】7 .表達(dá)式a-(-b)*c的逆波蘭表示為Aa-bc*Babc*-Cab-Dab

12、c-*(注：為單目10 .一個(gè)過程的DISPLAY表的內(nèi)容是它的直接外層的DISPLAY表的內(nèi)容加減運(yùn)算符)【】8.過程的DIS PLAY表記錄了A 過程的連接數(shù)據(jù)B 過程的嵌套層次C 過程的返回地址D 過程的入口地址填空題3 .對(duì)于文法G1禾口 G2,若有L(G1)=L(G2)(或 G1和G2的語(yǔ)言相同)，則稱文法G1 和 G2是等價(jià)的。4 .對(duì)于文法GE: Ef T|E+TTf F|T*F FtPF|PPf (E)|i，句型 T+T*F+i 的句柄是T，最左素短語(yǔ)是T*F。最右推導(dǎo)的逆過程稱為規(guī)范歸約，也稱為最左歸約。規(guī)范規(guī)約中的可規(guī)約串是 句柄，算符優(yōu)先分析中的可規(guī)約串是最左素短語(yǔ)(A

13、V B)A(C V ?D A E)的逆波蘭式是 ABVCD ? EA VA在屬性文法中文法符號(hào)的兩種屬性分別稱為繼承屬性和綜合屬性(次序可換)。9.符號(hào)表的每一項(xiàng)是由名字欄和地址分配 兩個(gè)欄目組成。在目標(biāo)代碼生成階段，符號(hào)表是 地址分配 的依據(jù)。上本過程的SP的地址三 有窮自動(dòng)機(jī)M接受字母表 =0,1上所有滿足下述條件的串：每個(gè)1都有0直 接跟在右邊。構(gòu)造一個(gè)最小的 DFA M及和M等價(jià)的正規(guī)式?！尽俊尽克淖C明正規(guī)式（ab）*a與正規(guī)式a（ba）*等價(jià)（用構(gòu)造他們的最小的 DFA方法）。這兩十TF規(guī)式最線郁可得到最筒的TJKA如圖所示=所以這兩個(gè)正規(guī)式等價(jià)4五 寫一個(gè)文法，使其語(yǔ)言是:L =

14、1n0m1m0n | m,n >0 【】【】五文法G: S f 1S0 | AA f 0A1 |£六對(duì)文法GSS f aSb|PP f bPc | bQc(1) 它是否是算符優(yōu)先文法？請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表(2) 文法GS消除左遞歸、提取左公因子后是否是LL( 1)文法？請(qǐng)證實(shí)?！尽俊尽?.求出GS的FIRSTVT集和LASTVT集:FIERSTVT( S)=a,bLASTBVT ( S)=b,cFIERSTVT (P )=bLASTBVT ( P) =cFIERSTVT(Q)=aLASTBVT (Q) =a構(gòu)造優(yōu)先關(guān)系表為:abca< ><>b<

15、>c>>由于在優(yōu)先關(guān)系中同時(shí)出現(xiàn)了a<a和a>a以及b<b和b>b，所以該文法不是算符優(yōu)先文法。2.消除左遞歸和提取左公因子后的文法為:7 aSb|P7 Pc |Qc7 aQ 'Q' 7 aQ ' | £求具有相同左部的兩個(gè)產(chǎn)生式的Select集的交集:Select(S 7 aSb) nSelect(S 7 p) = a QFirst(P) = a nb=na=nc=Select(P 7 Pc) nselect(P '7 Qc) = First(P)nFirst(Q)=bSelect(Q ' 7 aQ

16、' ) nSelect(Q ' 7) = a nFollow(Q) = a所以修改后的文法是 LL (1 )文法。七已知文法G為:S，fSaAdbAcaecbed試構(gòu)造它的LR(1)項(xiàng)目集、可歸前綴圖和 LR (1 )分析表?！尽俊敬鸢福骸繕?gòu)造LR(1)分析表如下:狀態(tài)actio ngotoabcde#SA0S2S311ac2S5c3S74S85S9r56S107r5S118r19r310r211r4八已知源程序如下:P rod:=0;i:=1;while i <20 dobeginp rod:=prod+ai*bi;i:=i+1end;試按語(yǔ)法制導(dǎo)翻譯法將源程序翻譯成四

17、元式序列（設(shè)A是數(shù)組a的起始地址，B是數(shù)組b的起始地址；機(jī)器按字節(jié)編址，每個(gè)數(shù)組元素占四個(gè)字節(jié)）【答案：】八四冠杼JprDde :=0100101102103104105101C7108If i<20 goto 104goto 114T2:=A-4T3:=T2 T1T5:=B-4105110111112113114T6：=T5T4T7：=T3*T6 prod, z7goto 102九設(shè)有以下程序段P rocedure P( x,y,z)beginY :=y*3;Z:=X+z;end;begina:=5; b:=2;p(a*b,a,a);prin t(a);end若參數(shù)傳遞的方法分別為（1

18、）傳值、（2 ）傳地址、（3）傳名，試問結(jié)果分別什么？(3)傳名 45【】【】十（1）傳值 5 ；（ 2）傳地址 25 ；十對(duì)以下文法，請(qǐng)寫出關(guān)于括號(hào)嵌套層數(shù)的屬性文法。（為S,L引入屬性h,用來記錄輸出配對(duì)的括號(hào)個(gè)數(shù)）文法規(guī)則語(yǔ)義規(guī)則s-(T)Sf iT-T,ST-S文袪規(guī)則語(yǔ)義規(guī)則S-* (T)(S-h:=T.h+l;)SiT一咗 fS<T.h:=T.h+S.h;Tf ST,h:= S.h; 答案:1一 對(duì)PL/0語(yǔ)言的while語(yǔ)句 while 條件B DO 語(yǔ)句S 的編譯程序,請(qǐng)?jiān)诳杖碧幪羁眨瓿稍撜Z(yǔ)句的編譯算法:switch (SYM) case WHILES YM:ex仁ex

19、GetSym();CONDITION(SymSetAdd(DOS YM,FS YS)丄EV,TX);CX2=CXGEN(J PC,O,O);if (SYM=DOS YM)GetSymQelse Error(18);STATEMENT(FS YS,LEV,TX);GEN(J MP ,0,CX1);CODECX2.A=CXbreak;編譯原理期末試題(七)、回答下列問題：(30分)1. 什么是S-屬性文法？什么是L屬性文法？它們之間有什么關(guān)系?解答:S-屬性文法是只含有綜合屬性的屬性文法。(2 分)L屬性文法要求對(duì)于每個(gè)產(chǎn)生式 A X1X2沢門，其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是Xj

20、的一個(gè)繼承屬性，且該屬性僅依賴于:(1)產(chǎn)生式Xj的左邊符號(hào)X1,X2 Xj-1的屬性;(2 分)(2) A的繼承屬性。S-屬性文法是L屬性文法的特例。(2 分)2 .什么是句柄？什么是素短語(yǔ)?一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。（3分）素短語(yǔ)是這樣的一個(gè)短語(yǔ),它至少包含一個(gè)終結(jié)符并且不包含更小的素短語(yǔ)。（3分）3 .劃分程序的基本塊時(shí)，確定基本塊的入口語(yǔ)句的條件是什么?解答:（1）程序第一個(gè)語(yǔ)句，或（2）能由條件轉(zhuǎn)移語(yǔ)句或無條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或（3）緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。4. （6分）運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么?答：DISPLAY表是嵌套層次顯示

21、表。每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表diaplay.假定現(xiàn)在進(jìn)入的過程層次為i，則它的diaplay表含有i+1個(gè)單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外 層、直至最外層（主程序，0層）等每層過程的最新活動(dòng)記錄的起始地址。通 過DISPLAY表可以訪問其外層過程的變量。5. （6分）對(duì)下列四元式序列生成目標(biāo)代碼:A:=B*CD:=E+FG:=A+DH:=G*2其中,H是基本塊出口的活躍變量，R0和R1是可用寄存器答:LDRO,MULRO,LDR1 ,ADDR1 ,ADDRO,R1MULRO,STRO,、設(shè)=0,1上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字

22、符串組成，請(qǐng)給出該字集對(duì)應(yīng)的正規(guī)式，并構(gòu)造一個(gè)識(shí)別該正規(guī)集的DFA。 （8 分）答:構(gòu)造相應(yīng)的正規(guī)式：（0|1）*1（0|1）（3分）NFA:（2 分）1確定化：（3分）I1。I10,1,21,21,2,31,21,21,2,31,2,31,2,41,2341,2,41,21,2,31,2,3,41,2,41,2,3,40O丄CXaGWHaO11三、寫一個(gè)文法使其語(yǔ)言為 L(G)= anbmambn | m,n>1。 (6分)答：文法G(S):SBaSb | BbBa | ba四、對(duì)于文法G(E): (8 分)1.T|E+TF|T*F(E)|i寫出句型（T*F+i）的最右推導(dǎo)并畫出語(yǔ)法樹

23、。2. 寫出上述句型的短語(yǔ)，直接短語(yǔ)、句柄和素短語(yǔ)。答:1. (4 分)E T F (E)(E+T)(E+F)(E+i)(T+i)(T*F+i)F2.(4 分)短語(yǔ)：(T*F+i),T*F+i, T*F, i直接短語(yǔ)：T*F, i句柄：T*F 素短語(yǔ)：T*F, i五、設(shè)文法G（S）: （12分）SiA | AA B |B)A*|(構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合;構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)。（12分）答:(6分)FIRSTVT(S)= i , + , ), ( FIRSTVT(A)= + , ), ( FIRSTVT(B)= ) , ( LASTVT(S)= i , + , *,

24、 ( LASTVT(A)= + , * , ( LASTVT(B)= * , ( 優(yōu)先關(guān)系表：（3分）i+()*i><<<+>><<>(>>>)<<<*>>>優(yōu)先函數(shù)：（3分）i+()*f26616g14661六、設(shè)某語(yǔ)言的do-while 語(yǔ)句的語(yǔ)法形式為（9分）S do S While E其語(yǔ)義解釋為:針對(duì)自下而上的語(yǔ)法分析器，按如下要求構(gòu)造該語(yǔ)句的翻譯模式:（1）寫出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式;（2）寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。答：（1）.適合語(yǔ)法制導(dǎo)翻譯的文法（3分）G(S):d

25、oR S(1) While(2). (6 分)R do R.QUAD:=NXQ R S While U.QUAD:=R.QUAD;BACK PATCH(S.CHAIN, NXQ) BACK PATCH(E.TC, U.QUAD);S.CHAIN:=E.FC 101 (j ,109)答案二:(1) SdoM 1 S While M 2(3分)£ M.QUAD := NXQ (6分)do M1 S WhileM2 EBACK PATCH(S.CHAIN, M2.QUAD);BACK PATCH(E.TC, M1.QUAD);S.CHAIN:=E. FC七、（8分）將語(yǔ)句if (A<

26、X)(B>0) then while C>0 do C:=C+D翻譯成四元式。(8分)答:100 (j< , A ,X,102)102 (j> :，B，0，104)103 (j，109)104 (j> :,C，0， 106)105 (j，109)106 (+，C，D，T1)107 (:=，T1，-，C)108 (j，104)109（控制結(jié)構(gòu)3分，其他5分）八、（10分）設(shè)有基本塊如下:T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6（1）畫出DAG圖;(2)設(shè)A,B是出基本塊后的活躍變

27、量，請(qǐng)給出優(yōu)化后的四元式序列。答:T3(1) DAG如右圖:四元式序列：(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*4九、(9分)設(shè)已構(gòu)造出文法 G(S):(1) S BB B aB的LR分析表如下假定輸入串為abab ,請(qǐng)給出LR分析過程（即按照步驟給出狀態(tài)，符號(hào)，輸入串狀態(tài)ACTIONGOTOab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2的變化過程）。答:步驟狀態(tài)符號(hào)輸入串a(chǎn)bab#03#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab #70269#BaB

28、 #8025#BB #901#S# acc編譯原理期末試題（八）（10 分）處于/*和*/之間的串構(gòu)成注解，注解中間沒有*/。畫出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。2 .為語(yǔ)言L = ambn | 0 m 2n（即a的個(gè)數(shù)不超過b的個(gè)數(shù)的兩倍）寫一個(gè)LR （1）文法，不準(zhǔn)超過6個(gè)產(chǎn)生式。（若超過6個(gè)產(chǎn)生式，不給分。若所寫文法不是LR （1）文法，最多給5分。）3. （10分）構(gòu)造下面文法的LL （1）分析表。TL int | real id R ,id R |4. （15分）就下面文法S ( L) | a L L S | S?給出一個(gè)語(yǔ)法制導(dǎo)定義，它輸出配對(duì)括號(hào)的個(gè)數(shù)。?給出一個(gè)翻譯方案，它輸

29、出每個(gè) a的嵌套深度。如句子（a, （a, a），第一小題的輸出是2，第二小題的輸出是1 2 2 。5. （10分）Pascal語(yǔ)言for語(yǔ)句的含義見教材第222頁(yè)習(xí)題7.13。請(qǐng)為該語(yǔ)句設(shè)計(jì)一種合理的中間代碼結(jié)構(gòu)。你可以按第215頁(yè)圖7.17的方式或者第219頁(yè)圖7.19的方式寫出你的設(shè)計(jì)，不需要寫產(chǎn)生中間代碼的語(yǔ)法制導(dǎo)定義。6. （5分）一個(gè)C語(yǔ)言程序如下:fun c(i1,i2,i3) long i1,i2,i3;long j1,j2,j3;prin tf("Addresses of i1,i2,i3 = %o,%o,%on",&i1,&i2,&

30、;i3);prin tf("Addresses of j1,j2,j3 = %o,%o,%on",&j1,&j2,&j3);mai n()long i1,i2,i3;fun c(i1,i2,i3);該程序在某種機(jī)器的Linux上的運(yùn)行結(jié)果如下:Addresses of i1,i2,i3 = 27777775460,27777775464,27777775470Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434從上面的結(jié)果可以看出，func函數(shù)的3個(gè)形式參數(shù)的地址依次升高，而 3個(gè)局部

31、變量的地址依次降低。試說明為什么會(huì)有這個(gè)區(qū)別。7. （ 15分）一個(gè)C語(yǔ)言程序及其在某種機(jī)器linux操作系統(tǒng)上的編譯結(jié)果如下。根據(jù)所生成的匯編程序來解釋程序中四個(gè)變量的作用域、生存期和置初值方式等方面的區(qū)別。static long aa = 10;short bb = 20;fun c()static long cc = 30;short dd = 40;.file "static.c".versio n "01.01" gcc2_co mp iled.: .data.alig n 4.typeaa,object.sizeaa,4aa:.long 10

32、 .globl bb.alig n 2.typebb,object.sizebb,2bb:.value 20.alig n 4.type cc.2,object.size cc.2,4cc.2:.long 30.text.alig n 4.globl func.type func,fun cti onfunc:p ushi %eb pmovi %es p,%eb psubl $4,%espmovw $40,-2(%eb p)丄1:leaveret丄fe1:.sizefun c,.Lfe1-f unc.ide nt "GCC: (GNU) egcs-2.91.6619990314/Li

33、 nux (egcs-1.1.2release)"8. （10分）C語(yǔ)言是一種類型語(yǔ)言，但它不是強(qiáng)類型語(yǔ)言，因?yàn)榫幾g時(shí)的類型檢查不能保證所接受的程序沒有運(yùn)行時(shí)的類型錯(cuò)誤。 例如，編譯時(shí)的類型檢查一般不能保證運(yùn)行時(shí)沒有數(shù)組越界。請(qǐng)你再舉一個(gè)這樣的例子說明C語(yǔ)言不是強(qiáng)類型語(yǔ)言。9.（ 10分）如果在A機(jī)器上我們有C語(yǔ)言編譯器CCa,也有它的源碼Sa （用C語(yǔ)言寫成）。如何利用它通過盡量少的工作來得到 B機(jī)器的C語(yǔ)言編譯器CCb 010 . (5 分)表達(dá)式(x.( yz.(x + y) + z) 3) 4 5 和(x.( yz.(x + y) + z) 3 5) 4 有同樣的結(jié)果。在抽象

34、機(jī)FAM上，哪一個(gè)表達(dá)式對(duì)應(yīng)的目標(biāo)代碼的執(zhí)行效率高?為什么?參考答案LR(1)文法LRAB | aABbaaAb |Bb |intD TLT int(1)文法ABaaAb | ab |Bb |realTLrealL id Rid二義文法AASb |,id Rprin t(S .num)(L)S.num := L.num +1S. num := 0L1,SL.num := L 1.num + S. numL.num := S.numS.de pth := 0 SL.de pth := S.de pth +1 (L)a prin t(S.de pth)L1.de pth := L.de pth L

35、1, S.de pth := L.de pth S S.de pth := L.de pth S5.t1 := in itialt2 := finalif 11 > t 2 goto L1v := t 1L2:stmtif v = t 2 goto L1 v := v + 1 goto L2L1: 6.由于實(shí)參表達(dá)式是反序進(jìn)入活動(dòng)記錄， 而局部變量是順序在活動(dòng)記錄中分配。7. aa是靜態(tài)外部變量，而bb是外部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)（由.data偽指令開始），但是bb由偽指令.globl指明為全局的，用來解決其它文件中對(duì)bb的外部引用，而aa只能由本文件引用。cc是靜態(tài)局部變量，同a

36、a和bb樣，它的生存期是整個(gè)程序并分配在靜態(tài)數(shù)據(jù)區(qū)。由于cc在源程序中的作用域是函數(shù)func的體，而在目標(biāo)文件中，它的作用域至少已是整個(gè)文件了，為避免同源文件中外部變量和其它函數(shù)的靜態(tài)局部變量的名字沖突，所以要對(duì)它進(jìn)行改 名，成了 cc.2。由于cc不是全局的，因此cc.2前面沒有偽指令.globl。dd是自動(dòng)變量，其作用域是函數(shù)func的體，其生存期是該函數(shù)激活期間，因此它分 配在棧區(qū)，并且置初值是用運(yùn)行時(shí)的賦值來實(shí)現(xiàn)。8. 例如聯(lián)合體的類型檢查一般也不可能在編譯時(shí)完成，雖然下面例子是可靜態(tài)判斷類型錯(cuò)誤的。un io n U int u1; int *u2; u;int p;u.u1 = 1

37、0;p = u.u2;P = 0;9. ?修改源碼Sa的代碼生成部分，讓它產(chǎn)生B機(jī)器的代碼，稱結(jié)果程序?yàn)镾b。CCbo?將Sb提交給CCa進(jìn)行編譯，得到一個(gè)可執(zhí)行程序。?將Sb提交給上述可執(zhí)行程序進(jìn)行編譯，得到所需的編譯器10 .第一個(gè)表達(dá)式在執(zhí)行yz.(x + y) + Z) 3時(shí)出現(xiàn)參數(shù)個(gè)數(shù)不足的情況，因此有FUNVAL的值進(jìn)入棧頂，然后發(fā)現(xiàn)參數(shù)個(gè)數(shù)不足，又把它做成FANVAL的情況。而第二個(gè)表達(dá)式執(zhí)行的是(yz.(x + y) + Z)3 5，不會(huì)出現(xiàn)參數(shù)個(gè)數(shù)不足的情況。因此第二個(gè)表達(dá)式的執(zhí)行效率比第一個(gè)表達(dá)式的高。編譯原理期末大題1.設(shè)有如下文法 G (S)，試消除其左遞歸。G ( S

38、): S >Ac|cA >Bb|bB >Sa|a解：StabcS bcS cS ： S，方bcS 2.試構(gòu)造與下面G (S)等價(jià)的無左遞歸的文法。G ( S): S >Sa|Nb|cN >Sd|Ne|f解：StfN bS '|cS : S，tS |dN bS , N ' tN '|3.設(shè)有文法G ( S):S >aBc|bABA >aAb|bB >b| £ 求各產(chǎn)生式的first集，F(xiàn)OLLOW(A)和FOLLOW(B),以及各產(chǎn)生式的select集。 構(gòu)造LL(1)分析表，并分析符號(hào)串baabbb是否是。解：(1) FIRST(aBc)=a, FIRST(bAB)=b FIRST(aAb)=a, A tb: FIRST(Atb)=b, B tb: FIRST(b) = b, FIRST( £= £FOLLOW(A)=b, #, FOOLOW(B)=c, #SELECT(St aBc)=a, SELECT(St bAB) =b, SELECT(At aAb)=a,SELECT(Atb)=b, SELECT(B tb)=b, SELECT(B t )=c, #因此，所得的LL(1)分析表如表A-4所示。表A-4LL(1)分析表輸入符號(hào)入abc#N sSt aBcSt b