編譯原理模擬試卷

1、說(shuō)明： 向?qū)W生提供這門課程的4 份模擬考試試題與答案。試題最好分開(kāi)放題和客觀題兩類，客觀題提供答案，開(kāi)放題提供解題思路。如果期末的評(píng)估要求學(xué)員提交論文或作品，教師需提供評(píng)價(jià)標(biāo)準(zhǔn)。模擬試卷模擬試卷A1、 處于 /* 和 */之間的串構(gòu)成注解，注解中間沒(méi)有*/，請(qǐng)根據(jù)詞法分析基本方法，畫(huà)出接受這種注解的DFA 的狀態(tài)轉(zhuǎn)換圖。2、 根據(jù)自上而下的語(yǔ)法分析方法，構(gòu)造下面文法的LL（ 1）分析表。D TLTint | realLid RR , id R |三、根據(jù)自下而上的語(yǔ)法分析方法，為下面文法構(gòu)造規(guī)范LR（1）分析表，畫(huà)出狀態(tài)轉(zhuǎn)換圖就可以了。然后說(shuō)明它是否有動(dòng)作沖突。S V = E | EV E |

2、 idE V何謂語(yǔ)法制導(dǎo)的定義？為下面文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)的定義，它完成一個(gè)句子while-do 最大嵌套層次的計(jì)算并輸出這個(gè)計(jì)算結(jié)果。S EE while E do E | id := E | E + E | id | （E）五、 請(qǐng)根據(jù)數(shù)據(jù)流分析方法，對(duì)下面的程序片段作出其程序流圖并計(jì)算：（ 1）各基本塊的到達(dá)_定值集INB ；（ 2）各基本塊中各變量引用點(diǎn)的ud 鏈；I := 1J := 0II : J := J + Iread Iif I 100 goto L2write JhaltIII : I := I * Igoto L1模擬試卷B1、 敘述下面的正規(guī)式描述的語(yǔ)言，并畫(huà)出接受該語(yǔ)言

3、的最簡(jiǎn)DFA 的狀態(tài)轉(zhuǎn)換圖。( 1 | 01 )* 0*2、 ( 1)通過(guò)構(gòu)造識(shí)別活前綴的DFA 和構(gòu)造分析表，來(lái)證明文法E E + id | id是SLR(1)文法。( 2)下面左右兩個(gè)文法都和(1)的文法等價(jià)E E + M id | idE M E + id | idMM請(qǐng)指出其中有幾個(gè)文法不是LR(1)文法，并給出它們不是LR(1)文法的理由。3、 為下面的算術(shù)表達(dá)式文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)的翻譯方案，它將每個(gè)子表達(dá)式E的符號(hào)(即值大于零還是小于零)記錄在屬性 E.sign中(屬性值分別用POS或 NEG 表示) 。你可以假定所有的整數(shù)都不為零，這樣就不用擔(dān)心零的符號(hào)。E E *E | +E

4、| E | unsigned_integer四、一個(gè)C語(yǔ)言程序如下：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); main()long i1,i2,i3; func(i1,i2,i3);該程序在某種機(jī)器的Linux 上的運(yùn)行結(jié)果如下：Addresses of i1,i2,i3 = 27777775460,27777775464,277777

5、75470Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434從上面的結(jié)果可以看出，func 函數(shù)的 3 個(gè)形式參數(shù)的地址依次升高，而3個(gè)局部變量的地址依次降低。試說(shuō)明為什么會(huì)有這個(gè)區(qū)別。五、 考慮下面的三地址語(yǔ)句序列：b := 1b := 2if w = x goto L2e := bgoto L2L1: goto L3L2: c := 3b := 4c := 6L3: if y = z goto L4goto L5L4: g := g + 1h := 8goto L1L5: h := 9（ 1）在該代碼中用水平的橫線將代碼分

6、成基本塊，并給每個(gè)基本塊一個(gè)序號(hào)。（ 2）畫(huà)出該代碼的控制流圖，每個(gè)基本塊就用（1）的序號(hào)表示。（ 3）若有循環(huán)的話，列出構(gòu)成每個(gè)循環(huán)的結(jié)點(diǎn)。模擬試卷C1、 下面是用正規(guī)式表示的變量聲明：（ int | float ） id （, id ）* ;請(qǐng)改用上下文無(wú)關(guān)文法表示，也就是寫(xiě)一個(gè)上下文無(wú)關(guān)文法，它和該正規(guī)式等價(jià)。2、 下面的文法產(chǎn)生代表正二進(jìn)制數(shù)的0 和 1 的串集：B B 0 | B 1 | 1下面的翻譯方案計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值：BB1 0B. val:=B1.val2|B1 1B. val:=B1.val2+1|1 B. val:= 1 請(qǐng)消除該基礎(chǔ)文法的左遞歸，再重寫(xiě)一個(gè)翻譯

