相应的翻译方案如下：
B ? 1 {B?.i := 1 }B?{B.val := B?.val} B? ? 0 {B?1.i := B?.i ? 2 } B?1 {B?.val := B?1.val} | 1 {B?1.i := B?.i ? 2 +1} B?1 {B?.val := B?1.val} | ? {B?.val := B?.i}
8、表达式&i的类型表达式是pointer(long)，表达式&i?&j的类型表达式是long。按照C语言的规定，指向同一个类型的两个指针可以相加减，它们值的差是它们之间的元素个数。 9、左边的编译器版本：一般只为局部变量分配空间。调用函数前，用若干次pushl指令将参数压栈，返回后用addl $n, %esp一次将所有参数退栈（常数n根据调用前做了多少次pushl来决定）。 右边的编译器版本：除了为局部变量分配空间外，同时还为本函数中出现的函数调用的参数分配空间，并且参数所用空间靠近栈顶。调用函数前，用movl指令将参数移入栈顶，调用结束后无需参数退栈指令。 优点是每次函数调用结束后不需要执行addl $n, %esp指令，另外增加优化的可能性。
第21页共6页
《编译原理》期末试题（三）
1、 从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？ 答：从优化的范围的角度，优化可以分为局部优化和全局优化两类； 对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强度削减。 2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+:= 四元式序列：
三元式序列: OP ARG1 ARG2
(1) (* b， c ) (2) (* b， d ) (3) (+ (1)， (2)) (4) (:= (3)， a)
(1) (*， b， c， t1) (2) (*， b， d， t2) (3) (+， t1， t2，t3) (4) (:=， t3， /， a)
3、对于文法G(S):
S ?bMbM ?(L|aL ?Ma）
答：1） S?bMb?b(Lb?b(Ma)b 2） 短语: Ma)， (Ma)， b(Ma)b
直接短语: Ma) 句柄: Ma)
b ( S M b T L M a ) 三、 设有字母表{a，b}上的正规式R=(ab|a)*。
解：（1）
2 - 0 ε a 1 a b ε + 3
（2）将（1）所得的非确定有限自动机确定化
ε a b -0 1 1 3 12 2 1 +3 第22页共6页
2 +
-+ a 0 b a 1 + a
（3）对（2）得到的DFA化简，合并状态0和2 为状态2：
2 -+ b a 1 +
（4）令状态1和2分别对应非终结符B和A
G: A→aB|a|ε； B→aB|bA|a|b|ε；可化简为：G: A→aB|ε；B→aB|bA|ε
a 四、 设将文法G改写成等价的LL(1)文法，并构造预测分析表。
G：S→S*aT|aT|*aT； T→+aT|+a
解：消除左递归后的文法G’: S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT|+a
提取左公因子得文法G’’: S→aTS’|*aTS’
S’→*aTS’|ε T→+aT’
T’→T|ε Select(S→aTS’)={a} Select(S→*aTS’)={*}
Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}
Select(S’→ε)=Follow(s’)={#}
Select(S’→*aTS’)∩Select(S’→ε)= Ф Select(T→+aT’)={+}
Select(T’→T)=First(T) ={+}
Select(T’→ ε)=Follow(T’)={*,#}
Select(T’→T)∩Select(T’→ε)= Ф 所以该文法是LL(1)文法。 预测分析表： * + a # S →*aTS’ →aTS’ 第23页共6页
S’ →*aTS’ T T’ → ε →ε → ε →+aT’ →T 6设文法G 为： S→A；A→BA|ε；B→aB|b
解：（1）拓广文法G’：(0) S’→S (1) S→A (2) A→BA(3) A→ε(4)
B→aB (5) B→b ； FIRST(A) = {ε, a, b}；FIRST(B) = {a, b}
构造的DFA 如下:
项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。
（2） LR(1)分析表如下：
(3)输入串abab 的分析过程为：
第24页共6页
简答题 3、设有文法G[S]: S→S(S)S|ε，该文法是否为二义文法？说明理由。 答：是二义的，因为对于（）（）可以构造两棵不同的语法树。 S S
S ( S ) S S ( S ) S
ε ε S ( S ) S S ( S ) S ε ε
ε ε ε ε ε ε
五、 给定文法G[S]：
S→aA|bQ； A→aA|bB|b；B→bD|aQ ；Q→aQ|bD|b；D→bB|aA ；E→aB|bF F→bD|aE|b
构造相应的最小的DFA 。
解：先构造其NFA： 用子集法将NFA确定化：
S A Q BZ DZ D B a A A Q Q A A Q b Q BZ DZ D B B D
将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。
第25页共6页