《编译原理》复习题

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