编译原理 3章

第三章 1、L(G[S])={ abc }

2、L(G[N])={ n位整数或空字符串 | n>0 }

3、G[E]：E—>E+D | E-D | D

D—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

4、L(G[Z])={ anbn | n>0 }

5、(1) 考虑不包括“0”的情况

G[S]：S—>0S | ABC | 2 | 4| 6 | 8

A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 B—>AB | 0B | ε

C—>0 | 2 | 4 | 6 | 8

考虑包括“0”的情况：

G[S]：S—>AB | C

B—>AB | C A—>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

C—>0 | 2 | 4 | 6 | 8

(2)方法1：

G[S]：S—> ABC | 2 | 4 | 6 | 8

A—>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 B—>AB | 0B | ε

C—>0 | 2 | 4 | 6 | 8

方法2： G[S]：S—>AB | C

B—> AB | 0B | C | 0 A—> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

C—>2 | 4 | 6 | 8

6、设为E，为T，为F，注：推导过程不能省略，以下均为最

左推导 (1) E => T => F => i

(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i

(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I

7、

*

+

i i i + i *

i i

8、是有二义性的，因为句子abc有两棵语法树（或称有两个最左推导或有两个最右

第三章 习题解答

6．每个表达式的推导及语法树分别如下：

(1)

=>

=>

=> i

(2)

=>

=>

=>()

=>()

=>()

=>(i)

(3)

=>

=>*

=>*

=>i*

=>i*i

(4)

=> +

=> +

=> *+

=> *+

=> i*+

=> i*i+

=> i*i+

=> i*i+i

(5)

=> +

=> +

=> +

=> i+

=> i+

=>i+

=>i+(+)

=> i+(+) => i+(+)

=> i+(i+)

=> i+(i+)

=>i+(i+i)

(6)

=> +

=> +

=> +

=> i+

=> i+*

=> i+*

=> i+i*

=> i+i*i

i()i*ii图（1）图（2）图（3） ()+*iii+i+ii图（4）图（5）

+i图（6）*ii

11．根据文法G给定的规则，从文法的开始符E出发可推导出E+T*F，推导过程如下：

E => E+T => E+T*F ，所以E+T*F是该文法的一个句型。由右图的语法树也可以看出，E+T*F是该文法的一个句型。

这个句型的所有短语为：E+T*F, T*F

直接短语为：T*F

句柄为：T*F

13． EE + TT * F(1)最左推导：S=>ABS

=>a1BS

=> a1SBBS

=> a1BBS

=> a1b1BS

=> a1b1b2S

=> a1b1b2Aa3

=> a1b1b2a2a3

最右推导：S=>ABS

=> ABAa3

=> ABa2a3

=> ASBBa2a3

=> ASBb2a2a3

=> ASb1b2a2a3

=> Ab1b2a2a3

=> a1b1b2a2a3

(2)该文法产生式集合P可能有如下规则：S→ABS|Aa|ε

编译原理答案(前三章) 第 1 章 引论

第 1 题

解释下列术语：

答案：

（1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语

言，则此翻译程序称为编译程序。

（2） 源程序：源语言编写的程序称为源程序。

（3） 目标程序：目标语言书写的程序称为目标程序。

（4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与

目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶

段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符

号表管理等工作。

（5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，

即目标代码生成，以及相关出错处理和符号表操作。

（6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第 2 题

一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程

序的总体结构图。

答案：

一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语

义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和

错误处理程序。其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表

中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式

的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

3.3.2, 3.3.6, 3.3.7, 3.3.8, 3.3.9,

3.6.3, 3.6.4, 3.6.5

3.7.1, 3.7.2, 3.7.3

3.8.1, 3.8.2

3.9.3

3.3.2 描述下列正则表达式代表的语言。

a) a(a|b)*a

b) ((ε|a)b*)*

c) (a|b)*a(a|b)(a|b)

d) a*ba*ba*ba*

e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*

答案 (a) 由a开头并结尾的由a和b构成的字符串

(b) 由a和b构成的字符串

(c) 倒数第三位为a的由a和b构成的字符串

(d) 仅含3个b的由a和b构成的字符串

(e) 含有偶数个a和偶数个b的由a和b构成的字符串

注意：请准确描述语言的性质而不是列举满足正则表达式的串 3.3.6 写出满足下列定义的字符

a) The first ten letters in either upper or lower case

b) The lowercase consonants

c) The “digits” in a hexadecimal number

d) The characters that can appear at the end of a legitimate English

sentence

答案

(a) a-jA-J

(b) a-j

(c) 0-9a-f

(d) .?!

3.3.7 写出匹配字符串 “\ 的正则表达式

答案：

\”\\

《编译原理》（龙书）第三章答案

3.6.3 对于图3.29表示的NFA,列出aabb的所有路径。这个NFA能否接受aabb?

答案：

aabb的所有路径

01223 00111 012000 00000 01222 00011 00123

存在路径1223和0123所以能接受aabb

3.6.4 对于图3.30表示的NFA,列出aabb的所有路径。这个NFA能否接受aabb?