編譯原理期末試題(8套含答案+大題集)

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

2、 Chomsky 四種文法的四種語言之間的關(guān)系是AL0L1L2L3BL3L2L1L0CL 3=L 2L1L0DL0L 1L2=L37詞法分析的任務(wù)是A 識(shí)別單詞B 分析句子的含義C識(shí)別句子D 生成目標(biāo)代碼8常用的中間代碼形式不含A 三元式B 四元式C逆波蘭式D語法樹9代碼優(yōu)化的目的是A 節(jié)省時(shí)間B 節(jié)省空間C節(jié)省時(shí)間和空間D 把編譯程序進(jìn)展等價(jià)交換10代碼生成階段的主要任務(wù)是A 把高級(jí)語言翻譯成匯編語言B 把高級(jí)語言翻譯成機(jī)器語言C把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼D 把匯編語言翻譯成機(jī)器語言二、填空題本大題共5 小題，每題 2 分，共 10 分1編譯程序首先要識(shí)別出源程序中每個(gè)( 單詞

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

4、務(wù)是從左向右掃描每行源程序的符號(hào)，按照詞法規(guī)那么從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。2 LL(1) 文法假設(shè)文法的任何兩個(gè)產(chǎn)生式A|都滿足下面兩個(gè)條件：1 FIRST()FIRST() =；2假設(shè)*，那么 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語法樹句子的樹構(gòu)

5、造表示法稱為語法樹 (語法分析樹或語法推導(dǎo)樹 )。給定文法 G=(V N， VT，P， S)，對(duì)于 G 的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有以下特征：(1) 根節(jié)點(diǎn)的標(biāo)記是開場(chǎng)符號(hào)S。(2) 每個(gè)節(jié)點(diǎn)的標(biāo)記都是 V 中的一個(gè)符號(hào)。(3) 假設(shè)一棵子樹的根節(jié)點(diǎn)為 A ，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)?A 1A 2AR，那么 A A 1A 2AR一定是 P 中的一條產(chǎn)生式。(4)假設(shè)一標(biāo)記為 A 的節(jié)點(diǎn)至少有一個(gè)除它以外的子孫，那么A VN。(5)假設(shè)樹的所有葉節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，那么 w 是文法 G的句型；假設(shè)w 中僅含終結(jié)符號(hào)，那么w 為文法 G 所產(chǎn)生的

6、句子。4 LR(0) 分析器所謂 LR(0) 分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(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語言和文法文法就是語言構(gòu)造的定義和描述，是有窮非空的產(chǎn)生式集合。文法 G 定義為四元組的形式：G=(V N， VT，P， S)其中： VN是非空有窮集合，稱為非終結(jié)符號(hào)集合；V T是非空有窮集合，稱為終結(jié)符號(hào)集合； P 是產(chǎn)生式的集合 (非空 )； S 是開場(chǎng)符號(hào)

7、(或識(shí)別符號(hào) )。這里， VV。 V=V V，稱為文法 G 的字母表，它是出現(xiàn)NT=，S VNNT文法產(chǎn)生式中的一切符號(hào)的集合。文法 G 所描述的語言用L(G) 表示，它由文法G 所產(chǎn)生的全部句子組成，即專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.L(G)=x| S*x ，其中 S 為文法開場(chǎng)符號(hào)，且xVT簡單的說，文法描述的語言是該文法一切句子的集合。四、簡答題 (共 4 小題，每題 5 分，共 20 分)1編譯程序和高級(jí)語言有什么區(qū)別?用匯編語言或高級(jí)語言編寫的程序，必須先送入計(jì)算機(jī)，經(jīng)過轉(zhuǎn)換成用機(jī)器語言表示的目標(biāo)程序這個(gè)過程即編譯，才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序

8、。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標(biāo)程序，也就是機(jī)器語言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對(duì)應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語言表示的程序。解釋型編譯程序?qū)⒏呒?jí)語言程序的一個(gè)語句，先解釋成為一組機(jī)器語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個(gè)程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進(jìn)展人和計(jì)算機(jī)的"對(duì)話 "，隨時(shí)可以修改高級(jí)語言的程序。 BASIC 語言就是解釋型高級(jí)語言。編譯型編譯程序?qū)⒓?jí)語言編寫的程序，一次就會(huì)部翻譯成機(jī)器語言表示的程序，而且過程進(jìn)

