編譯原理模擬試卷

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

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

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

4、| E | unsigned_integer四、一個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); main()long i1,i2,i3; func(i1,i2,i3);該程序在某種機器的Linux 上的運行結果如下：Addresses of i1,i2,i3 = 27777775460,27777775464,277777

5、75470Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434從上面的結果可以看出，func 函數(shù)的 3 個形式參數(shù)的地址依次升高，而3個局部變量的地址依次降低。試說明為什么會有這個區(qū)別。五、 考慮下面的三地址語句序列：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、成基本塊，并給每個基本塊一個序號。（ 2）畫出該代碼的控制流圖，每個基本塊就用（1）的序號表示。（ 3）若有循環(huán)的話，列出構成每個循環(huán)的結點。模擬試卷C1、 下面是用正規(guī)式表示的變量聲明：（ int | float ） id （, id ）* ;請改用上下文無關文法表示，也就是寫一個上下文無關文法，它和該正規(guī)式等價。2、 下面的文法產(chǎn)生代表正二進制數(shù)的0 和 1 的串集：B B 0 | B 1 | 1下面的翻譯方案計算這種正二進制數(shù)的十進制值：BB1 0B. val:=B1.val2|B1 1B. val:=B1.val2+1|1 B. val:= 1 請消除該基礎文法的左遞歸，再重寫一個翻譯

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

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

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

10、)文法。三、考慮一個類Pascal的語言，其中所有的變量都是整型(不需要顯式聲明)，并且僅包含賦值語句、讀語句、寫語句，條件語句和循環(huán)語句。下面的產(chǎn)生式定義了該語言的語法(其中l(wèi)it 表示整型常量；OP 的產(chǎn)生式?jīng)]有給出，因為它和下面討論的問題無關)。定義Stmt的兩個屬性：MayDef表示它可能定值的變量集合，MayUse表示它可 能引用的變量集合。寫一個語法制導定義或翻譯方案，它計算 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語百中，3+和(id + id )+這樣的表達式被編譯時，編譯器都會報告如 下的錯誤：invalid lvalue in increment現(xiàn)有如下簡化的C 語言表達式文法：E E + E | ( E ) | E + |id | num請寫一個語法制導定義或翻譯方案，它檢查+的運算對象是否合法。一個 C 語言程序如下：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 = %