(2) (j, _, _, (12)) (3) (j>, c, ‘0’, (5)) (4) (j, _, _, (8)) (5) (+, a, ‘1’, T1)) (6) (:=, T1, _, a) (7) (j, _, _, (1)) (8) (*, a, ‘13’, T2) (9) (-, T2, ‘1’, T3) (10) (:=, T3, _, a) (11) (j, _, _, (1)) 6.优化后的四元序列
D:=A-C E:=A*C F:=D*E M:=F+20 7. 最左推导
S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a)) 短语
((T,S),a) (T,S),a (T,S) T,S a
直接短语 T,S a 句柄 T,S 8.(1)
S→do M1 S1while M2 E M→ε (2)
M→ε {M.quad=nestquad;}
S→do M1 S1while M2 E {backpatch(s1.nextlist, M2.quad); backpatch(E.truelist, M1.quad); S.nextlist=E.falelist; }
9.(1) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde
(2) 短语: aAbcde, Ab, d 素短语: Ab, d 10.(1) S →(L) | aS’ S’→S |ε L→SL’
L’→,SL’ |ε
(2) FIRST(S)={a, (} FIRST(S’)={a, (, ε} FIRST(L)={a, (} FIRST(L’)={,, ε}
FOLLOW(S)={,, ), #} FOLLOW(S’)={,, ), #} FOLLOW(L)={ )} FOLLOW(L’)={ )}
第16页共6页
(3)
( ) a , S S →(L) S → aS? S? S?→S S?→ε S?→S S?→ε L L→SL? L→SL? L?→,SL? L? L?→ε
11.(1) (j>, X, 0, (5))
(2) (j, _, _, (3)) (3) (j<, Y, 0, (5)) (4) (j, _, _, (11)) (5) (j>0, X, 0, (7)) (6) (j, _, _, (7)) (7) (*, A, 3, T1) (8) (:=, T1, _, N) (9) (j, _, _, (5)) (10) (j, _, _, (13)) (11) (+, B, 3, T2) (12) (:=, T2, _, Y)
12.(1) E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T =>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T =>(i+i)*i+F=>(i+i)*i+i
(2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短语 i, E+T 最左素短语 E+T
13.(1) FIRSTVT(S)={∨, ∧, i, - } FIRSTVT(T)={∧, i, -} FIRSTVT(U)={i, -}
LASTVT(S)={∨, ∧, i, - }
LASTVT(T)={∧, i, -}
LASTVT(U)={i, -}
(2)
i ∨ ∧ - S .> .> ∨ <. .> <. <. ∧ <. .> .> <. - <. .> .> <.
# S?→ε 第17页共6页
《编译原理》期末试题（二）
1、描述由正规式b*(abb*)*(a| ?)定义的语言，并画出接受该语言的最简DFA。 2、证明文法E ? E + id | id是SLR(1)文法。
3、下面是表达式和赋值语句的文法，其中and的类型是bool ? bool ? bool，+的类型是int ? int ? int，=的类型是int ? int ? bool，:= 要求id 和E的类型都是int或者都是bool。为该文法写一个语法制导定义或翻译方案，它完成类型检查。
S ? id := E
E ? E and E | E + E | E = E |id
4、对于下面C语言文件s.c f1(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 请回答，对函数f2为什么没有类似的警告错误。
5、下面C语言程序经非优化编译后，若运行时输入2，则结果是 area=12.566360, addr=-1073743076 经优化编译后，若运行时输入2，则结果是 area=12.566360, addr=-1073743068 请解释为什么输出结果有区别。
main() {
float s, pi, r; pi=3.14159; scanf(\ printf(\ addr=%d\\n\
}
6、描述由正规式b?a(bb?a) ?b?定义的语言，并画出接受该语言的最简DFA。 7、下面的文法产生代表正二进制数的0和1的串集： B ? B 0 | B 1 | 1
第18页共6页
下面的翻译方案计算这种正二进制数的十进制值：
B ? B1 0 {B.val := B1.val ? 2 } | B1 1 {B.val := B1.val ? 2 +1} | 1 {B.val := 1 } 请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值。
8、 在C语言中，如果变量i和j都是long类型，请写出表达式&i和表达式&i?&j的类型表达式。为帮助你回答问题，下面给出一个程序作为提示，它运行时输出1。 main() { long i, j; printf(“%d\\n”, &i?&j); }
9、一个C语言的函数如下： func(i) long i; { long j; j = i – 1; func(j); }
下面左右两边的汇编代码是两个不同版本GCC编译器为该函数产生的代码。左边的代码在调用func之前将参数压栈，调用结束后将参数退栈。右边代码对参数传递的处理方式没有实质区别。请叙述右边代码对参数传递的处理方式并推测它带来的优点。 func: | func: pushl ?p | pushl ?p movl %esp, ?p | movl %esp, ?p subl $4, %esp | subl $8, %esp movl 8(?p), íx | movl 8(?p), êx decl íx | decl êx movl íx, -4(?p) | movl êx, -4(?p) movl -4(?p), êx | movl -4(?p), êx pushl êx | movl êx, (%esp) call func | call func addl $4, %esp | leave leave | ret ret |
编译原理试卷八答案
1、由正规式b*(abb*)*(a| ?)定义的语言是字母表{a, b}上不含子串aa的所有串的集合。最简DFA如下：
b start 1 b a 2 第19页共6页
2、先给出接受该文法活前缀的DFA如下：
E? ?·E E ?·E + id E ?·id I0 id E ? id· I2 E ? E +·id I3 id E ? E + id· I4 E E? ? E· E ? E·+ id I1 +
I0和I3都只有移进项目，肯定不会引起冲突；I2和I4都无移进项目并仅含一个归约项目，也肯定不会引起冲突；在I1中，E?的后继符号只有$，同第2个项目的展望符号“+”不一样，因此I1也肯定不会引起冲突。由此可以断定该文法是SLR(1)的。
3、语法制导定义如下。
S ? id := E { S.type := if (id.type = bool and E.type = bool) or (id.type = int and E.type = int)then type_ok else type_error } E ? E1 and E2
type_error }
{ E.type := if E1.type = bool and E2.type = bool then bool else
E ? E1 + E2 { E.type := if E1.type = int and E2.type = int then int else type_error } E ? E1 = E2 { E.type := if E1.type = int and E2.type = int then bool else type_error } E ? id { E.type := lookup(id.entry) }
4、对于函数f1，局部变量x声明的作用域是整个函数体，导致在函数体中不可能访问形式参数x。由于这是一个合法的C语言函数，因此编译器给出警告错误。
对于函数f2，由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。
5、使用非优化编译时，变量s, pi, r在局部数据区都分配4个字节的空间。使用优化编译时，由于复写传播，pi*r*r 变成3.14159*r*r，pi=3.14159成为无用赋值而删去，函数中不再有pi的引用，因此不必为pi分配空间。类似地，s=3.14159*r*r也是一个无用赋值（表达式要计算，但赋值是无用的），也不必为s分配空间。这样，和非优化情况相比，局部数据区少了8个字节， 因此r的地址向高地址方向移动了8个字节。
6、正规式b?a(bb?a) ?b?体现的特点是，每个a的左边都有若干b，除非a是第一个字母。该正规式定义的语言是：至少含一个a，但不含子串aa的所有a和b的串集。最简DFA如下：
b start 0 a b b
a 2 1
7、 消除左递归后的文法： B ? 1 B? B? ? 0 B? | 1 B? | ?
第20页共6页