T→*|+ （1分）
（2）(5分)没考虑#扣0.5分，其它错或少写一个扣0.5分
FIRST(E)={(,i} FIRST(E’)={*,+, ε} FIRST(T)={*,+} FOLLOW(E)={),*,+,#} FOWLLOW(E’)= {),*,+,#} FOLLOW(T)={(,i}
（3）每错一个扣0.5分，全错或不写不得分，扣完为止，共5分 E E’ ( ) i E→iE’ * E’→TEE’ E’ →ε T T→* + E’→TEE’ E’ →ε T→+ # E’ →ε E→(E)E’ E’→ ε 2．（1）规范推导过程如下.写错推导符号扣0.5分,错写或少写一步推导扣0.5分，扣完为止，最左推导扣2分，共4分.
S?S(S)?S(?)?S(S)()?S(?)()?S(S)()()?S(S(S))()()?S(S(?))()()?S(S(S)())()()?S(S(?)())()()?S((?)())()()??(()())()()（1）中加下划线的部分是句柄，标识如（1）.每少写一个句柄扣0.5分，扣完为止，共4分. （3）每少写步扣0.5分，扣完为止，共4分.
S ( S ) ε )
ε S ( S ) ) )
ε ε ．3（1）打印的字符串是：12020（错一个扣0.5分，共3分） （2）归约过程中错一步扣0.5分，扣完为止.（共5分） 4．（1）每少写一步扣0.5分，扣完为止，共5分.
S
while M1.q=100 E1.t=102 do M2.q=102 S1 6 / 15 E1.f=107
do S1.nl=103 S ( S ) ε
S ( S ) ) S ( S ) ε ) S
（2）
y z
c>d x E5.p=y + E6.p=z
(E3.t=102) ε L.p=x := E4.p=T1
（2）少写一个四元式扣0.5分，全错或不写不得分，回填错误扣0.5分，共5分. 四元式序列为：
100(j?,a,b,102)101(j,_,_,107)102(j?,c,d,104)103((j,_,_,106)104(?,y,z,T1)105(:?,T1,_,x)106(j,_,_,100)
5．（1）少写一个扣1分，全错或不写不得分，共5分. FIRSTVT(S)={a,∧,(} FIRSTVT(T)={, a,∧,(} LASTVT(S)={ a,∧,)} LASTVT(T)={ a,∧,), ,}
(2)优先表如下.每错一个扣0.5分，全错或不写不得分，扣完为止，共3分
文法G[S]没有两个非终结符相邻的情况，且其优先表中任一对终结符之间最多满足?、?、 三种关系中的一种，因此是G[S]算符优先文法.（2分） 可以不考虑终结符“#”. A ∧ ( ) , # a ? ? ? ∧ ? ? ? ( ? ? ? ) ? ? ? ?
7 / 15
, ? ? ? ? ? ? # ? ? ?
或者
（3）优先函数.可以不考虑终结符“#”.每错一个扣0.5分，全错或不写不得分，扣完为止，共5分. f g 或者 f g a 4 5 ∧ 4 5 ( 2 5 ) 4 2 , 4 3 a 6 7 ∧ 6 7 ( 2 7 ) 6 2 , 6 5 # 2 2 三、 填空题（每空2分，共20分）
1目标程序 （target code） 语法分析（syntax analyzer） 代码优化器（code optimizer） 代码产生器（code generator） 符号表管理（symbol table manager）
2 继承属性（inherited attribute） 3 局部优化（local optimization） 4 四元式（quatriple）
5 E + * ( ) id
四、 单项选择题（每题2分，共10分） 1.B 2.D 3.B 4.D 5.C 五、 解答题（共70分）
1．（1） L(G)={01|M≥1} 共2分，≥写成＞扣1分
mm
（2） S=>0S1=>00S11=>000111，共3分， =>写成->扣1分 （3） 共3分，错处扣0.5分，扣完为止
2.（1）空白表格也可以填写“错误”字样,共4分，错一个扣0.5分，扣完为止 S A B a S→aBc A→aAb b S→bAB A→b B→b c B→ε $(#) B→ε （2）共6分，其中判断“baabbb是该文法句子”为2分，其他错一个扣0.5分，扣完为止 符号栈 $S $BAb $BA $BbAa $BbA $BbbAa 输入串 baabbb$ baabbb$ aabbb$ aabbb$ abbb$ abbb$
8 / 15
规则 S→bAB A→aAb A→aAb $BbbA $Bbbb $Bbb $Bb $b $ bbb$ bbb$ bb$ b$ $ $ A→b B→ε success 3.(1) 共6分，其中判断“该文法为算符优先文法”为2分，其他错一个扣0.5分，扣完为止 + * i + > > > * < > > i < < (2) 共4分，错一个扣0.5分，扣完为止 f g + 2 1 * 4 3 i 4 5 4．（1）34242421 ，共4分，错一个扣0.5分 （2）共4分，错一个扣0.5分，扣完为止 stack $ $b $b( $b(( $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 Input string b(((aa)a)a)b$ (((aa)a)a)b$ ((aa)a)a)b$abbb$ (aa)a)a)b$bbb$ 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$
9 / 15
action shift shift shift 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） $bA $bAb $S $s$ b$ $ $ reduce, A→(B shift reduce, S→bAb accept 5． 共12分，其中带注释的分析树、三地址码序列和四元式序列分别为4分，错一个序列扣0.5分，而错某点（某项）少于或等于5个扣0.5分 带注释语法树(略)
三地址码序列 四元式序列 M1: if (x>y) goto M2 100 (j>, x,y,102) goto M4 101 (j,-,-,108) M2: if (a=b) goto M3 102 (j=,a,b,104) goto M1 103 (j,-,-,100) M3: t1=2*y 104 (*,2,y,t1) t2=t1+a 105 (+,t1,a,t2) x=t2 106 (=,t2,-,x) goto M1 107 (j,-,-,100) M4: 108 (-,-,-,-) 6．共8分，错一个扣0.5分，扣完为止
LD R1,0 ST S,R1 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分，扣完为止
10 / 15
相关推荐：
loading