编译原理复习例题

编译原理复习例题

一选择题

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

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

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

[A]递归 [B]右递归 [C]2型 [D]含有公共左因子的 4．文法E→E+E|E*E|i的句子i*i+i*i有c棵不同的语法树。 [A] 1 [B] 3 [C] 5 [D] 7 5．文法S→aaS|abc 定义的语言是c。 [A]{a2kbc|k>0} [C]{a2k-1bc|k>0}

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

6．若B为非终结符，则 A→?.B?为d。

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

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

[C]等价变换规则 [D]语义规则

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

[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的句柄是 T 。 3．最右推导的逆过程称为最左规约，也称为规范推导。 4．符号表的每一项是由名字栏和信息栏两个栏目组成。在目标代码生成阶段，符号表是内存分配的依据。

三判断题（认为正确的填“T”，错的填“F”）

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

【 F 】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型）。 解： G: S→AB|A A→aAb|ab

- 2 -

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 -+013 123 1 1 3 12 +123 123 13 - 3 -

+13 123 2 +

-+ a 0 b a 1 + a

（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，使其语言是

L(G)={ ambnc2n | m>=0,n>0 } 并证明文法是LL(1)。

- 4 -

b b + 4

解：文法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 →aTS’ ε, N ε, P ε, P OK （递归下降子程序，略）

S a b P Q c S = a <> < = b = < <> > > P < = Q =< c > = = > 由于矩阵中有元素存在多种优先关系，故不是简单优先文法。

13．考虑文法 G: S→AS|b

A→SA|a

（1）构造文法的可归前缀图（活前缀的DFA）； （2）判断文法是否是LR(0)文法，并说明理由。 解：（1）可归前缀图

I1:S’?S. A?S.A A?.SA A?.a S?.AS SSI5:A?S.A A?.SA A?.a S?.AS SAbAS?.b a S?.b aaI0:S’?.S S?.AS S?.b A?.SA A?.a I2:A?a. bbaI7:A?SA. S?A.S S?.AS S?.b A?.SA A?.a SAAI3:S?b. ababSbAI4:S?A.S S?.AS AI6:S?AS. A?S.A A?.SA A?.a S?.AS S?.b S?.b A?.SA A?.a S

（2）因为存在冲突，所以不是LR(0)文法。

14．文法G及其LR分析表如下，请给出对串dada#的分析过程。

G: S → VdB ①

V → e ② V → ε ③ B → a ④ B → Bda ⑤ B → ε ⑥

- 6 -

状态 0 1 2 3 4 5 6 7 8 ACTION d S4 r2 r6 r4 S7 r5 e a S8 # r4 r1 r5 S 1 r3 S3 GOTO B 6 V 2 acc S5 r6 解：对输入串dada#的分析过程 步骤 1 2 3 4 5 6 7 8 9 状态栈 0 02 024 0245 0246 02467 024678 0246 01 符号栈 剩余输入符号 # #V #Vd #Vda #VdB #VdBd #VdBda #VdB #S dada# dada# ada# da# da# a# # # # 动作 用V →ε归约 移进 移进 用B →a归约 移进 移进 用B →Bda 归约 用S →VdB 归约 接受 15．对传值、传地址和传名3种参数传递方法分别写出下列

程序的输出：

void p(int x, int y, int z) {

y *= 3; z += x; }

void main() {

int a=5, b=2; p(a*b,a,a);

printf(“%d\\n”, a); }

这些参数传递机制如何实现？ 解：（1）传值 5；（2）传地址 25；（3）传名 45 （参数传递机制，略）

16．将下面程序划分为基本块，并画出其程序流图。

b := 1 b := 2

- 7 -

if w <= x goto L2 e := b goto L2 L1:goto L3 L2:c := 3 b := 4 c := 6

L3:if y <= z goto L4 halt

L4:g := g + 1 h := 8 goto L1

解：（1）基本块： b := 1 b := 2 if w <= x goto L2 e := b goto L2 L1: goto L3 L2: c := 3 b := 4 c := 6 L3: if y <= z goto L4 halt L4: g := g + 1 h := 8 goto L1

（2）程序流图

1 5 7

（1） （2） （3）

2 4

6 （4）

（5） （6） 3

（7）

- 8 -

本文来源：https://www.bwwdw.com/article/guzt.html