编译原理复习题及答案

A→dAbA|dA|d 答：

文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为： S →AeS' S' →AeS'|ε A →dA' A' →AB|ε B →bA |ε

3． 将文法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。 G[S]： S→[A A→B]|AS B→aB|a 答：

文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为： S →[A A →B]A′ A′→SA′|ε B →aB′

B′→B|ε

4． 判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。 S→aH

H→aMd | d M→Ab | ε A→aM | e 答：

首先计算文法的 FIRST集和FOLLOW集如下表。

文法的 FIRST集和FOLLOW集 非终结符 FIRST集 FOLLOW集 S {a}......... {# }... H {# }... {a ，d}..... M {a ，e ，ε} {d ，b} A {b}.... {a ，e}..... 由于predict（H→aMd）∩predict（H→d）={a}∩{d }=

predict（M→Ab）∩predict（M→ε）={a ，e}∩{d ，b }= predict（A→aM）∩predict（A→e）={ a }∩{ e }= 所以该文法是LL(1)文法，LL(1)分析表如下表。 a d b S →aH. H →aMd →d. M →Ab. →ε →ε A →aM. 5． 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。 S→aD D→STe|ε T→bH|H H→d|ε 答：

首先计算文法的 FIRST集和FOLLOW集如下表。 非终结符 FIRST集 FOLLOW集 S {a} {#，b，d，e}. D {a，ε} {#，b，d，e }

e →Ab →e. # T H {b，d，ε} {d，ε} {e} {e} 由于predict（D→STe）∩predict（D→ε）={a}∩{# ，b ，d ，e }= predict（T→bH）∩predict（T→H）={b}∩{e }= predict（H→d）∩predict（H→ε）={ d }∩{ e }= 所以该文法是LL(1)文法，LL(1)分析表如下表： a e b d S →aD. D →STe →ε →ε →ε T →H. →bH →H. H →ε →d.

6． 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。 S→aD D→STe|ε T→bM M→bH H→M|ε 答：

文法的 FIRST集和FOLLOW集 非终结符 FIRST集 FOLLOW集 S {a}..... {# ，b} D {a ，ε} {# ，b} T {b}..... {e}.... M {b}..... {e}.... H {e}.... {b ，ε} 由于predict（D→STe）∩predict（D→ε）={a}∩{# ，b}=

predict（H→M）∩predict（H→ε）={ b }∩{ e }= 所以该文法是LL(1)文法，LL(1)分析表如下表： a e b S →aD. D →STe →ε T →bM M →bH H →ε →M.

7． 某语言的拓广文法G′为： (0) S′→S (1) S → Db|B (2) D → d|ε (3) B → Ba|ε

证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。 答：

# →ε # →ε

拓广文法G'，增加产生式S'→S 在项目集I0中： 有移进项目D →·d 归约项目D →·和B →·

存在移进-归约和归约-归约冲突，所以G不是LR(0)文法。

若产生式排序为： (0) S'→S (1) S → Db (2) S → B (3) D → d (4) D →ε (5) B → Ba (6) B →ε

G′的LR(0)项目集族及识别活前缀的DFA如下图：

由产生式知 Follow(S)={#} Follow(D)= {b} Follow(B)= {a ,#} 在I0中:

Follow(D) ∩{d}={ b} ∩{d}= Follow(B) ∩{d}= { a ,#} ∩{d}=

Follow(D) ∩ Follow(B)= {b}∩{a ,#} = 在I3中:

Follow(S) ∩{a}={#}∩{a}=

所以在I0，I3中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法, 构造的SLR(1)分析表如下表： ACTION GOTO 状态 b d a # S D B 0 r4 S4 r6 r6 1 2 3

1 2 3 4 5 6 S5 r3 S6 r5 acc r2 r1 r5

8． 给出与正规式R＝（ab）*（a|b*）ba等价的NFA。 答：

与正规式R等价的NFA如下图

9． 给出与正规式R＝（(ab)*|b）*（a|(ba)*）a 等价的NFA。 答：

与正规式R等价的NFA如下图

10． 给出与正规式 R＝（aba）*（(ba)*|b）b等价的NFA。 答：

与正规式R等价的NFA如下图

11． 将下图的NFA确定化为DFA。

答：

用子集法确定化如下表 I {X,1,2} {1,2}.. {1,2,3} {1,2,Y} 确定化后如下图：

Ia {1,2}.. {1,2}.. {1,2,Y} {1,2}.. Ib {1,2,3} {1,2,3} {1,2,3} {1,2,3} 状态 X 1 2 3