编译原理(清华大学 - 张素琴)复习例题(2)

编译原理复习例题(有些内容没有覆盖,比如优化、SLR(1)、LR(1)、LALR(1)

等。但要求至少要按照作业题的范围复习。)

一 选择题

1.编译的各阶段工作都涉及 。

[A]词法分析 [B]表格管理 [C]语法分析 [D]语义分析 2. 型文法也称为正规文法。

[A] 0 [B] 1 [C] 2 [D] 3 3. 文法不是LL(1)的。

[A]递归 [B]右递归 [C]2型 [D]含有公共左因子的 4.文法E→E+E|E*E|i的句子i*i+i*i有 棵不同的语法树。

[A] 1 [B] 3 [C] 5 [D] 7 5.文法 S→aaS|abc 定义的语言是 。 [A]{a2kbc|k>0} [C]{a2k-1bc|k>0}

[B]{akbc|k>0} [D]{akakbc|k>0}

6.若B为非终结符,则 A→?.B? 为 。

[A]移进项目 [B]归约项目 [C]接受项目 [D]待约项目 7.同心集合并可能会产生新的 冲突。

[A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约 8.代码优化时所依据的是 。 [A]语法规则 [B]词法规则 [C]等价变换规则 [D]语义规则

9.表达式a-(-b)*c的逆波兰表示(@为单目减)为 。 [A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-* 10.过程的DISPLAY表是用于存取过程的 。

[A]非局部变量 [B]嵌套层次 [C]返回地址 [D]入口地址

- 1 -

二 填空题

1.词法分析阶段的任务式从左到右扫描 字符流 ,从而逐个识别 一个个的单词 。

2.对于文法G[E]:E→T|E+T T→F|T*F F→P^F|P P→(E)|i,句型T+T*F+i的句柄是 。 3.最右推导的逆过程称为 规范归约 ,也称为 最

左归约 。

4.符号表的每一项是由名字栏和 两个栏目组成。在目标代码生成阶段,符号表是 的依据。

三 判断题(认为正确的填“T”,错的填“F”)

【 】1.同心集的合并有可能产生“归约/归约”冲突。 【 】2.一个文法所有句子的集合构成该文法定义的语言。 【 】3.非终结符可以有综合属性,但不能有继承属性。 【 】4.逆波兰表示法表示表达式时无需使用括号。 【 】5.一个有穷自动机有且只有一个终态。

【 】6.若过程p第k次被调用,则p的DISPLAY表中就有

k+1个元素。

四 解答题

1.给定文法G和句型(T+F)*i+T,

G: E→E+T | T T→T*F | F F→(E) | i (1)画出句型的语法树;

(2)写出句型的全部短语、简单短语和句柄。 解:(略)

2.设有文法G:S→S+S|S*S|i|(S)。

(1)对于输入串i+i*i 给出一个最左推导;

(2)该文法是否是二义性文法?请证明你的结论。 解:(1)i+i*i的最左推导:

S => S+S => i+S => i+S*S => i+i*S => i+i*i

(2)该文法是二义性的。因为对于句子i+i*i可以画出两棵

语法树(语法树略)。

3.给出语言{ambmcn|m≥1,n≥0}的上下文无关文法(2型)。

- 2 -

解: G: S→AB|A A→aAb|ab B→cB|c

4.给出语言{akbmcn|k,m,n≥1}的正规文法(3型)。 解: G: A→aA|aB B→bB|bC C→cC|c

5.将文法G改写成等价的正规文法(3型)。

G: S→dAB A→aA|a B→bB|b 解: G: S→dA A→aA|aB B→bB|b

6.构造一文法产生任意长的a,b串,使得 |a|≤|b|≤2|a|

其中,“|a|”和“|b|”分别表示串中的字符a和b的个数。 解:b的个数在a的个数和其2倍之间,串的结构形如aSBS和

BSaS,其中B为1或2个b。故得文法 G: S→aSBS|BSaS|ε B→b|bb

7.设有字母表{a,b}上的正规式R=(ab|a)*。 (1)构造R的相应有限自动机; 解:

2 - 0 ε a 1 a b ε + 3

(2)构造R的相应确定有限自动机;

解:将(1)所得的非确定有限自动机确定化

ε a b -0 1 2 +3

a b - 3 -

1 1 3 12 -+013 123 +13 123 2 +

-+ a 0 b a 1 + a +123 123 13

(3)构造R的相应最小确定有限自动机;

解:对(2)得到的DFA化简,合并状态0和2 为状态2:

2 -+ b a 1 + a

(4)构造与R等价的正规文法

解:令状态1和2分别对应非终结符B和A

G: A→aB|a|ε

B→aB|bA|a|b|ε 可化简为: G: A→aB|ε B→aB|bA|ε

8.写出如图所示的自动机描述的语言的正规式

+ 2 b - 0 a 1 a a 3 a 解:abb*|abb*aa*b|aaa*b

9.写出在{a,b}上,不以a开头,但以aa结尾的字符串集合的正规式(并构造与之等价的最简DFA)。 解:依题意,“不以a开头”,则必以b开头,又要“以aa结尾”,

故正规式为:b(a|b)*aa

(构造与之等价的最简DFA,此略)

10.写一个LL(1)文法G,使其语言是

- 4 -

b b + 4

L(G)={ ambnc2n | m>=0,n>0 } 并证明文法是LL(1)。 解:文法G(S):S ? aS | E

E ? bE’

E’? Ecc | cc

Select(S ? aS)∩Select (S ? E)= Ф Select(E’? Ecc)∩Select (E’? cc) =Ф 故文法为LL(1)的

11.将文法G改写成等价的LL(1)文法,并构造预测分析表。

G:S→S*aT|aT|*aT T→+aT|+a (编写递归下降子程序)

解:消除左递归后的文法G’: S→aTS’|*aTS’

S’→*aTS’|ε T→+aT|+a

提取左公因子得文法G’’:S→aTS’|*aTS’

S’→*aTS’|ε T→+aT’ T’→T|ε

Select(S→aTS’)={a} Select(S→*aTS’)={*}

Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}

Select(S’→ε)=Follow(s’)={#}

Select(S’→*aTS’)∩Select(S’→ε)= Ф Select(T→+aT’)={+}

Select(T’→T)=First(T) ={+}

Select(T’→ ε)=Follow(T’)={*,#} Select(T’→T)∩Select(T’→ε)= Ф 所以该文法是LL(1)文法。 预测分析表: * + a # S S’Ta, N S’ S’Ta, N T T’ ε, P a #

12.对文法G[S]: S → aSb | P

P → bPc | bQc Q → Qa | a

- 5 -

T’a, N T, P TS’T, N ε, N ε, P ε, P OK (递归下降子程序,略)

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4