7、方案，它仍然計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值。3、 為下面文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)的定義，用S 的綜合屬性val 給出下面文法中S產(chǎn)生的二進(jìn)制數(shù)的值。例如， 輸入 101.101 時(shí)， S. val := 5.625。（不得修改文法。）SL . R| LLL B |BRB R |BB0 | 14、 對(duì)于下面C 語(yǔ)言文件s.cf1(int x)long x;x = 1;f2(int x)long x;x = 1;某編譯器編譯時(shí)報(bào)錯(cuò)如下：s.c: In function f1 :s.c:3: warning: declaration of x shadows a parameter 請(qǐng)回答，對(duì)函數(shù)f2 為什

8、么沒(méi)有類似的警告錯(cuò)誤。五、 考慮一個(gè)簡(jiǎn)單語(yǔ)言，其中所有的變量都是整型(不需要顯式聲明)，并且僅包含賦值語(yǔ)句、讀語(yǔ)句和寫(xiě)語(yǔ)句。下面的產(chǎn)生式定義了該語(yǔ)言的語(yǔ)法(其中l(wèi)it表示整型常量；OP的產(chǎn)生式?jīng)]有給出，因?yàn)樗拖旅嬗懻摰膯?wèn)題無(wú)關(guān))。Program StmtListStmtList Stmt StmtList | StmtStmt id := Exp; | read (id ); | write ( Exp );Exp id | lit | Exp OP Exp我們把不影響write語(yǔ)句輸出值的賦值(包括通過(guò)read語(yǔ)句來(lái)賦值)稱為無(wú)用賦值， 寫(xiě)一個(gè)語(yǔ)法指導(dǎo)定義，它確定一個(gè)程序中出現(xiàn)過(guò)賦予無(wú)用值

9、的變量集合(不需要知道無(wú)用賦值的位置)和沒(méi)有置初值的變量集合(不影響write 語(yǔ)句輸出值的未置初值變量不在考慮之中)。非終結(jié)符StmtList和Stmt用下面3個(gè)屬性(你根據(jù)需要來(lái)定義其它文法符號(hào)的屬性) ：(1) uses_in：在本語(yǔ)句表或語(yǔ)句入口點(diǎn)的引用變量集合，它們的值影響在該程序點(diǎn)后的輸出。(2) uses_out在本語(yǔ)句表或語(yǔ)句出口點(diǎn)的引用變量集合，它們的值影響在該程序點(diǎn)后的輸出。(3) useless本語(yǔ)句表或語(yǔ)句中出現(xiàn)的無(wú)用賦值變量集合。模擬試卷D描述由正規(guī)式b*(abb*)*(a| )定義的語(yǔ)言，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn)DFA。、證明文法E E + id | id是SLR(1

10、)文法。三、考慮一個(gè)類Pascal的語(yǔ)言，其中所有的變量都是整型(不需要顯式聲明)，并且僅包含賦值語(yǔ)句、讀語(yǔ)句、寫(xiě)語(yǔ)句，條件語(yǔ)句和循環(huán)語(yǔ)句。下面的產(chǎn)生式定義了該語(yǔ)言的語(yǔ)法(其中l(wèi)it 表示整型常量；OP 的產(chǎn)生式?jīng)]有給出，因?yàn)樗拖旅嬗懻摰膯?wèn)題無(wú)關(guān))。定義Stmt的兩個(gè)屬性：MayDef表示它可能定值的變量集合，MayUse表示它可 能引用的變量集合。寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義或翻譯方案，它計(jì)算 Stmt的MayDef和MayUse屬性。Program StmtStmtid := ExpStmtread (id )Stmtwrite ( Exp )StmtStmt ; StmtStmt if ( Ex

11、p ) then begin Stmt end elsebegin Stmt endStmtwhile(Exp ) do begin Stmt endExpidExplitExpExpOP Exp四、在C語(yǔ)百中，3+和(id + id )+這樣的表達(dá)式被編譯時(shí)，編譯器都會(huì)報(bào)告如 下的錯(cuò)誤：invalid lvalue in increment現(xiàn)有如下簡(jiǎn)化的C 語(yǔ)言表達(dá)式文法：E E + E | ( E ) | E + |id | num請(qǐng)寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義或翻譯方案，它檢查+的運(yùn)算對(duì)象是否合法。一個(gè) C 語(yǔ)言程序如下：typedef struct _a short i; short j; short k;a;typedef struct _b long i; short k;b;main() printf(Size of short, long, a and b = %