编译原理习题及答案

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中各节