L,M n9 + G n7 * F,J n6 + n4 D,H n5 E,I + K n8 15 3 B n1 A n2 n3 C * 若只有L活跃，则代码为
D:=A+C
E:=A*C F:=D+E L:=F+15
五、将下图DFA最小化，并写出最小化后DFA的正规式。（10分） 解：P0=({6,7},{1,2,3,4,5})
P0=({6,7},{1,2}，{3,4,5}) 输入b进入不同状态。
P0=({6,7},{1,2}，{3,4},{5}) 3，4对d有定义，5没有定义 最小化DFA如下： b c b
a b
1 3 6 d 5 a 正规式为：b*a(c|da)*bb*
评分标准：划分状态集过程给3分，图对得5分，图部分对根据对的多少给2-4分，正规上式对给2分。
六、对下面的文法进行改写，并判断改写后是否是LL（1）文法。（15分）
S ?Aa|b A ?SB B ?ab
【解法1】 first(S)={b} first(A)={b} first(B)={a} follow(S)={#,a} follow(A)={a} follow(B)={a}
select(S?AS)=first(AS)={b} select(S?b)=first(b)={b} select(S?AS)∩select(S?b)={b}≠φ 所以该文法不是LL（1）文法
改写为： S ?Aa|b S ?SBa|b
A ?SB A ?SB B ?ab B ?ab
消除左递归： S ?bS’ 化简得： S ?b S’
S ?Ba S’|ε S’ ?Ba S’|ε A ?SB (多余) B ?ab B ?ab
first(S)={b} first(S’)={a,ε} first(B)={a} follow(S)={#} follow(S’)={#} follow(B)={a}
select(S?bS’)=first(bS’) ={b} select(S’?BaS’)=first(BaS’)={a} select(S’?ε)=first(ε)Ufollow(S’)={#, ε}
select(S’?BaS’)∩select(S’?ε)=φ
所以改写后是LL(1)文法。
评分标准：改写前判断LL（1）全对4分，改写正确4分，改写后判断LL（1）正确得6分，最后结论1分。
【解法2】 first(S)={b} first(A)={b} first(B)={a} follow(S)={#,a} follow(A)={a} follow(B)={a}
select(S?AS)=first(AS)={b} select(S?b)=first(b)={b} select(S?AS)∩select(S?b)={b}≠φ 所以该文法不是LL（1）文法
用S的产生式右部代替A的产生式右部的S得： S→Aa|b A→AaB|bB B→ab 消除左递归后文法变为：
0) S→A a 1) S→b 2) A→b B N
3) N→a B N 4) N→ε 5) B→a b 非终结符 FIRST集 FOLLOW集 S {b} {#} A {b} {a} B {a} {a} N {a,ε} {a}
SELECT(S→A a)∩SELECT(S→b) ={ b }∩ { b }={ b }≠φ SELECT(N→a B N)∩SELECT(N→ε) ={ a }∩ { a }={ a }≠φ 所以文法不是LL(1)的。
评分标准：改写前判断LL（1）全对4分，改写正确4分，改写后判断LL（1）正确得6分，最后结论1分。 七、已知文法:
S?S；G|G G?G（T）|H H?a|(S)
7 / 11
T?T+S|S
求句型#a;(T+S);H;(S)#短语、句柄、素短语、最左素短语（12分） 解：语法图见下图 短语有：
a 相对非终结符 H、G 短语 T+S 相对非终结符 T短语 H 相对非终结符 G短语 (S) 相对非终结符 H、G短语 a(T+S) 相对非终结符 G短语 a(T+S);H 相对非终结符 S短语 a(T+S);H;(S) 相对非终结符 S短语 句柄是 a
素短语 a，T+S，（S） 最左素短语 a
S S S ； ； G G H G G （ T ） H （ S ） H T + S a 评分标准：语法图正确4分，短语正确5分，句柄正确1分，素短语正确1分，最左素短语正确1分。
八、1、给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。（5分）
G[S]为： (1) E ?E+T (2) E ?T (3) T ?T*F (4) T ?F (5) F ?(E) (6) F ?a
解：
I0： S’??E ， # E ??E+T ， #,+ E ??T ， #,+ T ??T*F ， #,+,* T ??F ， #,+,* F ?? (E) ， #,+,* F ??a ， #,+,* 评分标准：前4条项目，每条0.5分，后面3条下面。每条1分
2、文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。（10分）
G[M]: 1) M →VbA 2) V →d 3) V →ε 4) A →a 5) A →Aba 6) A →ε 解：对串dbba#的分析过程如下表
对输入串dbba#的分析过程
步骤 1 2 3 4 5 6 7 8 9 状态栈 0 03 02 024 0246 02467 024678 0246 01 文法符号栈 剩余输入符号 # #d #V #Vb #VbA #VbAb #VbAba #VbA #M 动作 移进 dbba# bba# 用V →d归约 移进 bba# ba# 用A →ε归约 移进 ba# 移进 a# # 用A →Aba 归约 # 用M →VbA 归约 接受 # 评分标准：每条1分，格式1分。 3、判断下列各题所示是否为LR类文法，若是请说明是LR(0)，SLR(1)，LALR(1)或LR(1)的哪一种，并构造相应分析表。（15分）
S?aAd?eBd?aBr?eAr A?a B?a
解：LR(0)项目集规范族如图：
9 / 11
I1： I4： S I0： S’?·S S?·aAd S?·eBd S?·aBr S?·eAr S’?S· I2： A B S?aA·d I5： S?aB·r a S?a·Ad S?a·Br A?·a B?·a I3： S?e·Bd S?e·Ar A?·a B?·a a I6： A?a· B?a· e
在状态I6中有“规约-规约”冲突，且Follow(A)=follow(B)={d,r}故不是LR(0)和SLR(1)。
文法LR(1)项目集规范族如下：
I4： I1： S?aA·d ,# S’?S· ，# I2： d I10： S?aAd· ,# S I0： S’?·S ，# S?·aAd ，# S?·eBd ，# S?·aBr ，# S?·eAr ，# A B I5： S?aB·r ,# I6： A?a· ,d r I11： S?aBr· ,# a S?a·Ad ，# S?a·Br ，# A?·a ，d a a B?a· ,r I7： A?a· ,r B?a· ,d e B?·a ,r I3： S?e·Bd ,# S?e·Ar ,# A?·a ,r B?·a ,d B A I8： S?eB·d ,# I9： S?eA·r ,# d I12： S?eBd· ,# r I13： S?eAr· ,#
在状态I6、I7中有“规约-规约”冲突，但归依项目的向前搜索符集不相交，故文法是LR(1)。
I6，I7是同心集，若合并，则合并后的状态I6，I7有项目：
A?a· ,r/d B?a· ,d/r
向前搜索符集相交，故文法不是LALR(1)。 因此，本文法是LR(1)文法。
评分标准：LR（0）和SLR（1）的判断正确给4分，LR（0）和SLR（1）的结论1分，LR(1)项目集规范族正确的给6分，判断LALR（1）同心集正确给2分，LALR（1）结论1分，LR（1）结论1分。
11 / 11
编译原理期末考试试卷及复习资料
