编译原理习题及答案

编译原理模拟试卷及答案（二） 学生姓名：_____________ 学号：___________________学生系别：_____________ 专业：______________ 年级___________班级_____________ 课程名称：编译原理 课程性质：专业必修一、 文法G[]的产生式为： （12%）® + | ® * | ® I | ()a)给出（I+I）* I的最左推导、最右推导及相应的推导树；b)列出句型 + * 的所有短语、简单短语和句柄答：a)最左推导：ÞÞ*Þ*Þ()*Þ(+)*Þ(+)*Þ(+)*Þ(I+)*Þ(I+)*Þ(I+I)*Þ(I+I)*Þ(I+I)*Þ(I+I)*I最右推导：ÞÞ*Þ*Þ*Þ*IÞ*IÞ()*IÞ(+)*IÞ(+)*IÞ(+I)*IÞ(+I)*IÞ(+I)*IÞ(I+I)*I推导树如下：b)所有短语：(2个)、*、 + * 简单短语：(2个)短语：二、构造下列正则表达式的确定性的有限状态自动机。

（12%）aba(a|b)*a答： 三、证明下面文法是SLR(1)文法，并构造其SLR分析表 （15%）® + | ® | ®* | a | b答：分析表如下所示：状 态 T项 目 集输入符号下一状态0*→·⊥1→·+1→·2→· 2→· 3→·* 3→·a a4→·b b51*→·⊥⊥Accept*→·++62*→·⊥/+#2*→·7→·* 7→·a a4→·b b53*→· ⊥/+/a/b#4*→·* *84*→a· #65*→b· #76*→+·9→· 9→· 3→·* 3→·a a4→·b b57*→· ⊥/+/a/b#3*→·* *88*→*· #59*→+·⊥/+#1*→· 7→·* 7→·a a4→·b b5四、写出下列表达式的三地址形式的中间表示。

（16%）（1） 5+6 ´ (a + b);（2） ØAÚ( B Ù (C Ú D));（3） for j:=1 to 10 do a[j + j]:=0;（4） if x > y then x:=10 else x:= x + y;答：⑴ 100: t1:=a+b 101: t2:=6*t1 102: t3:=5+t2⑵ 100: if A goto 102 101: goto T 102: if B goto 104 103: goto F 104: if C goto T 105: goto 106 106: if D goto T 107: goto F⑶ 100: j:=1 101: if j>10 goto NEXT 102: i:=j+j 103: a[i]:=0 104: goto 101⑷ 100: if x>y goto 102 101: goto 104 102: x:=10 103: goto 105 104: x:=x+y 105:五、条件语句可形式定义为： (20%) à IF THEN 1 ELSE 2其中带有属性1．.type 值为“boolean” 表示是布尔类型2．.true 和.false 值为中真和假的尚待回填的出口的链首指针条件语句的语义可描述为：t:=e;if not t then goto L1; 1;goto L2;L1: 2;L2:其中 e 为的值。