9、展很快，在過程中，不能進(jìn)展人機(jī)對(duì)話修改。FORTRAN 語言就是編譯型高級(jí)語言。2編譯程序的工作分為那幾個(gè)階段?詞法分析、語法分析和語義分析是對(duì)源程序進(jìn)展的分析(稱為編譯程序的前端) ，而中間代碼生成、代碼優(yōu)化和代碼生成三個(gè)階段合稱為對(duì)源程序進(jìn)展綜合(稱為編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序。3簡述自下而上的分析方法。所謂自下而上分析法就是從輸入串開場(chǎng)，逐步進(jìn)展“歸約 ，直至歸約到文法的開場(chǎng)符號(hào)；或者說從語法樹的末端開場(chǎng)，步步向上“歸約 ，直到根節(jié)點(diǎn)。4簡述代碼優(yōu)化的目的和意義。代碼優(yōu)化是盡量生成 “好 的代碼的編譯階段。也就是要對(duì)程序代碼進(jìn)展一種等價(jià)變換，在保

10、證變換前后代碼執(zhí)行結(jié)果一樣的前提下，盡量使目標(biāo)程序運(yùn)行時(shí)所需要的時(shí)間短，同時(shí)所占用的存儲(chǔ)空間少。五、綜合應(yīng)用題 (共 3 小題，每題 10 分，共 30 分 )1證明下述文法G：SaSbS|aS|d是二義性文法。解：一個(gè)文法，如果存在某個(gè)句子有不只一棵語法分析樹與之對(duì)應(yīng)，那么稱這個(gè)文法是二義性文法。句子 aadbd 有兩棵語法樹。如以下圖：SS專業(yè)資料整理WORD格式aSbSaS專業(yè)資料整理WORD格式aSdaSbS參考專業(yè)資料整理WORD格式ddd專業(yè)資料整理WORD格式.(1)(2)由此可知， SaSbS|aS|d定義的文法是二義性文法。2對(duì)于文法 GS ：S AB ，A Aa|bB ，B

11、a|Sb 求句型 baSb 的全部短語、 直接短語和句柄？句型 baSb 的語法樹如圖五 (2)所示。SABbBSba解： baSb 為句型 baSb 的相對(duì)于S 的短語， ba 為句型 baSb 的相對(duì)于A 的短語， Sb 為句型baSb 的相對(duì)于 B 的短語，且為直接短語， a 為句型 baSb 的相對(duì)于 B 的短語，且為直接短語和句柄。3設(shè)有非確定的有自限動(dòng)機(jī)NFAM=(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)換圖。解：狀態(tài)轉(zhuǎn)換距陣為：01ACA， BBCCC狀態(tài)轉(zhuǎn)

12、換圖為1111ABC10?編譯原理?期末試題六編譯原理樣題【】 1 _型文法也稱為正規(guī)文法。專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.A 0B 1C 2D 3【】 2 _文法不是 LL(1) 的。A遞歸B 右遞歸C 2 型D含有公共左因子的【】 3文法 EE+E|E*E|i 的句子 i*i+i*i的不同語法分析樹的總數(shù)為_。A1B3C5D7【】 4四元式之間的聯(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 語法規(guī)那么B 詞法規(guī)那么C 等價(jià)變換

13、規(guī)那么D 語義規(guī)那么【】 7表達(dá)式 a-(-b)*c 的逆波蘭表示為。Aa-bc*Babc*-Cab-Dabc-*注： 為單目減運(yùn)專業(yè)資料整理WORD格式算符【】 8過程的 DISPLAYA 過程的連接數(shù)據(jù)C 過程的返回地址表記錄了。B 過程的嵌套層次D 過程的入口地址專業(yè)資料整理WORD格式二填空題3對(duì)于文法G1 和 G2，假設(shè)有L(G1)=L(G2)或G1 和 G2 的語言一樣，那么稱文法G1和 G2 是等價(jià)的。4對(duì)于文法 GE ：E T|E+TT F|T*FFPF|PP (E)|i ，句型 T+T*F+i 的句柄是 T，最左素短語是T*F 。5最右推導(dǎo)的逆過程稱為標(biāo)準(zhǔn)歸約，也稱為最左歸約

14、 。6標(biāo)準(zhǔn)規(guī)約中的可規(guī)約串是句柄，算符優(yōu)先分析中的可規(guī)約串是最左素短語7 A BC ?D E 的逆波蘭式是?。8在屬性文法中文法符號(hào)的兩種屬性分別稱為繼承屬性和綜合屬性次序可換 。9符號(hào)表的每一項(xiàng)為哪一項(xiàng)由名字欄和地址分配兩個(gè)欄目組成。在目標(biāo)代碼生成階段，符號(hào)表是地址分配的依據(jù)。10一個(gè)過程的DISPLAY 表的內(nèi)容是它的直接外層的 DISPLAY 表的內(nèi)容加上本過程的 SP 的地址三有窮自動(dòng)機(jī) M 承受字母表 0,1 上所有滿足下述條件的串：每個(gè) 1 都有 0 直接跟在右邊。構(gòu)造一個(gè)最小的 DFA M 及和 M 等價(jià)的正規(guī)式?！尽俊尽繉I(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.四證

15、明正規(guī)式 (ab)*a 與正規(guī)式 a(ba)*等價(jià) 用構(gòu)造他們的最小的DFA 方法?！敬鸢福骸课?寫一個(gè)文法，使其語言是：L 1 n0m1m0n | m,n 0 【】【】五文法 G：S 1S0 | AA 0A1 |六對(duì)文法 GS專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.S aSb | PP bPc | bQcQ Qa | a(1) 它是否是算符優(yōu)先文法？請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表(2) 文法 GS 消除左遞歸、提取左公因子后是否是 LL1文法？請(qǐng)證實(shí)。專業(yè)資料整理WORD格式【】【】 1.求出GS的FIRSTVT集和FIERSTVT S=a,bFIERSTVT(P)=bFIERSTVT(

16、Q)=aLASTVT集：LASTBVT S=b,cLASTBVT P=cLASTBVT Q =a專業(yè)資料整理WORD格式構(gòu)造優(yōu)先關(guān)系表為：專業(yè)資料整理WORD格式abca<>b<< >>c>>專業(yè)資料整理WORD格式由于在優(yōu)先關(guān)系中同時(shí)出現(xiàn)了a<a和 a>a 以及b<b和b>b，所以該文法不是算符優(yōu)先文法。專業(yè)資料整理WORD格式2. 消除左遞歸和提取左公因子后的文法為：S aSb | P專業(yè)資料整理WORD格式P bP 專業(yè)資料整理WORD格式PPc |QcQ aQ專業(yè)資料整理WORD格式QaQ |專業(yè)資料整理WORD格

17、式求具有一樣左部的兩個(gè)產(chǎn)生式的Select 集的交集：Select(S aSb) Select(S =aP) First(P)= a b =Select(P Pc) Select(P=First(PQc) First(Q)=bSelect(Q aQ ) Select(Q= a)Follow(Q) = a 所以修改后的文法是LL 1文法。 c =a=專業(yè)資料整理WORD格式七文法 G 為:（ 0 SS（ 1 S aAd（ 2 S bAc（ 3 S aec（ 4 S bed（ 5 A e試構(gòu)造它的 LR 1工程集、可歸前綴圖和LR1分析表。【】【答案：】SI 1：S S ·,I0:#S

18、·S ,da#AI 4：S aA· d ,I 8： S aAd ·,S·aAd ,I 2：#S a ·Ad , #ec ·：S ae·c ,SS a ec , #I 5I 9：S aec ·,A ·e , d# ·bAc ,#Ae ·,d參考#bI 10：S ·aec ,AI 3: S b ·Ac ,c S bAc ·,#I6: S bA·c,#專業(yè)資料整理WORD格式.構(gòu)造 LR(1) 分析表 如下：actiongoto狀態(tài)abcde#SA0S

19、2S311ac2cS53S74S85S9r56S107r5S118r19r310r211r4八 源程序如下：prod:=0;i:=1;while i 20 dobeginprod:=prod+ai*bi;i:=i+1end;試按語法制導(dǎo)翻譯法將源程序翻譯成四元式序列設(shè)A 是數(shù)組 a 的起始地址， B 是數(shù)組 b 的起始地址；機(jī)器按字節(jié)編址，每個(gè)數(shù)組元素占四個(gè)字節(jié)?！敬鸢福骸繉I(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.九 設(shè)有以下程序段procedure P(x,y,z)beginY:=y*3;Z:=X+z;end;begina:=5; b:=2;p(a*b,a,a);print(a)

20、;end假設(shè)參數(shù)傳遞的方法分別為 1傳值、2傳地址、 3傳名，試問結(jié)果分別什么？【】【】十 1傳值 5； 2傳地址 25； 3傳名 45十對(duì)以下文法，請(qǐng)寫出關(guān)于括號(hào)嵌套層數(shù)的屬性文法。(為 S,L 引入屬性h,用來記錄輸出配對(duì)的括號(hào)個(gè)數(shù))文法規(guī)那么語義規(guī)那么S (T)S iTT,ST S專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.答案：十一對(duì) PL/0 語言的 while 語句 while條件 BDO語句 S的編譯程序，請(qǐng)?jiān)诳杖碧幪羁眨瓿稍撜Z句的編譯算法：switch (SYM) case WHILESYM:CX1=CX;GetSym();CONDITION(SymSetAdd(D

21、OSYM,FSYS),LEV,TX);CX2=CX;GEN(JPC,0,0);if (SYM=DOSYM)GetSym();else Error(18);STATEMENT(FSYS,LEV,TX);GEN(JMP,0,CX1);CODECX2.A=CX；break;?編譯原理?期末試題七一、答復(fù)以下問題： (30 分)1什么是 S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？解答：S-屬性文法是只含有綜合屬性的屬性文法。2 分L- 屬性文法要求對(duì)于每個(gè)產(chǎn)生式 A X1X2 Xn，其每個(gè)語義規(guī)那么中的每個(gè)屬性或者是綜合屬性，或者是 Xj 的一個(gè)繼承屬性，且該屬性僅依賴于：1 產(chǎn)生式 Xj

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

23、。每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一X嵌套層次顯示表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 是可用存放器答：LDR0， BMULR0， CLDR1， EADDR1， FADDR0， R1MULR0， 2STR0， H二、設(shè)

24、=0 ，1 上的正規(guī)集 S 由倒數(shù)第二個(gè)字符為 1 的所有字符串組成，請(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 分)1101214300確定化： (3 分 )專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.II 0I 10,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4010100012340111三、寫一個(gè)文法使其語言為L(G)= anbmambn | m,n 1 。(6 分)答：文法 G

25、(S):S aSb | BB bBa | ba四、對(duì)于文法G(E): (8 分 )專業(yè)資料整理WORD格式E T|E+TT F|T*FF (E)|i1. 寫出句型 (T*F+i) 的最右推導(dǎo)并畫出語法樹。2. 寫出上述句型的短語，直接短語、句柄和素短語。答：1. (4 分)ETF(E)(E+T)(E+F)ETF專業(yè)資料整理WORD格式(E+i)(T+i)(T*F+i)2. (4 分)短語： (T*F+i),T*F+i,T*F,i直接短語： T*F, i句柄： T*F素短語： T*F, i(E)E+TTF專業(yè)資料整理WORD格式五、設(shè)文法G(S) ： (12 分)T *Fi專業(yè)資料整理WORD格

26、式參考專業(yè)資料整理WORD格式.SSiA | AA A B|BB )A* |(1構(gòu)造各非終結(jié)符的FIRSTVT 和 LASTVT 集合；2構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)。(12 分 )答： (6 分)FIRSTVT(S)= i ， +， )，( FIRSTVT(A)= + ，)，( FIRSTVT(B)= ) ，( LASTVT(S)= i，+，* ，( LASTVT(A)= +，*，( LASTVT(B)= *， ( 優(yōu)先關(guān)系表 : (3 分)i+()*i><<<+>><<>(>>>)<<<*>>

27、>優(yōu)先函數(shù) : (3 分)i+()*f26616g14661六、設(shè)某語言的do-while 語句的語法形式為(9 分)S do S(1) While E其語義解釋為：專業(yè)資料整理WORD格式S(1)的代碼真專業(yè)資料整理WORD格式E的代碼假專業(yè)資料整理WORD格式針對(duì)自下而上的語法分析器，按如下要求構(gòu)造該語句的翻譯模式：(1) 寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；(2) 寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作。答： (1). 適合語法制導(dǎo)翻譯的文法 (3 分 )G(S):RdoURS(1)WhileSUE專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.(2). (6 分)R do R.QUAD:=

28、NXQURS(1)While U.QUAD:=R.QUAD; BACKPATCH(S.CHAIN, NXQ) S U E BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC 答案二：(1) SdoM 1(1)While M 2ESM(3 分)(2) M M.QUAD := NXQ (6 分)SdoM 1S(1)WhileM 2 E(1)BACKPATCH(S.CHAIN, M 2.QUAD);BACKPATCH(E.TC, M 1.QUAD);七、 (8 分)將語句if(A<X)(B>0) then while C>0 do C:=C+D翻譯成四元式

29、。 (8 分)答：100(j<， A ， X ， 102)101(j， -， -， 109)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(控制構(gòu)造 3 分，其他 5 分)八、 (10 分 ) 設(shè)有根本塊如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.T6:=T5*T3

30、B:=T6(1)畫出 DAG 圖；(2)設(shè) A,B 是出根本塊后的活潑變量， 請(qǐng)給出優(yōu)化后的四元式序列。答： (1)DAG 如右圖： (6 分)n7An8 T6,B_*n3 T1,T5, Bn6 T4+/n1n2n4T2n5T3SR34(2) 四元式序列： (4 分 ) T1:=S+RT4:=S/R A:=T1-T4 B:=T1*4九、 (9 分 ) 設(shè)已構(gòu)造出文法G(S)：(1) S BB(2) B aB(3) B b的 LR 分析表如下ACTIONGOTO狀態(tài)ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定輸入串為 abab，請(qǐng)

31、給出 LR 分析過程 ( 即按照步驟給出狀態(tài)，符號(hào)，輸入串的變化過程 )。專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.答：步驟狀態(tài)符號(hào)輸入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S# acc?編譯原理?期末試題八110 分處于 /* 和 */ 之間的串構(gòu)成注解，注解中間沒有 */ 。畫出承受這種注解的 DFA 的狀態(tài)轉(zhuǎn)換圖。2為語言 L a mbn | 0m2n 即 a 的個(gè)數(shù)不超過 b 的個(gè)數(shù)的兩倍寫一個(gè) LR 1文法，不準(zhǔn)超過6 個(gè)產(chǎn)生式。假設(shè)超過

32、 6 個(gè)產(chǎn)生式，不給分。假設(shè)所寫文法不是 LR 1文法，最多給5 分。310 分構(gòu)造下面文法的LL 1分析表。DTLTint | realL id RR , id R |415 分就下面文法S( L) | aLLS | S給出一個(gè)語法制導(dǎo)定義，它輸出配對(duì)括號(hào)的個(gè)數(shù)。給出一個(gè)翻譯方案，它輸出每個(gè)a 的嵌套深度。如句子 (a, (a, a) )，第一小題的輸出是2，第二小題的輸出是1 2 2。510 分 Pascal語言 for 語句的含義見教材第222 頁習(xí)題 7.13。請(qǐng)為該語句設(shè)計(jì)一種合理的中間代碼構(gòu)造。你可以按第 215 頁圖 7.17 的方式或者第 219 頁圖 7.19 的方式寫出你的

33、設(shè)計(jì)，不需要寫產(chǎn)生中間代碼的語法制導(dǎo)定義。6 5 分一個(gè) C 語言程序如下：func(i1,i2,i3)long i1,i2,i3;long j1,j2,j3;printf("Addresses of i1,i2,i3 = %o,%o,%on",&i1,&i2,&i3); printf("Addresses of j1,j2,j3 = %o,%o,%on",&j1,&j2,&j3);專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.main()long i1,i2,i3;func(i1,i2,i3);該

34、程序在某種機(jī)器的Linux 上的運(yùn)行結(jié)果如下：Addresses of i1,i2,i3 = 27777775460,27777775464,27777775470 Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434從上面的結(jié)果可以看出， func 函數(shù)的 3 個(gè)形式參數(shù)的地址依次升高，而 3 個(gè)局部變量的地址依次降低。試說明為什么會(huì)有這個(gè)區(qū)別。715 分一個(gè) C 語言程序及其在某種機(jī)器 linux 操作系統(tǒng)上的編譯結(jié)果如下。根據(jù)所生成的匯編程序來解釋程序中四個(gè)變量的作用域、生存期和置初值方式等方面的區(qū)別。static lon

35、g aa = 10;short bb = 20;func()static long cc = 30;short dd = 40;.file "static.c".version "01.01"gcc2_compiled.:.data.align 4.typeaa,object.sizeaa,4aa:.long 10.globl bb.align 2.typebb,object.sizebb,2bb:.value 20.align 4.typecc.2,object.sizecc.2,4專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.cc.2:.lo

36、ng 30.text.align 4.globl func.typefunc,functionfunc:pushl %ebpmovl %esp,%ebpsubl $4,%espmovw $40,-2(%ebp).L1:leaveret.Lfe1:.sizefunc,.Lfe1-func.ident "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)" 8 10 分 C 語言是一種類型語言，但它不是強(qiáng)類型語言，因?yàn)榫幾g時(shí)的類型檢查不能保證所承受的程序沒有運(yùn)行時(shí)的類型錯(cuò)誤。例如，編譯時(shí)的類型檢查一般不能保證運(yùn)

37、行時(shí)沒有數(shù)組越界。請(qǐng)你再舉一個(gè)這樣的例子說明 C 語言不是強(qiáng)類型語言。分如果在A機(jī)器上我們有C語言編譯器CCA，也有它的源碼SA用C9 10語言寫成。如何利用它通過盡量少的工作來得到B 機(jī)器的 C 語言編譯器 CCB。105 分表達(dá)式 ( x.( yz.(x + y) + z) 3)4 5 和( x.(yz.(x + y) + z) 3 5) 4 有同樣的結(jié)果。在抽象機(jī) FAM 上，哪一個(gè)表達(dá)式對(duì)應(yīng)的目標(biāo)代碼的執(zhí)行效率高？為什么？參考答案1others*start/2*2*4/51others2LR1文法LR 1文法二義文法SAB | aABbSABSAASb |AaaAb |A aaAb |

38、 ab |A a |BBb |BBb |3intrealid,$DDTLDTLTTintTrealLLid RRR, id RR4 SSprint(S.num)S(L)S.num := L.num +1專業(yè)資料整理WORD格式參考專業(yè)資料整理WORD格式.SaS.num := 0LL 1,SL.num := L 1.num + S.numLSL.num := S.numSS.depth := 0 SS L.depth := S.depth +1 (L) S a print(S.depth)L L 1.depth := L.depth L 1, S.depth := L.depth S L S.

39、depth := L.depth S5t1 := initialt2 := finalif t 1 > t2 goto L1v := t1L2: stmtif v = t 2 goto L1v := v + 1 goto L2L1:6由于實(shí)參表達(dá)式是反序進(jìn)入活動(dòng)記錄，而局部變量是順序在活動(dòng)記錄中分配。7aa 是靜態(tài)外部變量，而 bb 是外部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)由 .data 偽指令開場(chǎng)，但是 bb 由偽指令 .globl 指明為全局的，用來解決其它文件中對(duì) bb 的外部引用，而 aa只能由本文件引用。 cc 是靜態(tài)局部變量，同 aa 和 bb 一樣，它的生存期是整個(gè)程序并分配在靜

40、態(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ò)誤的。union U int u1; int *u2; u;intp;u.u1 = 10;p = u.u2;p = 0;9修改源碼 SA 的代碼生成局部， 讓它產(chǎn)生 B 機(jī)器的代碼，稱結(jié)果程序?yàn)?SB。將 SB提交給 CCA進(jìn)展編譯，得到一個(gè)可執(zhí)行程序。將 SB提交給上述可執(zhí)行程序進(jìn)展編譯，得到所需的編譯器CCB。10第一個(gè)表達(dá)式在執(zhí)行 yz.(x + y) + z) 3 時(shí)出現(xiàn)參數(shù)個(gè)數(shù)缺乏的情況，因此有 FUNVAL 的值進(jìn)入棧頂， 然后發(fā)現(xiàn)參數(shù)個(gè)數(shù)缺乏， 又把