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

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

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

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

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

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

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

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

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

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

10、不只一棵語法分析樹與之對應(yīng)，那么稱這個 文法是二義性文法。句子aadbd有兩棵語法樹。如下圖:(1)d由此可知，S aSbS|aS|d定義的文法是二義性文法。柄？2 .對于文法句型baSb解：baSb為句型baSb的相對于S的短語，ba 為句型 baSb 的相對于 A 的短語，Sb 為句型baSb的相對于B的短語，且為直接短語，a為句型baSb的相對于B的短語，且為直接 短語和句柄。3 .設(shè)有非確定的有自限動機(jī)NFA M=(A , B, C, 0, 1, , A , C)，其中:(A , 0)=C (A , 1)=A , B (B , 1)=C (C, 1)=C。請畫出狀態(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的不同語法分析樹的總數(shù)為B3C5D7四元式之間的聯(lián)系是通過實現(xiàn)。A臨時變量 B指示器 C符號表D程序變量】5.同心集合并可能會產(chǎn)生的新沖突為A二義 B移進(jìn)/移進(jìn)C移進(jìn)/歸約D歸約/歸約【】6.代碼優(yōu)化時所依據(jù)的是A語法規(guī)則B詞法規(guī)則C等價變換規(guī)則D語義規(guī)則【】7 .表達(dá)式a-(-b)*c的逆波蘭表示為Aa-bc*Babc*-Cab-Dab

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

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

14、1n0m1m0n | m,n >0 【】【】五文法G: S f 1S0 | AA f 0A1 |£六對文法GSS f aSb|PP f bPc | bQc(1) 它是否是算符優(yōu)先文法？請構(gòu)造算符優(yōu)先關(guān)系表(2) 文法GS消除左遞歸、提取左公因子后是否是LL( 1)文法？請證實?！尽俊尽?.求出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)系中同時出現(xiàn)了a<a和a>a以及b<b和b>b，所以該文法不是算符優(yōu)先文法。2.消除左遞歸和提取左公因子后的文法為:7 aSb|P7 Pc |Qc7 aQ 'Q' 7 aQ ' | £求具有相同左部的兩個產(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)項目集、可歸前綴圖和 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;試按語法制導(dǎo)翻譯法將源程序翻譯成四

