注意 正规式不唯一 a) (a|b)*ab b) (bb)*
c) (a*ba*ba*)* d) b*ab*
e) (a|b)*ab(a|b)* f) b*a* 2答案：
a) 每个 1 至少有一个 0 跟在后边的串 b) 所有含两个相继的0或两个相继的1的串
c) 必须以 1 开头和0结尾的串 7答案：
(１) 先改写文法为： 0) A→baB 1) A→ε 2) B→baBbb 3) B→bb 4) B→a
再改写文法为：
0) A→baB 1) A→ε 2) B→bN 3) B→a 4) N→aBbb 5) N→b A B N 预测分析表： A B N a →a →aBbb FIRST {b} {b,a} {b,a} 由预测分析表中无多重入口判定文法是 LL(1)的。 1答案：
不妨约定:在进入一个非终结符号相应的子程序前，已读到一个单词.word：存放当前读
到的单词，Getsym()为一子程序，每调用一
次，完成读取一单词的工作。error()为出错处理
程序.FIRST(A)为终结符 A 的 FIRST 集. 类 C 程序如下： void A() {
if word=='[' {
Getsym(); B(); }
else error(); }
void B() { X();
if word==']' {
Getsym(); while(word in FIRST(A)) A(); }
else error(); }
void X() {
if (word= ='a'||word=='b') {
Getsym(); FOLLOW while(word= ='a'||word=='b') {#} Getsym(); {#,b} } {#,b } else error(); } b # 2baB 答案： →→ε 提示：B、C 排序.先将 A 代入 B →bN 不妨以 A、中，然后消除 B 中左递归；再将 A、B 代 →b 入 C 中。再消除 C 中左递归。 最后结果为:G[A]:
A→BaC|CbB B→CbBcB'|cB' B'→aCcB'|ε C→cB'bC'|bC' C'→bBcB'bC'|ε 3答案：
各非终结符的 FIRST 集和 FOLLOW 集如下：
36
FIRST（E）= { [ } FOLLOW（E）= {＃} FIRST（E′）= { [ ，ε} FOLLOW（E′）= {＃}
FIRST（F）= { a } FOLLOW（F）= { ] } FIRST（F′）= { a ，ε} FOLLOW（F′）= { ] } 对于 E’ → E.ε，FIRST(E)∩ FIRST(ε)= (注：句柄下面有下划线) (2)
步骤 栈 输 入 动 作
1 # (a, ((a, a), (a, a)))# 移进 2 #( a, ((a, a), (a, a)))# 移进
3 #(a , ((a, a), (a, a)))# 归约，S..a 4 #(S , ((a, a), (a, a)))# 归约，L..S φ
FIRST(E) ∩ FOLLOW（E’）= φ
对于 F’ → aF’.ε，FIRST(aF’)∩FIRST(ε)= φ FIRST（aF’）∩ FOLLOW（F’）= φ 所以, 文法 G[E]是 LL（1）文法。 6答案：
提取左公共因子和消除左递归后，G［A］变换为等价的G′［A］如下： A→a A′
A′→A B e|ε B→d B′ B′→b B′|ε
.. 计算非终结符的FIRST 集和FOLLOW集结果如下：
FIRST（A）= { a} FOLLOW（A）= {#,d } FIRST（B）= { d} FOLLOW（B）= { e } FIRST（A′）= { a,ε} FOLLOW（A′）= {#,d } FIRST（B′）= { b,ε} FOLLOW（B′）= { e } .. 对相同左部的产生式可知：
FIRST (A B e)∩FOLLOW (A′) ={ a }∩{#,d }=.
FIRST (b B′)∩FOLLOW (B′) ={ b }∩{ e }=.
所以 G′［S］是 LL(1) 文法。 1答案：
(1)S => ( L ) => (L, S) => (L, (L)) => (L, (L, S)) => (L, (L, (L))) => (L, (L, (L, S)))=> (L, (L, (L, a)))
=>(L,(L,(S, a))) => (L, (L, (a, a))) => (L, (S, (a, a))) => (L, ((L), (a, a))) => (L, ((L, S), (a, a)))
=>(L,((L,a), (a,a)))=> (L, ((S, a), (a, a))) => (L, ((a, a), (a, a))) => (S, ((a, a), (a, a))) => (a, ((a, a), (a, a)))
5 #(L , ((a, a), (a, a)))# 移进 6 #(L, ((a, a), (a, a)))# 移进 7 #(L, ( (a, a), (a, a)))# 移进 8 #(L, (( a, a), (a, a)))# 移进
9 #(L, ((a , a), (a, a)))# 归约，S..a 10 #(L, ((S , a), (a, a)))# 归约，L..S 11 #(L, ((L , a), (a, a)))# 移进 12 #(L, ((L, a), (a, a)))# 移进
13 #(L, ((L, a ), (a, a)))# 归约，S..a 14 #(L, ((L, S ), (a, a)))# 归约，L..L, S
15 #(L, ((L ), (a, a)))# 移进
16 #(L, ((L) , (a, a)))# 归约，S..(L) 17 #(L, (S , (a, a)))# 归约，L..S 18 #(L, (L , (a, a)))# 移进 19 #(L, (L, (a, a)))# 移进 20 #(L, (L, ( a, a)))# 移进
21 #(L, (L, (a , a)))# 归约，S..a 22 #(L, (L, (S , a)))# 归约，L..S 23 #(L, (L, (L , a)))# 移进 24 #(L, (L, (L, a)))# 移进
25 #(L, (L, (L, a )))# 归约，S..a 26 #(L, (L, (L, S )))# 归约，L..L, S 27 #(L, (L, (L )))# 移进
28 #(L, (L, (L) ))# 归约，S..(L) 29 #(L, (L, S ))# 归约，L..L, S 30 #(L, (L ))# 移进
31 #(L, (L) )# 归约，S..(L) 32 #(L, S )# 归约，L..L, S 33 #(L )# 移进
34 #(L) # 归约，S..(L) 35 #S # 接受 1答案：
给出下面表达式的逆波兰表示(后缀式)： (1) ab-c+*
(2)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示 if-then-else 运算）
37
如果写成这样： xy+z*0=sab+c*:=sabc**:=￥，则是错误的，因为写表达式和赋值语句 的中间代码序列，或是写它们的代码生成过程，必须注意按照算符优先序进行，这实际上是
按照 LR 分析过程进行的。例如：写出赋值语句 a:=a+b*c*(d+e)的四元式中间代码,当前四元 式序号为 100。不能写成： 100 (+,d,e,t1) 101 (*,b,c,t2) 102 (*,t2,t1,t3) 103 (+,a,t3,t4) 104 (:=,t4,-,a) 应该写成： 100 (*,b,c,t1) 101 (+,d,e,t2) 102 (*,t1,t2,t3) 103 (+,a,t3,t4) 104 (:=,t4,-,a) 2答案： 三元式：
100 (+, a, b) 101 (+, c, d) 102 (* , (1), (2))
38
103 (-, (3), /) 104 (+, a, b) 105 (+,(5),c) 106 (- (4), (6)) 间接三元式：
间接三元式序列 间接码表 100 (+，a, b) (100) 101 (+，c, d) (101) 102 (*，(1), (2)) (102) 103 (-，(3), /) (103)
104 (+，(1), c) (100) (104) 105 (-，(4), (1)) (105) 或者：
间接三元式： 100 (+，a, b) 101 (+，c, d) 102 (*，(1), (2)) 103 (-，(3), /) 104 (+，(1), c) 105 (-，(4), (1))
间接码表：100 101 102 103 100 104 105 四元式：
100 (+, a, b, t1) 101 (+, c, d, t2) 102 (*, t1, t2, t3) 103 (-, t3, /, t4) 104 (+, a, b, t5) 105 (+, t5, c, t6) 106 (-, t4, t6, t7) 树形：
逆波兰：ab+cd+*-ab+c+- 1答案：
假定翻译的四元式序列从（100）开始： （100） if A
（102） if C （106） goto （100） （107） 8答案： a) 语法树： b) 后缀式: a b c + uminus * c)三地址代码: t1 := b + c t2 := - t1 t3 := a * t2 9答案： 先写出三地址代码为： t1 := a + b t2 := - t1 t3 := c + d t4 := t2 * t3 t5 := a + b t6 := t5 + c t7: = t4 + t6 a)：对应的四元式为： op arg1 arg2 result (0) + a b t1 (1) uminus t1 t2 (2) + c d t3 (3) * t2 t3 t4 (4) + a b t5 (5) + t5 c t6 (6) + t4 t6 t7 b)：对应的三元式为： op arg1 arg2 (0) + a b (1) Uminus (0) (2) + c d (3) * (1) (2) (4) + a b (5) + (4) c (6) + (3) (5) c)：对应的间接三元式为：statement op arg1 arg2 (0) 15 15 + a b (1) 16 16 uminus 15 (2) 17 17 + c d (3) 18 18 * 16 17 (4) 15 19 + 15 c (5) 19 20 + 18 19 (6) 20 10答案： t11 := i * 20 t12 := t11+j 39 t13 := A-84; t14 := 4*t12 t15 := t13[t14] //A[i,j] t21 := i*20 t22 := t21+j t23 := B-84; t24 := 4*t22 t25 := t23[t24] //B[i,j] t31 := k*20 t32 := t31+l t33 := A-84 t34 := 4*t32 t35 := t33[t34] //A[k,l] t36 := 4*t35 t37 := C-4 t38 := t37[t36] //C[A[k,l]] t41 := i+j t42 := 4*t41 t43 := D-4 t44 := t43[t42] //D[i+j] t1 := t25 +t38 t2 := t1 + t44 t23[t24] := t2 2答案： 依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。 3答案： 1. 删除多余运算 2. 代码外提 3. 强度削弱 4. 变换循环控制条件 5. 合并已知量与复写传播 6. 删除无用赋值 1答案： 编译程序的实现途径可有： （１）手工构造：用机器语言、汇编语言或高级程序设计语言书写。 （２）自动构造工具：Lex,Yacc。 Lex ,Yacc 分别是词法和语法分析器的生成器。 （３）移植方式：目标程序用中间语言。 （４）自展方式：用 T 型图表示。 1答案： 用 T 型图 表示编译程序的实现 2答案： 用自展方式在 PC 机上实现 C 语言的编译程序，首先把 C 划分成真包含的子集 C1 和 C2，然后分 3 步实现。 3答案： 通常把某个机器(称为宿主机)上已有的软件移植到另一台机器(称为目标机) 4答案： 交叉编译是指把一个源语言在宿主机上经过编译产生目标机的汇编语言或机器语言。 5答案： 编译程序的实现 应考虑：开发周期、目标程序的效率、可移植性、可调试性、可维护 性、可扩充性等. 40