1、編譯原理模擬試卷及答案（二） 學生姓名：_ 學號：_學生系別：_ 專業：_ 年級_班級_ 課程名稱：編譯原理 課程性質：專業必修一、 文法G<E>的產生式為：（12%）<E>®<E> + <T> | <T> <T>®<T> * <E> | <F><F>® I | (<E>)a)給出（I+I）* I的最左推導、最右推導及相應的推導樹；b)列出句型<F> + <T> * <F>的所有短語、簡單短語和句柄

2、。答：a)最左推導：<E>Þ<T>Þ<T>*<E>Þ<F>*<E>Þ(<E>)*<E>Þ(<E>+<T>)*<E>Þ(<T>+<T>)*<E>Þ(<F>+<T>)*<E>Þ(I+<T>)*<E>Þ(I+<F>)*<E>Þ(I+I)*<E>

3、;Þ(I+I)*<T>Þ(I+I)*<F>Þ(I+I)*I最右推導：<E>Þ<T>Þ<T>*<E>Þ<T>*<T>Þ<T>*<F>Þ<T>*IÞ<F>*IÞ(<E>)*IÞ(<E>+<T>)*IÞ(<E>+<F>)*IÞ(<E>+I)*IÞ(&

4、lt;T>+I)*IÞ(<F>+I)*IÞ(I+I)*I推導樹如下：b)所有短語：<F>(2個)、<T>*<F>、<F> + <T> * <F>簡單短語：<F>(2個)短語：<F>二、構造下列正則表達式的確定性的有限狀態自動機。 （12%）aba(a|b)*a答： 三、證明下面文法是SLR(1)文法，并構造其SLR分析表。 （15%）<E>®<E> + <T> | <T><T>®&l

5、t;T> <F> | <F><F>®<F>* | a | b答：分析表如下所示：狀 態 T項 目 集輸入符號下一狀態0*<E>·<E><E>1<E>·<E>+<T><E>1<E>·<T><T>2<T>·<T><F> <T>2<T>·<F> <F>3<F>·&l

6、t;F>* <F>3<F>·a a4<F>·b b51*<E><E>·Accept*<E><E>·+<T>+62*<E><T>·/+#2*<T><T>·<F><F>7<F>·<F>* <F>7<F>·a a4<F>·b b53*<T><F>·

7、 /+/a/b#4*<F><F>·* *84*<F>a· #65*<F>b· #76*<E><E>+·<T><T>9<T>·<T><F> <T>9<T>·<F> <F>3<F>·<F>* <F>3<F>·a a4<F>·b b57*<T><T>&

8、lt;F>· /+/a/b#3*<F><F>·* *88*<F><F>*· #59*<E><E>+<T>·/+#1*<T><T>·<F> <F>7<F>·<F>* <F>7<F>·a a4<F>·b b5四、寫出下列表達式的三地址形式的中間表示。 （16%）（1） 5+6 ´ (a + b);（2） Ø

9、;AÚ( B Ù (C Ú D);（3） for j:=1 to 10 do aj + j:=0;（4） if x > y then x:=10 else x:= x + y;答： 100:t1:=a+b101:t2:=6*t1102:t3:=5+t2 100:if A goto 102101:goto T102:if B goto 104103:goto F 104:if C goto T105:goto 106106:if D goto T107:goto F 100:j:=1101:if j>10 goto NEXT102:i:=j+j103:a

10、i:=0104:goto 101 100:if x>y goto 102101:goto 104102:x:=10103:goto 105104:x:=x+y105:五、條件語句可形式定義為：(20%)<S> à IF <E> THEN <S>1 ELSE <S>2其中<E>帶有屬性1<E>.type 值為“boolean” 表示<E>是布爾類型2<E>.true 和<E>.false 值為<E>中真和假的尚待回填的出口的鏈首指針條件語句的語義可描述為：t:=

11、e;if not t then goto L1; <S>1;goto L2;L1: <S>2;L2:其中 e 為<E>的值。試用句法制導翻譯的方法寫出符合上述要求的條件語句的翻譯方案。答：條件語句的屬性翻譯文法為：<if1>®if<E>CheckBool(<E>.type);TLT:=NewTL;GEN(LABEL,TLT);Backpatch(<E>.true,TLT);<if1>.false:=<E>.false;<if2>®<if1> t

12、hen <S>1 <if2>.TL:=NewTL;GEN(BR, <if2>.TL);TLF:=NewTL;GEN(LABEL,TLF);Backpatch(<E>.false,TLF);<S>®<if2> else <S>2GEN(LABEL,<if2>.TL);六、對如下程序框架,若采用以過程為單位、二級存儲區的存儲分配方法.試寫出當程序流到達L時,整個運行棧的內容. （15）procedure main procedure q(x,y : int)begin Z:real; arra

13、y Bx.y of real; begin D,E: real; array C1.600 of int;end;begin array A1.x of real;begin E,F : int; L:end;end;end;/q begin r,s : int; array T10.400 of real; call q(1,200); end;/main要求用圖的形式詳細列出調用記錄中各個項的分布情況。答：調用記錄中各項的分布情況如圖6.29所示：七、設基本塊p由如下語句構成：（10）T0: =3.14; T1:=2*T0; T2:=R+r; A:=Tl*T2； B:=A; T3:=2*T0;T4:=R+r;T5:=T3*T4;T6:=R-r；B:=T5*T6；a)試給出基本塊p的DAG。b)根據DAG重寫基本塊。c)若p所在的程序中只有A和B在p后將要被引用，試寫出優化后的基本塊。答：1）基本塊 p 的DAG如圖7.1所示。圖7.1 基本塊 p 的DAG2）因為DAG重寫基本塊必須滿足的約束條件是：DAG中各節