《编译原理》复习题
I4: S’→ aS? S a I0: S’→ ?S S→ ?aS S→ ?bS S→ ?a b I2: S→ a?S S→ ?aS S→ ?bS S→ ?a S→ a? a S I1: S’→ S? b a I5: S’→ bS? I3: S→ b?S S→ ?aS S→ ?bS S→ ?a S b （2）在状态I2存在“移近-归约”冲突，因此该文法不是LR(0)文法。
计算S的FOLLOW集合： FOLLOW(S)= {#}
I2中的冲突用FOLLOW集合可以解决，所以该文法是SLR(1)文法。 构造SLR(1)分析表如下：
状态 0 1 2 3 4 5
29．将下图所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。其中，X为初态，Y为终态。
ACTION a s2 s2 s2 b s3 s3 s3 # acc r3 r1 r2 GOTO S 1 4 5 29
《编译原理》复习题
b2bab3b4baYaaX1??a?
【解】 用子集法将NFA确定化，如图所示。
IIaIbSab{X}{1}{3}012{1}{2,3,Y}{3,Y}134{3}—{3,4}重新命名2—5{2,3,Y}{2,3,Y}{2,3,4,Y}336{3,Y}{2,3,Y]{3,4}435{3,4}{3,4}{3,4,Y}557{2,3,4,Y}{2,3,4,Y}{2,3,4,Y}666{3,4,Y}{2,3,4,Y}{3,4,Y}767确定化的DFA如下图所示：
a3aaba1ba604bb2bab5b7ab30．
对正规式(a|b)*abb构造其等价的NFA。 【解】
30
《编译原理》复习题
31． 下面的文法产生0和1的串，即二进制的正整数，请给出决定每个二进制数的值（十进制形式）的语法制导定义。
【解】定义值属性为.val，翻译方案如下： B ? B1 0 { B.val = B1.val ? 2 } B ? B1 1 { B.val = B1.val ? 2 + 1 } B ? 1 { B.val = 1 }
B ? 0 { B.val = 0 }
32．把算术表达式?(a + b) ? (c + d) + (e+ f) 翻译成等价的四元式序列（序号从0开始）。 【解】
0（+，a, b ,T1）
1（uminus，T1，-，T2） 2（+，c, d , T3） 3（*，T2，T3，T4） 4（+，e，f，T5） 5（+，T4，T5，T6）
33．设有文法G[S]:
S→a|（T）|? T→T,S|S
试给出句子(a,a,a)的最左推导。 【解】(1) (a,a,a)的最左推导
S=>(T) =>(T,S) =>( T,S,S) =>( S,S,S) =>(a,S,S) =>(a,a,S) =>(a,a,a)
34．已知文法Ｇ： S → ( L | a L → S , L | )
判断是不是LL（1）文法，如果是请构造文法 Ｇ 的预测分析表，如果不是请说明理由。【解】
1）求各非终结符的 FISRT 集和 FOLLOW 集： = { (, a ) FIRST(L) = { a }? FIRST(S) = { (, ), a } FOLLOW(S) = {, # }
FOLLOW(L) = FOLLOW(S) ={ , # } FIRST(( L)∩{a}=Φ FIRST(S , L)∩{)}=Φ 所以是LL（1）文法
31
《编译原理》复习题
2）预测分析表： S L
35．文法
S ? A a | b A c | d c | b d a A ? d
构造识别活前缀的DFA。请根据这个DFA来判断该文法是不是SLR(1)文法并说明理由。 【解】 S’ ? S . S’ ? .S S
I1 S ? .A a S ? .b A c A a S ? A .a S ? A a . S ? .d c I2 I5 S ? .b d a A ? .d c S ? b A .c S ? b A c . A S ? b .A c b I0 I6 I9 S ? b .d a A ? .d d S ? b d .a I3 S ? b d a . a d A ? d . I10 S ? d .c I7 A ? d . c S ? d c . I4 I8 ( S→ ( L L→ S , L a S→ a L→ S , L , } L → ) # Follow(S)={#}
Follow(A)={a,c}
I4存在冲突且Follow(A)∩{c}={ c} I7存在冲突且Follow(A)∩{a}={ a} 所以不是SLR(1)文法
36．将下图所示的确定有限自动机(DFA)最小化。其中，X为初态，Y为终态。
aaXb21ba3abYb
【解】 先划分为终态集{Y}和非终态集I={X,1,2,3}
X面对输入符号b时下一状态属于I，而1,2,3面对输入符号b时下一状态属于{Y}，故划分为{X}、{1,2,3} 非终态2和非终态3面对输入符号a的下一状态相同，而1不同，即最简状态{X}、{1}、{2，3}、{Y}。按顺序重新命名为0、1、2、3，则得到最简DFA，
32