编译原理复习题及答案

B.最左推导和最右推导对应的语法树可能相同 C.最左推导和最右推导必定相同

D.可能存在两个不同的最左推导，但他们对应的语法树相同 66． (B)不是DFA的成分

A.有穷字母表

B.多个初始状态的集合

C.多个终态的集合

D.转换函数

67． 与逆波兰式(后缀表达式)ab+c*d+对应的中缀表达式是(B)

A. a+b+c*d

B. (a+b)* c+d

C. (a+b)* (c+d)

D. a+b*c+d

68． 后缀式abc?+?d+可用表达式(B)来表示。

A．(? (a+b)?c)+d D．(a?(?b+c))+d

B．?(a+(b?c))+d

C．? (a?(b+c))+d

69． 表达式A*(B-C*(C/D))的后缀式为(B)。

A．ABC-CD/**

B．ABCCD/*-*

C．ABC-*CD/*

D．以上都不对

70． (D)不是NFA的成分。

A. 有穷字母表 二、 问答

1． 将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。 G[S]： S→bSAe | bA A→Ab | d 答：

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

A' →bA' | ε

2． 将文法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。 G[S]： S→SAe|Ae A→dAbA|dA|d 答：

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

B. 初始状态集合

C. 终止状态集合

D. 有限状态集合

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集

非终结符 S H M A FIRST集 {a} {a ，d}..... {a ，e ，ε} {a ，e}..... FOLLOW集 {# }... {# }... {d ，b} {b}.... 由于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)分析表如下表。

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

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

非终结符 S D T H {a} {a，ε} {b，d，ε} {d，ε} FIRST集 FOLLOW集 {#，b，d，e}. {#，b，d，e } {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)分析表如下表：

S D T H a →aD. →STe e →ε →H. →ε b →ε →bH d →ε →H. →d. # →ε 6． 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。

S→aD D→STe|ε T→bM M→bH H→M|ε 答：

文法的 FIRST集和FOLLOW集

非终结符 S D T M H FIRST集 {a}..... {a ，ε} {b}..... {b}..... {b ，ε} FOLLOW集 {# ，b} {# ，b} {e}.... {e}.... {e}.... 由于predict（D→STe）∩predict（D→ε）={a}∩{# ，b}= predict（H→M）∩predict（H→ε）={ b }∩{ e }= 所以该文法是LL(1)文法，LL(1)分析表如下表：

S D T M H a →aD. →STe e →ε b →ε →bM →bH →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