2.输出是4231
3.句子b(aa)b的规范归约过程： 步骤 符号栈 0 1 2 3 4 5 6 7 8 9 10 # #b #b( #b(a #b(A #b(Ma #b(Ma) #b(B #bA #bAb #S 输入串 b(aa)b# (aa)b# aa)b# a)b# a)b# )b# b# b# b# # # 预备 移进 移进 移进 归约 移进 移进 归约 归约 移进 接受 动作 4.传地址 A=6, B=16 传值 A=2, B=4
nm
5.L(G)={dab |n>0, m≥0} 6.证明：
因为文法G[S]存在句子aa有两个不同的最左推导，所以文法G[S]是是二义性的。
S=>SaS=>SaSaS=>aSaS=>aaS=>aa S=>SaS=>aS=>aSaS=>aaS=>aa 7.句子 adccd 的分析过程： 步骤 符号栈 输入串 产生式 0 1 2 3 4 5 6 7 8 9 10 11 12 13 8.所求文法是G[S]: S→AB
A→aAc | D D→bD | b B→aBb | aabb
#S #AB #AAa #AA #Ad #A #SB #Sc #S #AB #Ac #A #d # adccd# adccd# adccd# dccd# dccd# ccd# ccd# ccd# cd# cd# d# d# d# # A→BS B→c B→c A→d A→d S→BA B→aA
第11页共6页
9.
函数 f g a 4 5 ( 2 5 ) 4 2 , 4 3 10.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化
11.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。
应着重考虑的问题：
(1)如何使生成的目标代码较短；
(2)如何充分利用寄存器，以减少访问内存次数； (3)如何充分利用指令系统的特点。 12.正规式 a ( a | b )*。
13.删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。 14.文法G[S]:
S→aB | a B→bc |bBc 15.传值 a=2 传地址 a=15
16.逆波兰式: abcd-*e/+
三元序列: op arg1 arg2 (1) - c d (2) * b (1) (3) / (2) e (4) + a (3) 17.证明：
因为文法G[S]存在句子 () 有两个不同的最左推导，所以文法G[S]是是二义性的。
A=>AA=>(A)A=>()A=>()
A=>AA=>A=>(A)=>()
**
18.(ab|ba)={a,b,ab,ba,aab,bba??} 19.Display表: 嵌套层次显示表
由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display表就是用于登记每个外层过程的最新活动记录起始地址。 20.传地址 a=12 传值 a=5
21.所求文法是G[S]: S→AC
A→aaAbb | ab C→ccC | cc
22.逆波兰式 abc+e*bc+f/+:=
三元序列 op arg1 arg2 (1) + b c (2) * (1) e (3) + b c (4) / (3) f (5) + (2) (4) (6) := a (5)
第12页共6页
23.一个文法G别是LL(1)文法的充要条件是: (1) FIRST(α) ∩FIRST(β)=Ф
*
(2) 如果 β=>ε, FIRST(α) ∩FOLLOW(A)= Ф 24.消除左递归
S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF | +a
提公共左因子,文法 G’(S) S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF’ F’→F |ε
25.作用：登记源程序中出现的各种名字及其信息，以及了解各阶段的进展状况。 主要技术：线性表，对折查找，杂奏技术。 五、计算题： 1.设文法G(S):
S→^ | a | (T) T→T,S | S
⑴ 消除左递归；
⑵ 构造相应的FIRST和FOLLOW集合； ⑶ 构造预测分析表 2.语句 if E then S
(1) 改写文法，使之适合语法制导翻译； (2) 写出改写后产生式的语义动作。 3.设文法G（S）： S→(T) | a T→T+S | S
(1）计算FIRSTVT 和LASTVT； （2）构造优先关系表。 4.设某语言的for语句的形式为
(1)(2)
for i:＝E to E do S 其语义解释为
(1)
i:＝E
(2)
LIMIT:＝E
again: if i＜＝LIMIT then
Begin S;
i:＝i＋1 goto again End;
（1）写出适合语法制导翻译的产生式； （2）写出每个产生式对应的语义动作。 5.把语句
while a<10 do
if c>0 then a:=a+1
else a:=a*3-1;
翻译成四元式序列。 6.设有基本块 D:=A-C
第13页共6页
E:=A*C F:=D*E S:=2 T:=A-C Q:=A*C G:=2*S J:=T*Q
K:=G*5 L:=K+J M:=L
假设基本块出口时只有M还被引用，请写出优化后的四元序列。 7.已知文法G(S) S→a | ^ | (T) T→T,S | S
(1) 给出句子(a,(a,a))的最左推导；
(2) 给出句型((T,S),a)的短语, 直接短语，句柄。 8.对于 C 语言do S while E语句
(1)改写文法，使之适合语法制导翻译； (2)写出改写后产生式的语义动作。 9.已知文法G(S) S→aAcBe A→Ab| b B→d
(1)给出句子abbcde的最左推导及画出语法树； (2)给出句型aAbcde的短语、素短语。 10.设文法G(S):
S→(T) | aS | a T→T,S | S
⑴消除左递归和提公共左因子；
⑵构造相应的FIRST和FOLLOW集合； ⑶构造预测分析表。 11.把语句
if X>0 ∨ Y<0
then while X>0 do X:=A*3 else Y:=B+3;
翻译成四元式序列。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i
(1) 给出句型 (i+i)*i+i的最左推导及画出语法树；
(2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。 13.设文法G（S）： S→T | S∨T T→U |T∧U U→i |-U
（1）计算FIRSTVT 和LASTVT； （2）构造优先关系表。
第14页共6页
答案：(1)消除左递，文法变为G’[S]：
S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε
此文法无左公共左因子。
(2)构造相应的FIRST和FOLLOW集合： FIRST(S)={a, ^, (}， FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ，FOLLOW(T)={}} FIRST(T’)={,, ε} ，FOLLOW(F)={)} (3)构造预测分析表： a ^ ( S T T? S→a T→ST? S→^ T→ST? S→(T)' T→ST? ) T?→ε , T?→,ST? # 2. (1) C→if E then
(1)
S→CS (2)
C→if E then {BACK(E.TC, NXQ); C.chain:=E.FC}
(1) (1)
S→CS{S.chain:=MERG(C.Chain, S. Chain)} 3. (1) FIRSTVT(S)={a, ( } FIRSTVT(T)={+, aa, (} LASTVT(S)={a, ) }
LASTVT(T)={+, a, )}
(2) a + ( a .> + <. .> <. ( <. <. <. ) .> .> (1)(2) 4. (1) F→for i:=E to E do (1)
S→FS
(1)(2)
(2) F→for i:=E to E do
(1)
{GEN(:=, E.place, _, entry(i)); F.place:=entry(i); LIMIT:=Newtemp;
(2)
GEN(:=, E.place, _, LIMIT); Q:=NXQ; F.QUAD:=q;
GEN(j≤, entry(i), LIMIT, q+2) F.chain:=NXQ; GEN(j, _, _, 0)}
(1)
S→FS
(1)
{BACKPATCH(S.chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, _, _, F.QUAD); S.chain:=F.chain }
5. (1) (j<, a, ‘10’, (3))
第15页共6页
) .> .> =. >.