17、元式序列（設(shè)A是數(shù)組a的起始地址，B是數(shù)組b的起始地址；機(jī)器按字節(jié)編址，每個數(shù)組元素占四個字節(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 ；十對以下文法，請寫出關(guān)于括號嵌套層數(shù)的屬性文法。（為S,L引入屬性h,用來記錄輸出配對的括號個數(shù)）文法規(guī)則語義規(guī)則s-(T)Sf iT-T,ST-S文袪規(guī)則語義規(guī)則S-* (T)(S-h:=T.h+l;)SiT一咗 fS<T.h:=T.h+S.h;Tf ST,h:= S.h; 答案:1一 對PL/0語言的while語句 while 條件B DO 語句S 的編譯程序,請在空缺處填空，完成該語句的編譯算法: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屬性文法要求對于每個產(chǎn)生式 A X1X2沢門，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj

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

21、表。每當(dāng)進(jìn)入一個過程后，在建立它的活動記錄區(qū)的同時建立一張嵌套層次顯示表diaplay.假定現(xiàn)在進(jìn)入的過程層次為i，則它的diaplay表含有i+1個單元，自頂向下每個單元依次存放著現(xiàn)行層、直接外 層、直至最外層（主程序，0層）等每層過程的最新活動記錄的起始地址。通 過DISPLAY表可以訪問其外層過程的變量。5. （6分）對下列四元式序列生成目標(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ù)第二個字符為1的所有字

22、符串組成，請給出該字集對應(yīng)的正規(guī)式，并構(gòu)造一個識別該正規(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三、寫一個文法使其語言為 L(G)= anbmambn | m,n>1。 (6分)答：文法G(S):SBaSb | BbBa | ba四、對于文法G(E): (8 分)1.T|E+TF|T*F(E)|i寫出句型（T*F+i）的最右推導(dǎo)并畫出語法樹

23、。2. 寫出上述句型的短語，直接短語、句柄和素短語。答:1. (4 分)E T F (E)(E+T)(E+F)(E+i)(T+i)(T*F+i)F2.(4 分)短語：(T*F+i),T*F+i, T*F, i直接短語：T*F, i句柄：T*F 素短語：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è)某語言的do-while 語句的語法形式為（9分）S do S While E其語義解釋為:針對自下而上的語法分析器，按如下要求構(gòu)造該語句的翻譯模式:（1）寫出適合語法制導(dǎo)翻譯的產(chǎn)生式;（2）寫出每個產(chǎn)生式對應(yīng)的語義動作。答：（1）.適合語法制導(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分）將語句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、量，請給出優(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 ,請給出LR分析過程（即按照步驟給出狀態(tài)，符號，輸入串狀態(tài)ACTIONGOTOab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2的變化過程）。答:步驟狀態(tài)符號輸入串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 .為語言L = ambn | 0 m 2n（即a的個數(shù)不超過b的個數(shù)的兩倍）寫一個LR （1）文法，不準(zhǔn)超過6個產(chǎn)生式。（若超過6個產(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?給出一個語法制導(dǎo)定義，它輸出配對括號的個數(shù)。?給出一個翻譯方案，它輸

29、出每個 a的嵌套深度。如句子（a, （a, a），第一小題的輸出是2，第二小題的輸出是1 2 2 。5. （10分）Pascal語言for語句的含義見教材第222頁習(xí)題7.13。請為該語句設(shè)計一種合理的中間代碼結(jié)構(gòu)。你可以按第215頁圖7.17的方式或者第219頁圖7.19的方式寫出你的設(shè)計，不需要寫產(chǎn)生中間代碼的語法制導(dǎo)定義。6. （5分）一個C語言程序如下: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個形式參數(shù)的地址依次升高，而 3個局部

31、變量的地址依次降低。試說明為什么會有這個區(qū)別。7. （ 15分）一個C語言程序及其在某種機(jī)器linux操作系統(tǒng)上的編譯結(jié)果如下。根據(jù)所生成的匯編程序來解釋程序中四個變量的作用域、生存期和置初值方式等方面的區(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語言是一種類型語言，但它不是強(qiáng)類型語言，因為編譯時的類型檢查不能保證所接受的程序沒有運(yùn)行時的類型錯誤。 例如，編譯時的類型檢查一般不能保證運(yùn)行時沒有數(shù)組越界。請你再舉一個這樣的例子說明C語言不是強(qiáng)類型語言。9.（ 10分）如果在A機(jī)器上我們有C語言編譯器CCa,也有它的源碼Sa （用C語言寫成）。如何利用它通過盡量少的工作來得到 B機(jī)器的C語言編譯器CCb 010 . (5 分)表達(dá)式(x.( yz.(x + y) + z) 3) 4 5 和(x.( yz.(x + y) + z) 3 5) 4 有同樣的結(jié)果。在抽象

34、機(jī)FAM上，哪一個表達(dá)式對應(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.由于實參表達(dá)式是反序進(jìn)入活動記錄， 而局部變量是順序在活動記錄中分配。7. aa是靜態(tài)外部變量，而bb是外部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)（由.data偽指令開始），但是bb由偽指令.globl指明為全局的，用來解決其它文件中對bb的外部引用，而aa只能由本文件引用。cc是靜態(tài)局部變量，同a

36、a和bb樣，它的生存期是整個程序并分配在靜態(tài)數(shù)據(jù)區(qū)。由于cc在源程序中的作用域是函數(shù)func的體，而在目標(biāo)文件中，它的作用域至少已是整個文件了，為避免同源文件中外部變量和其它函數(shù)的靜態(tài)局部變量的名字沖突，所以要對它進(jìn)行改 名，成了 cc.2。由于cc不是全局的，因此cc.2前面沒有偽指令.globl。dd是自動變量，其作用域是函數(shù)func的體，其生存期是該函數(shù)激活期間，因此它分 配在棧區(qū)，并且置初值是用運(yùn)行時的賦值來實現(xiàn)。8. 例如聯(lián)合體的類型檢查一般也不可能在編譯時完成，雖然下面例子是可靜態(tài)判斷類型錯誤的。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é)果程序為Sb。CCbo?將Sb提交給CCa進(jìn)行編譯，得到一個可執(zhí)行程序。?將Sb提交給上述可執(zhí)行程序進(jìn)行編譯，得到所需的編譯器10 .第一個表達(dá)式在執(zhí)行yz.(x + y) + Z) 3時出現(xiàn)參數(shù)個數(shù)不足的情況，因此有FUNVAL的值進(jìn)入棧頂，然后發(fā)現(xiàn)參數(shù)個數(shù)不足，又把它做成FANVAL的情況。而第二個表達(dá)式執(zhí)行的是(yz.(x + y) + Z)3 5，不會出現(xiàn)參數(shù)個數(shù)不足的情況。因此第二個表達(dá)式的執(zhí)行效率比第一個表達(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)等價的無左遞歸的文法。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)分析表，并分析符號串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)分析表輸入符號入abc#N sSt aBcSt b