編譯原理樣題3

1、*編譯原理樣題選擇題【】1. 型文法也稱(chēng)為正規(guī)文法。a 0b 1c2d 3【】2. 文法不是ll的。a 遞歸 b 右遞歸 c 2 型d含有公共左因子的【 】3.文法e-e+e|e*e|i的句子i*i+i*i的不同語(yǔ)法分析樹(shù)的總數(shù)為 。a1b3c5d7【 】4.四元式之間的聯(lián)系是通過(guò) 實(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-dabc-*(注：軟

2、單目減運(yùn)算符)【】8.過(guò)程的display表記錄了 。a過(guò)程的連接數(shù)據(jù)b過(guò)程的嵌套層次c過(guò)程的返回地址d過(guò)程的入口地址二填空題1 .編譯過(guò)程的六個(gè)階段為：詞法分析、 、語(yǔ)義分析、代碼優(yōu)化和目標(biāo) 代碼生成。2 .詞法分析階段的任務(wù)式從左到右掃描 ,從而逐個(gè)識(shí)別。3 .對(duì)于文法g1和g2,若有,則稱(chēng)文法g1和g2是等價(jià)的。4 .對(duì)于文法 ge : e- t|e+t t - f|t*f f -p af|p p f (e)|i,句型 t+t*f+i 的句柄是,最左素短語(yǔ)是 。所謂素短語(yǔ)是指這樣的一個(gè)短語(yǔ)，它至少含有一個(gè)終結(jié)符，并且，除它自身之外不再含任何更小的素短語(yǔ)。所謂最左素短語(yǔ)是指處于句型最左邊的

3、那個(gè)素短語(yǔ)。如， p*p和i是句型p*p+i的素短語(yǔ)，而 p*p 是它的最左素短語(yǔ)。5 .最右推導(dǎo)的逆過(guò)程稱(chēng)為 ,也稱(chēng)為。6 .規(guī)范規(guī)約中的可規(guī)約串是 ,算符優(yōu)先分析中的可規(guī)約串是 。7 . (av b ) a (cv ?d a e ) 的逆波蘭式是。8 .在屬性文法中文法符號(hào)的兩種屬性分別稱(chēng)為 和。9 .符號(hào)表的每一項(xiàng)是由名字欄和 兩個(gè)欄目組成。在目標(biāo)代碼生成階段，符號(hào)表 是 的依據(jù)。10 . 一個(gè)過(guò)程的 display 表的內(nèi)容是它的 的display表的內(nèi)容加上 三 有窮自動(dòng)機(jī)m接受字母表 =0,1上所有滿足下述條件的串：每個(gè) 1都有0直接跟在右 邊。構(gòu)造一個(gè)最小的 dfa m及和m等價(jià)

4、的正規(guī)式。四證明正規(guī)式(ab)*a與正規(guī)式a(ba)*等價(jià)(用構(gòu)造他們的最小的dfa方法)。五 寫(xiě)一個(gè)文法，使其語(yǔ)言是：l = 1 n0mlm0n | m,n >0 六對(duì)文法gss asb|pp bpc | bqcq f qa | a(1) 它是否是算符優(yōu)先文法？請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表(2) 文法gs消除左遞歸、提取左公因子后是否是ll (1)文法？請(qǐng)證實(shí)。七已知文法g為：(0) s' f s(1) s - aad(2) s bac(3) s - aec(4) s - bed(5) a e試構(gòu)造它的lr (1)項(xiàng)目集、可歸前綴圖和 lr (1)分析表。八已知源程序如下：prod:=

5、0;i:=1;while i w 20 dobeginprod:=prod+ai*bi; i:=i+1end;試按語(yǔ)法制導(dǎo)翻譯法將源程序翻譯成四元式序列(設(shè)a是數(shù)組a的起始地址，b是數(shù)組b的起始地址；機(jī)器按字節(jié)編址，每個(gè)數(shù)組元素占四個(gè)字節(jié))。九設(shè)有以下程序段procedure p(x,y,z)beginy:=y*3;z:=x+z;end;begina:=5; b:=2;p(a*b,a,a);print(a);end若參數(shù)傳遞的方法分別為(1)傳值、(2)傳地址、(3)傳名，試問(wèn)結(jié)果分別什么？十 對(duì)以下文法，請(qǐng)寫(xiě)出關(guān)于括號(hào)嵌套層數(shù)的屬性文法。 (為s,l引入屬性h,用來(lái)記錄輸出配對(duì)的括號(hào)個(gè)數(shù))文

6、法規(guī)則語(yǔ)義規(guī)則s-(t)sfitft,stfs對(duì)pl/0 語(yǔ)言的while 語(yǔ)句while 條件b do 語(yǔ)句s 的編譯程序,請(qǐng)?jiān)诳杖碧幪羁眨瓿稍撜Z(yǔ)句的編譯算法：switch (sym) case whilesym:;getsym();condition(symsetadd(dosym,fsys),lev,tx);gen(jpc,0,0);if (sym=dosym) else error(18);statement(fsys,lev,tx);gen(jmp,0,cx1);；break;-3 -編譯原理樣題參考答案選擇題（12分）1. d 2. d 3. b 4. a 5. d 6. c7.

7、 b8. b填空題（8分）1.語(yǔ)法分析2.源程序3. l(g1)=l(g2)中間代碼生成單詞（或g1和g2的語(yǔ)言相同）6.7.8.句柄最左素短語(yǔ)abvcd ?eava繼承屬性綜合屬性（次序可換）4. t5.規(guī)范歸約t*f最左歸約9.信息欄10.直接外層地址分配本過(guò)程的sp的地址最小的dfam如下圖所示:*與m等價(jià)的正規(guī)式為:* *(0 i (10)四 正規(guī)式（ab） * a對(duì)應(yīng)的nf做口圖:正規(guī)式a（ba）對(duì)應(yīng)的nfa如圖:這兩個(gè)正規(guī)式最終都可得到最簡(jiǎn)的 dfa如圖所示:所以這兩個(gè)正規(guī)式等價(jià)。五文法g: s -1s0 | aa - 0a1 |£六 1.求出gs的firstvt 集和l

8、astvt集:fierstvt (s) =a,bfierstvt(p尸bfierstvt(q尸alastbvt (s) =b,clastbvt (p) =clastbvt (q) =a-7 -構(gòu)造優(yōu)先關(guān)系表為:abca< ><>b< >c>>由于在優(yōu)先關(guān)系中同時(shí)出現(xiàn)了a<a和a>a以及b<b和b>b ,所以該文法不是算符優(yōu)先文法。2.消除左遞歸和提取左公因子后的文法為:s 一asb|pp 一 bp'p'沖c |qcq 一 aq'q' aq' | e求具有相同左部的兩個(gè)產(chǎn)生式的sele

9、ct 集的交集:select(s f asb) n select(s 一 p) = a n first(p) = a n b= select(p ' 一 pc) n select(p ' 一 qc) = first(p) n first(q尸bn a=select( q 一 aq' ) n select(q ' 一 f ) a n follow(q) = a n c= 所以修改后的文法是ll (1)文法。七 lr(1)項(xiàng)目集和可歸前綴圖如下構(gòu)造lr(1)分析表 如下:狀態(tài)actiongotoabcde#sa0s2s311acc2s53s74s85s9r56s107r5s118r19r310r211r4八四元式序列100 prode:=0101 i:=1102 if i <20 goto 104103 goto 114104 t1:=4*i105 t2:=a-4106 t3:=t2t1107 t4:=4*i108 t5:=b-4109 t6:=t5t4110 t7:=t3*t6111 prod:二prod