文法 G[S]没有两个非终结符相邻的情况，且其优先表中任一对终结符之间最多满足?、?、 三种关系中的
一种，因此是 G[S]算符优先文法。（2 分）
可以不考虑终结符“#”。
a ∧ ( ) , # A ? ? ? ∧ ? ? ? ( ? ? ? ? ? ) ? , ? ? ? ? ? ? # ? ? ? ?
或者
（3）优先函数。可以不考虑终结符“#”。每错一个扣 0.5 分，全错或不写不得分，扣完为止，共 5 分。
a ∧ ( ) , # 2 f 6 6 2 6 6 5 g 7 7 7 2 2 或者
a ∧ ( ) , 4 f 4 4 2 4 2 g 5 5 5 3
三、 填空题（每空 2 分，共 20 分） 1 目标程序 （target code） 语法分析（syntax analyzer） optimizer） manager）
代码产生器（code generator）
代码优化器（code
符号表管理（symbol table
2 继承属性（inherited attribute）
3 局部优化（local optimization）
4 四元式（quatriple）
5 E+ * ( ) id
四、 单项选择题（每题 2 分，共 10 分）
1.B 2.D 3.B 4.D 5.C 五、
解答题（共 70 分）
mm
1．（1） L(G)={01|M≥1} 共 2 分，≥写成＞扣 1 分 （2） S=>0S1=>00S11=>000111，共 3 分， =>写成->扣 1 分 （3） 共 3 分，错处扣 0.5 分，扣完为止
2.（1）空白表格也可以填写“错误”字样,共 4 分，错一个扣 0.5 分，扣完为止
a b c $(#) S S→aBc S→bAB A→b A A→aAb B B→b B→ε B→ε （2）共 6 分，其中判断“baabbb 是该文法句子”为 2 分，其他错一个扣 0.5 分，扣完为止
符号栈 输入串 规则 $S $BAb $BA $BbAa $BbA $BbbAa $BbbA $Bbbb $Bbb $Bb $b $ baabbb$ baabbb$ aabbb$ aabbb$ abbb$ abbb$ bbb$ bbb$ bb$ b$ $ $ S→bAB A→aAb A→aAb A→b B→ε success 3.(1) 共 6 分，其中判断“该文法为算符优先文法”为 2 分，其他错一个扣 0.5 分，扣完为止
+ * i < + > < > * > > < i > (2) 共 4 分，错一个扣 0.5 分，扣完为止
+ * i 4 f 2 4 3 g 1 5
4．（1）34242421 ，共 4 分，错一个扣 0.5 分 （2）共 4 分，错一个扣 0.5 分，扣完为止
stack Input string action $ $b $b( $b(( b(((aa)a)a)b$ (((aa)a)a)b$ ((aa)a)a)b$abbb$ (aa)a)a)b$bbb$ shift shift shift $b((( $b(((a $b(((A $b(((Aa $ b(((Aa) $ b(((B $b((A $b((Aa $b((Aa) $b（（B $b(A $b(Aa $b(Aa) $b(B $bA $bAb $S $s$ aa)a)a)b$bb$ a)a)a)b$$ a)a)a)b$ )a)a)b$ a)a)b$ a)a)b$ a)a)b$ )a)b$ a)b$ a)b$ a)b$ )b$ b$ b$ b$ $ $ shift shift reduce, A→a shift shift reduce, B→Aa） reduce, A→(B shift shift reduce, B→Aa） reduce, A→(B shift shift reduce, B→Aa） reduce, A→(B shift reduce, S→bAb accept
5． 共 12 分，其中带注释的分析树、三地址码序列和四元式序列分别为 4 分，错一个序列扣 0.5 分，而
错某点（某项）少于或等于 5 个扣 0.5 分 带注释语法树(略) 三地址码序列 M1: if (x>y) goto M2
goto M4
M2: if (a=b) goto M3
goto M1 M3: t1=2*y
t2=t1+a x=t2 goto M1 M4:
6．共 8 分，错一个扣 0.5 分，扣完为止
LD R1,0 ST S,R1
四元式序列 100 (j>, x,y,102) 101 (j,-,-,108) 102 (j=,a,b,104) 103 (j,-,-,100) 104 (*,2,y,t1) 105 (+,t1,a,t2) 106 (=,t2,-,x) 107 (j,-,-,100) 108 (-,-,-,-)
ST I,R1 L1: LD R1,X
SUB R1,R1,Y (OR SUB R1,Y) BGTZ R1,L2
LD R2,a(R1)
ADD R2,R2,S (OR ADD R2,S) ST Z,R2
LD R1,I (从这开始，下面的语句中的 R1 也可以全部变成 R2) ADD R1,R1,1 (OR INC R1)
ST I,R1 BR L1
L2:
7． 共 6 分，基本块划分和流图各为 3 分，错一处扣 1 分，扣完为止
read
c B1 A=0
B=1 L4: A=A+B
If B>C goto L2 (OR B4) B=B+1
Goto L4 (OR B2)
B2
B3
B4 L2: write A
8. （1）共 4 分，错一项扣 1 分，扣完为止（2）共 4 分，错一项扣 1 分，扣完为止 t1=b*c
t2=b*d t3=t1-t2