编译复习大纲

一、题型与分值（可能会微调）

1、填空题：10题20分

2、判断题：5题10分

3、简答题：4题20分

4、解答题：5题50分

二、考试内容

01、汇编程序、解释程序、编译程序的概念

（记忆）P2-3【小题】

汇编程序：把汇编语言写的源程序翻译成机器语言的目标程序

解释程序：将高级语言写的源程序作为输入数据，但并不产生目标

程序，而是边解释边执行源程序本身的一种程序会话型语言编译程序：是将高级语言写的源程序翻译成目标语言（汇编语言、机器语言）的程序。这种翻译过程称为编译

02、编译过程的八大组成部分的名称

（记忆）P5【小题】

源程序->词法分析程序->语法分析程序->语义分析程序->中间代码生成->

代码优化程序->目标代码生成->目标程序

03、分遍（趟程）的概念及其适用情况

（记忆）P9【小题】

趟程(遍)：从头到尾扫描一遍源程序或等价源程序，并做有关加工处理。

决定趟程的因素

（1）计算机存贮容量大小；

（2）编译程序功能强弱；

（3）源语言繁简；

（4）目标程序优化程度；

（5）设计和实现编译程序时使用工具的先进性

（6）参加人员多少和素质等。

当源语言较繁，编译程序功能很强，目标程序优化度高却计算机存贮容量小时，采用多遍扫描方式

04、系统程序设计语言、自编译的概念（记忆+理解）P10【简答题】

系统程序设计语言：能够编写编译程序或其他系统软件的高级语言。如PASCAL、

C、C++

自编译：如果一种高级语言与之相应的编译程序也能直接用该语言本身写出来, 具有这种性质语言称自编译语言,即自编译,能够编译自身的编译程序称自编译程序。自编译语言书写自身以及其它语言编译程序（系统程序设计语言就是自编译语言）

自编译方法：在A机器上有了某种语言的A代码编译程序，就可以在A机器上运行这种语言编译程序

05、交叉编译的概念（记忆+理解）P11【小题】

交叉编译程序：A 机器上编译程序能产生B 机器的目标代码

06、符号和符号串（掌握）P17-19

【基础，不单独考】

07、产生式、文法、推导（推导的长度）与归约

（理解）P21-23【小题】

文法是规则的有穷集合，形式定义为四元组：

G=(VN, VT, P, Z)

其中：VN是非终结符集合，VT是终结符集合，P代表产生式集，Z∈VN是文法G 开始符号，也称识别符号，它至少要在一条产生式左部出现。文法G通常记为G［Z］推导和归约

定义1设G为一个文法，U∷=u是G中一个规则，x和y是V*上的

符号串，使得v=xUy 与w=xuy 成立，

则称符号串v直接推导出符号串w，或称w直接归约到v，并把w叫做v

直接派生式，记作v w

注意三点：1）v ，w是两个不同符号串

2）有一规则U∷=u

3）直接推导v ? w

若x=y=ε，则v=xUy =U，w=xuy=u

可见v ? w即U ? u 说明一个规则就是一个直接推导

例如〈句子〉直接推导到<主语><谓语>，而<主语><谓语>直接归约

到<句子>。

定义2设u0, u1, u2, … , u n均为V*上符号串，若w是v经过一系列直接

推导得到的，即

v= u0? u1? u2?… ?u n-1?u n =w (n>0) 【原符号串记为0，共推导出其他n

个符号串】则称v推导到w，或称w归约到v，记作

v ?+w

称这个直接推导序列为长度为n的推导。如果v ?+w或者v=w(表示0

步推导)，则记作

v ?*w

称v广义推导到w或称w广义归约到v。

显然，直接推导?的长度为1，推导? +的长度≥1，而广义推导? *

的长度≥0

08、句型、句子、语言（给文法写语言）、BNF（巴科斯范式）P24【小题】

句型：由识别符Z推导而得的符号串（终结符和非终结符）

只有终结符组成

句子（一个正确的源程序是句子）

语言：

语言是句子集合，是V T*一个子集合，即V T中行集合子集。

句子必须由该语言文法识别符推出

09、递归文法的含义（消除文法的左递归P78-79）（掌握）P25【小题或简

答】

递归规则：在规则左部和右部具有相同的非终结符规则

对于一个文法，若有一个规则U∷=…U…，则称直接递归，若有规则U∷=U…，则称直接左递归，若有规则U∷=…U，则称直接右递归。若有推导式U?+…U…，则称间接递归，若有推导式U?+U…，则称间接左递归，若有推导式U?+…U，则称间接右递归。非终结符U称递归非终结符。如果一个文法中至少含有一个递归非终结符，则将此文法称为递归文法。

消除文法的左递归：

1）用重复表示法（扩充的ＢＮＦ表示法）改写语法规则

假定一个文法中有关于非终结符的规则为

Ａ∷＝Ａα｜β

其中α非空，β不以Ａ开头，则等价地改写为

Ａ∷＝β｛α｝

例如，下述直接左递归规则：

Ｅ∷＝Ｅ＋Ｔ｜Ｔ

可改写为

Ｅ∷＝Ｔ｛＋Ｔ｝

2）消除直接左递归（改写法）

对Ａ引入一个新的非终结符Ａ′，将Ａ∷＝Ａα｜β等价写成

Ａ∷＝βＡ

Ａ′∷＝αＡ′｜

由于β不以Ａ开头，α不以Ａ′开头，因此改写后两条规则不是直接

左递归。

就一般而言，关于Ａ的规则具有下面形式：

Ａ∷＝Ａα１｜Ａα２｜…｜Ａαn｜β１｜β２｜…｜βn

这时可改写成如下形式：

Ａ∷＝A(α１｜α２｜…｜αn) ｜β１｜β２｜…｜βn

由消除直接左递归方法，得

Ａ∷＝(β１｜β２｜…｜βn)Ａ

Ａ′∷＝(α１｜α２｜…｜αn)Ａ′｜

3）消除间接左递归

对于间接左递归先将间接左递归变成直接左递归，然后消除直接左递归

4) 消除文法递归的一般算法

要求：文法不含形如Ａ ＋Ａ的推导，也不存在Ａ∷＝ε这样规则

算法思想如下：

①将文法Ｇ的所有非终结符整理成某种顺序Ｕ１，Ｕ２，…Ｕn

②从U1开始消除U1规则的直接左递归

③用左部为U1的所有规则右部替换左部为U2，右部以U1开始的规则中的U1，并消除U2规则的直接左递归。

④用类似的方法把U1，U2的右部替换左部为U3，右部以U1，U2开始的规则中，消除U3规则中的直接左递归。

⑤重复上一步，直到最后把左部为U1，U2，…Un-1的右部带入Un规则中，并消除Un中的直接左递归。

⑥消除多余规则

10、短语、简单短语、句柄、素短语、最左素短语（P109）（掌握）P26【小

题或简答】

短语和简单短语（u可以含有非终结符号，u必是所给句型中的一部分）

定义：设G［Z］是一文法，w=xuy是其中一句型，若有

Z ? *xUy, U∈VN 且U ? +u, u∈V+

则称u是一个相对于非终结符U、句型w的短语。

若Z ? *xUy 且U ? u

则称u是一个相对于非终结符U、句型w的简单短语。

例2.22设有文法G[S]=({S, A, B}, {a, b}, P, S)，其中P为

S∷=AB A∷=Aa | bB B∷=a | Sb

找出句型baSb的全部短语，简单短语，根据句型推导过程有

S ? AB ? bBB ? baB ? baSb

由上可见，下式成立：S ? *baB 且B ? Sb

所以子串Sb是相对于非终结符B，句型baSb的简单短语。

同样有S ? AB ? ASb ? bBSb ? baSb

即S ? *bBSb 且 B ? a

子串a是相对于B，句型baSb的简单短语。

还有S ? *Asb 且 A ? +ba

即子串ba是相对于非终结符A，句型baSb的短语。

对于句型baSb，再没有其它能产生新的短语推导了，所以句型baSb

有短语ba简单短语a和Sb

柄短语（句柄必定是简单短语）

定义：一个句型最左边的简单短语称为该句型的句柄(或柄短语)，而且句柄最左边的符号称句柄的头，句柄最右边的符号称句柄的尾。

如上例句型baSb简单短语为a和Sb ，由于a是

最左简单短语，所以a又是句柄。

最左素短语

所谓句型素短语，是指这样一种短语，它至少包含一个终结符号，且除它自身不再包含其它的素短语。最左边的素短语就称为最左素短语。

在算符优先分析过程中，每次归约的符号串就是当前句型的最左素短语, 它不是规范归约

我们仍然以文法G[E]为例

Ｅ∷＝Ｅ＋Ｔ｜Ｔ

Ｔ∷＝Ｔ*Ｆ｜Ｆ

Ｆ∷＝(Ｅ)｜

考虑文法Ｇ［Ｅ］的句型Ｔ＋Ｔ*Ｆ＋i，从其语法树可看出

T 是相对于非终结符E 的简单短语，也是句柄 T*F 是相对于非终结符T 的简单短语

i 是相对于非终结符F 的简单短语

T+T*F 是相对于非终结符E 的短语

由素短语定义知 T*F 和i 是素短语，T*F 还是最左素短语

T+T*F 不是素短语，因为它包含了素短语T*F ，

T 因为不含终结符也不是素短语

句型最左素短语判断方法

对于算符文法来说，其句型总可以表示成如下形式：

＃Ｎ１a １Ｎ２a ２…Ｎn a n Ｎn ＋1

＃

其中a i 为终结符号，Ｎi 是可有可无的非终结符号。 换句话说，

句型是由n 个终结符号组成，而且每对相邻终结符号之间至多只能出现

一个非终结符(因为是算符文法)。

最左素短语判断定理：

一个算符优先文法，其句型的最左素短语是满足如下条件

a i-1··a j+1

的最左子串Ｎi a i N i+1a i+1j －1a j －1N j a j N

j+1

（最左素短语是每次归约的符号串，即其中的终结符算符优先级比相邻的都高）

例如，刚才讨论文法Ｇ［Ｅ］的句型

＃T ＋Ｔ*Ｆ＋i

＃

若令N 1=T,N 2=T,N 3=F ，a 1=+,a 2=*,a 3=+,a 4=i ，由表4.8

可知

a 1··a 3

所以Ｔ*Ｆ(即N 2a 2N 3)是最左素短语，结论正确。

E E + T E + T T *

F T F i

11、规范推导和规范归约

（理解+记忆）P27【小题】

定义1：在任何一步推导v?w中，都是对符号串v的最左(右)的非终结符进行替换，则称最左(右)推导。

例如：G[S]

S∷=AB A∷=Aa|bB B∷=a|Sb

S?AB?bBB?baB ------ 最左推导

S?AB?ASb?AABb?AAab?AbBab -------最右推导

S?AB?ASb?bBSb?baSb ------ 非左非右推导

定义2：最右推导叫规范推导，即在规范推导过程中，每步直接推导xUy?xuy中，符号串y只含有终结符。如果推导v?+w中每一步直接推导是规范的，则称

推导v?+w为规范推导。

规范句型：由规范推导所得的句型称为规范句型。

规范归约：我们把最左推导的逆过程称最右归约

最右推导的逆过程称最左归约

最左归约也称为规范归约

12、语法树（掌握）P27-28【小题或简答】

（1）语法树形式定义

设有文法G=(VN，VT，P，Z)，满足下列条件的树即为一个语法树

a. 树中每一个结点都有标记，且该标记是VN∪VT中某一符号

b. 树根标记是识别符号

c. 若有一个结点至少有一个后继结点，则该结点标记必为非终结符

d. 若一个标记为U的结点，它有标记依次为X1，X2，X3，…，Xn的

直接后继结点，则U∷=X1X2…Xn必定是G的一条规则。

结论：

a.对于每一个语法树（或者子树）至少对应一个推导（可能是直接推导，可能是n步推导）

b.对于每个推导必存在有一个语法树，语法树中每个分支对应于一个直接推导。

c.不同推导可能有相同的语法树。

如：S ? AB ? bBB ? baB ? baSb

S ? AB ? ASb ? bBSb ? baSb

同一句型的两个不同的推导对应的语法树却是相同的。

树的末端结点标记从左到右连接起来就是要推导的句型或句子

3）语法树的作用

1）利用语法树可以构造文法的句型；（前面我们已经讲了句型baSb 的语法树构造过程）

2）根据语法树可以确定短语、简单短语和句柄；树末端结点的符号串是相对于子树根的短语，分支结点的符号串是相对于分支名字的简单短语(只有父子两代) ，最左简单子树的末端结点的符号串是句柄。从右图语法树可直观看出：ba 是句型baSb ，相对于A 的短语，Sb 是句型baSb 相对于B 的简单短语，a 是句型baSb 相对于B 的简单短语，也是句柄。

3）当给定文法G 后，我们可借助于推导语法树的逆过程把句型推导构造出来 （见下页举例）

语法树构造推导:不断地重复构造最后直接推导，剪去相应分支直到无分支可剪过程。

对于每个语法树至少存在一个推导。

最左归约，即每次剪去最左末端分支，实际上每次归约是句柄。如果改变剪去相

应分支顺序便将得到不同推导。

13、文法的二义性（会证明）

（掌握）P29【小题或简答】 定义：如果一个文法中某个句型对应两棵不同的语法树，则称这个文法是二义性

的。也就是说，若一个文法中的某句型对应两个不同的最左推导或最右推

导，则这个文法是二义性的。

例如：文法G[E]

E ∷=E+E|E*E|(E)|i

符号串i+i*i 是L(G)中一个句子，有两个不同的最右推导

S A B b B S b a

E?E+E?E+E*E?E+E*i?E+i*i?i+i*i (1)

E?E*E?E*i?E+E*i?E+i*i?i+i*i (2)

对应两棵不同的语法树。

推导序列(1)和(2)分别对应两棵不同的语法树，所以文法G[E]是二义性的。

若将+，*看成算术运算符，则出现对表达式i+i*i 是先做+还是先做*的不确定问题。

文法二义性消除

由于二义性文法的存在，使得语法分析时存在许多麻烦，为此，人们可以具体采用两种途径来解决文法二义性问题。

（1）在语义上加些限制，或者说加一些语法非形式规定。

例如对于上例中G[E]文法，我们可以通过规定运算符之间的优先级来避免文

法的二义性。又例如对于条件语句文法G[C]，我们可以规定else永远与最靠

近它前面一个尚未匹配then配对，这样就避免文法二义性。

（2）对原二义性文法加上一定条件，将其改造成一个等价的无二义性文法。

说明：

（1）文法的二义性是不可判定的，要证明一个文法是否二义性，即找一个句型能否产生两个不同的语法树

（2）文法的二义性和语言的二义性是两个不同的概念。

产生该语言的文法都是二义性文法，称该语言为二义性语言，也称先

天二义性。至少有一个非二义文法产生该语言称此语言为非二义性语言14、文法和语言的分类、文法与自动机的对应

（掌握）P33-35【小题或简答】

1）0型文法（短语结构文法）

若在文法G中，P中规则具有如下形式：

α∷=β 其中α∈V+，且至少含一个非终结符，β∈Ｖ*

特点：产生式的左部可以是一个符号串，右部可以为空

2）1型文法（上下文有关文法）

若在文法G中，P中规则具有如下形式：

αAβ∷=αwβ，其中α,β∈V*,A∈ＶＮ,w∈Ｖ＋

特点：只有当非终结符A的上下文为α和β时，方可用w去替换A。

产生式右部不得为空(仅仅S→ε例外，但S不得出现在产生式右部)。例2.26 设文法G=(V N，ＶＴ,P,S),其中

V N={S,B,C} V T={a,b,c}

P: S∷=aSBC S∷=aBC CB∷=BC (CB::=AB AB::=AC AC::=BC 所以为1型) aB∷=ab bB∷=bb bC∷=bc cC∷=cc

这也是一个1型文法,它所产生的语言为L(G)={a n b n c n|n≥1}

3）2型文法（上下文无关文法）

若在文法G中，P中规则具有如下形式：

A∷=w 其中A∈V N,w∈V*

利用规则将A替换成w时，无需考虑A的上下文出现情况

大部分程序设计语言的文法近似于2型文法。

通常使用BNF表示法等价于前后文无关文法。是用BNF定义的语言都是前后文无关语言

4）3型文法（正规文法）

若在文法G中，P中规则具有如下形式：

右线性文法：A∷=aB 或A∷=a

左线性文法：A∷=Ba 或A∷=a

其中A,B∈V N,a∈V T

注意：这里的A和a只是代指，并不存在大小写之间的关系。

由3型文法所产生的语言称3型语言，记RL,即L3 3型文法与词法分析密切相关.

语言

由于将文法分为0型、1型、2型、3型四类，是逐渐增加

对规则限制条件而得到的。因此，由它们所定义的语言

是依次缩小，如果分别用L0、L1、L2和L3表示0型、1型、

2型和3型语言，则有

L0? L1 ?L2 ?L3

编译中分别借助于2型(上下文无关)文法和3型(正规)文法

来研究语法分析和词法分析。

文法和自动机

3型文法和有穷自动机

2型文法和下推自动机

1型文法和与线性界限自动机

0型文法和图灵机

15、会求一个文法的压缩过文法

（掌握）P36【小题】

压缩过文法

1. 在文法中不含有形如A∷=A的规则

2. 在文法中不包含多余规则

（1）每一个非终结符号A(Z除外)必须在某句型中出现(否则为不可到达的)，即Z?*αAβ，其中α,β∈V*,

（2）非终结符A必须推出终结符串t来(否则为不可终止的)，即A?+t t∈V T

例如：已知文法G，其产生规则P为：

Z∷=Be A∷=Ae|e B∷=Ce|Af C∷=Cf D∷=f

由该文法可知，因为规则D∷=f中非终结符D不在其它任何规则右部出现，所以规则D∷=f在推导中不起作用，为多余规则，应将其删除.

另外，规则C∷=Cf也是多余规则，因为一旦使用了这条规则，便会使推导无限制进行下去，最终无法推出终结符号串，所以也是该删除的多余规则；

同理，B∷=Ce也是多余规则，因为它含有非终结符C。

所以，将该文法多余文法删除得到压缩过文法为G’，其规则为：

Z∷=Be A∷=Ae|e B∷=Af

16、扫描缓冲区，超前搜索的概念和作用（记忆）P46【小题】

扫描缓冲区

（1）定义：扫描缓冲区就是在内存中开辟一部分单元，供识别单词用。

（扫描缓冲区的作用是为了识别单词符号）

注意：扫描缓冲区和缓冲区不同，缓冲区是从内/外存上读入部分字符，而扫描缓冲区仅是为识别单词用。

（2）工作原理

在扫描缓冲区中一般设两个指示器，一个指向当前正在识别单词开始位

置，另一个用于向前搜索寻找单词的终点。不论扫描缓冲区定为多大都

不能保证单词符号不会被它的边界所打断,因此，扫描缓冲区最好使用如

下所示的一分为二的区域（每半区可容120个字符）：

扫描缓冲区1 扫描缓冲区2

起始指示器搜索指示器

1) 开始时扫描缓冲区皆为空。

2) 调用预处理子程序，将120个字符填满扫描缓冲区1，并将两个指示器指向扫描

缓冲区１的第１个字符。

3) 将搜索指示器向后移动，当识别出一个单词之后，搜索指示器已指向下一个单词

的第一个字符，然后再将起始指示器移到搜索指示器指向字符，接着搜索指示器又开始扫描第二个单词。当搜索指示器越界时，说明缓冲区１中的字符不足一个单词，这时再调用预处理子程序，再将120个字符填满扫描缓冲区２，再将搜索指示器扫描缓冲区２第１个字符。这样，两个扫描缓冲区交替工作。

4) 一般描缓冲区长度可以存放最长一个单词，即可正常工作；否则就不能保证单词

符号不会被缓冲区边界所打断。

超前搜索

定义：词法分析程序在识别单词的时候，为进一步判明情况，确定下一步要做什么，一般采用超前读字符的方法

工作原理：向前搜索由起始指示器和搜索指示器协同工作，搜索指示器一直向前搜索直到可以判断单词类别后再退回原来位置

17、正规文法和状态转换图、左右线性文法转换（全套理解+掌握）P46-50

【小题或简答或解答】

左线性文法→状态转换图

右线性文法→状态转换图（见笔记）

状态转换图→正规文法

（1）开始状态只有引出，无引入，适合左线性（开始状态虚拟，可忽略）

（2）终止状态只有引入，无引出，适合右线性（终止状态虚拟，可忽略）

（3）若满足（1）（2），左右均可。

左右线性文法转换

左线性文法的产生式右线性文法的产生式

S → a S → a

A1 → a1 S → a1A1

A2 → A1a2 A1 → a2A2

S → A2a3A2 → a3

18、有穷自动机的概念和特点（DFA和NFA的各自特点）（理解+掌握）

P55-58【小题或简答】

DFA

有穷自动机可以用形式化的五元组、状态转换图和状态转换矩阵三种方式表示(DFA)M=(K,VT,M,S,Z)

(1)Ｋ是状态有穷的非空集合，Ｋ中每一个元素是一个状态；

(2)ＶＴ是一个有穷输入字母表，ＶＴ中的每一个元素称为输入字符；

(3)Ｍ是Ｋ×ＶＴ到Ｋ的单值映射（或函数），即Ｍ(q ,a)=p q ,p ∈K, a∈ＶＴ

表示：当前状态为q，输入字符为a时，将转到下一状态p，p是q的一个后继状态。由于映射是单值，所以称确定有穷自动机。

(4)Ｓ为开始状态，是唯一一个初态Ｓ∈Ｋ；

(5)Ｚ是终止状态集合Ｚ是Ｋ的子集。

输入符号串在确定有穷自动机上运行和DFA接受的语言

1)运行定义

一个输入符号串在DFA上运行定义为：

①Ｍ（q, ε）＝q q∈Ｋ

②Ｍ（q, at）=Ｍ（Ｍ（q, a）, t）=M (p, t)=…… a∈ＶＴ∈VＴ

表示：当状态为q时，输入字符串为at时，利用映射Ｍ（q, a）得到状态p，然后再利用映射Ｍ（p, t），如此继续下去，直至最后.

如果对某一字符串x，有Ｍ（Ｓ，x）＝r，而r∈Ｚ，则称字符串x被（ＤＦＡ）Ｍ接受。

我们把一个（ＤＦＡ）Ｍ所接受VT*中字符串全体称为M的接受集或M所接受

的语言，记为Ｌ（Ｍ），即

Ｌ（Ｍ）＝｛x｜Ｍ（Ｓ，x）∈Ｚ，x∈VT* ｝

NFA

一个非确定的有穷自动机（ＮＦＡ）Ｍ是一个五元组，即

Ｍ＝（Ｋ，ＶＴ，Ｍ，Ｓ，Ｚ）

其中：

Ｋ是状态有穷的非空集合；

ＶＴ是一个有穷输入字母表；

Ｍ是Ｋ×ＶＴ到Ｋ子集上映射，即Ｋ× VT → ２k}

２k是幂集，是K中所有子集组成。

即

Ｍ（q, a）＝｛p１，p２，…，pn｝∈２Ｋ，q∈Ｋ，a∈Ｖ它表示：当前状态为q，输入字符为a 时，映射Ｍ将产生一个状态集

合｛p１，p２，…，pn ｝（可能是空集），而不是单个状态，所以

称非确定有穷自动机。

Ｓ是开始状态集，Ｓ包含于K；

Ｚ是终止状态集，Ｚ包含于K。

(2) 输入符号串在NFA上的运行和NFA接受的语言

一个输入串在NFA上的运行定义为：

①Ｍ（q,ε）＝｛q｝q∈Ｋ；

②Ｍ（q,at）＝Ｍ（Ｍ（q,a）,t）

＝Ｍ（｛p１，p２，…，pn ｝，t）

＝∪Ｍ（pi，t）（i从1变到n)

其中，pi∈Ｍ（q,a），a∈ＶＴ，t∈ＶＴ*

对于ＶT*上的字符串x，令Ｓ０∈Ｓ，若集合Ｍ（Ｓ０，x）中

含有属于终态集Ｚ中的状态，或者说至少存在一条从某一个初

态结点到某一个终态结点的路径，且这些路径上所有箭弧的标

记字符连接起来的字符串等于x，我们就说x为（ＮＦＡ）Ｍ所

接受（识别）。

所有这样的x所组成的集合称之为（ＮＦＡ）Ｍ接受集或（Ｎ

ＦＡ）Ｍ所接受的语言，记为Ｌ（Ｍ），即

Ｌ（Ｍ）＝｛x｜Ｍ（Ｓ０，x）∩Ｚ≠ ? ，Ｓ０∈Ｓ，x∈ＶＴ*｝

凡是一个语言被NFA接受，一定能被DFA接受

19、正规表达式（会求其正规集）和有穷自动机

（含利用子集法把NFA转DFA并化简）（全套理解+掌握）P62-70【小题或简答或解答】

有一个正规文法G就一定可以构造一个有穷自动机（FA）M；反之，有一个有穷

自动机（FA）M，则一定可以构造一个正规文法。

（1）什么叫正规表达式？

首先我们来看一个例子，如：对于数字集合D={0，1，2，……9}，现在要用一个表达式刻画符号串20这个数，可以将20看成2和0组成的符号串，也可以用4*5表示，或用0+1+2+3+4+9+9-8表示。同样，在词法分析阶段，我们也要解决某字母表∑上语言的表示问题（所谓语言就是∑*上一个子集，即某些符号串集合。）

例如：Σ＝{0, 1}上一个语言L(G)={x｜x以0开头后面跟任意个1} ，这可以采用如下方法表示：

枚举法：L（G）={0，01，011，0111??}

文法生成法Z ∷=0 | Z1

自动机识别法：可以构造一个DFA来识别该语言

正规表达式：可用正规表达式来表示一个正规语言，象用4*5表示20一样，可以用0(1)* 表示0后跟若干个1的二进制数。

（2）非形式定义：

用来表示字母表∑上字符串集合∑*某些子集，经过运算符|（和）、?（积）、*（闭包）以及决定运算顺序的括号组合成一个有意义的集合运算式，称为正规表达式；正规表达式的值称正规集。

注意：正规表达式是表示运算的一个式子，而正规集是一个符号串集合，是正规表达式的运算结果。

例如：上面的例子，Σ＝{0, 1}其0(1)* 是正规表达式，而集合{0，01，011，0111??}是0开头后面跟任意个1，是正规集，也可以写成｜0(1)* ｜＝{0，01，011，0111??}

（4）递归定义

令Σ为有穷字母表，则Σ上的正规式和正规集可递归定义如下：

1.ε和?是Σ上的正规式，则它们相应正规集分别为｛ε｝和?；

2. 对于每一a∈Σ，a是Σ上一个正规式，则它所表示相应正规集为｛a｝；

3.如果e1和e2是Σ上的正规式，则相应正规集分别为L(e1)和Ｌ(e2)，则

(1) (e1)是正规式，其相应的正规集为L((e1))=L(e1)

(2) e1｜e2是正规式，其相应正规集为Ｌ(e1｜e2)＝Ｌ(e1) ∪Ｌ(e2);

（∪表示选择，集合直接合并，元素不能连接）

(3) e1·e2是正规式，其相应正规集为Ｌ(e1·e2)＝Ｌ(e1)Ｌ(e2)；

(4) (e1)*是正规式，其相应正规集为Ｌ((e1)*)＝(Ｌ(e１))*。

（5）性质

a.若两个正规式所表示正规集相同，则认为两者等价(证明正规式等价的方式)

b.其他性质（利用这些性质可以化简正规式，证明正规式的等价关系）

（1）e1｜e2＝e2｜e1 交换律

（2）e1｜（e2｜e3）＝（e1｜e2）｜e3 结合律+

（3）e1（e2e3）＝（e1e2）e3 结合律*

（4）e1（e2｜e3）＝e1e2｜分配律

（5）εe1＝e1ε＝e1 与空串联结

（6）?e1＝e1?＝?与空集积

（7）（e*）*＝e* 循环

（8）（ε｜e）*＝循环2

说明：∑*上的某些集合若不能用正规表达式表示，则该集合不是正规集。

如：∑={a,b},L(G)={a n b n| n≥0}就不是正规集，因为它不能用正规式表示。（可以用上下文无关文法Z∷=aZb | ab |ε产生）可以证明，

凡是由正规文法所产生的语言一定是正规集，即可由正规式表示。

（6）正规文法、正规表达式与有穷自动机的关系

定理：L是正规集?存在一个有穷自动机(FA)M，使得L=L(M)

?存在一个正规文法G，使得L(M)=L(G)

?存在一个正规表达式e，使得L(e)=L(G)

★★★

（7）正规表达式—>有穷自动机：

①正规表达式?②构造转换系统?③NFA(状态转换图) ?④NFA?⑤DFA

正规表达式?转换系统

方法一：

转换系统? NFA? DFA

由正规表达式构造出转换系统，实际上就是一个带空转换的ＮＦＡ

消去空转换而成为一个不带空转换ＮＦＡ，

再利用前面所学的方法将ＮＦＡ变成ＤＦＡ。

对于任一个（NFA）M，我们总能构造出与其等价的（DFA）M′

设（NFA）M=（Ｋ，V T，Ｍ，Ｓ，Ｚ）是V T上一个NFA，今构造一个等价

的（DFA ）M′＝（Ｋ′，V T′，Ｍ′，Ｓ′，Ｚ′）

其方法如下：例题P59

１. Ｋ′由Ｋ的全部子集组成，即Ｋ′＝２Ｋ（一般空集?无用可除去）

例如，若Ｋ＝｛Ｓ１，Ｓ２，Ｓ３｝，则Ｋ的一个子集｛Ｓ１，Ｓ２｝表示

Ｋ′一个状态，我们用记号［Ｓ１，Ｓ２］表示，也可重新命名。

２.ＶＴ′＝ＶＴ

３.Ｓ′＝［Ｓ］（例如：S={S1，S2}，则S’=[S1，S2]）

４.Ｚ′＝｛［Ｓ１，Ｓ２，…，Ｓn］｜［Ｓ１，Ｓ２，…，Ｓn］∈Ｋ′

且｛Ｓ１，Ｓ２，…，Ｓn｝∩Ｚ≠?｝

5.Ｍ′（［Ｓ１，Ｓ２，…，Ｓi］，a）＝［Ｒ１，Ｒ２，…，Ｒj］a∈ＶＴ

其中Ｍ（｛Ｓ１，Ｓ２，…，Ｓi｝,a）＝｛Ｒ１，Ｒ２，…，Ｒj｝

方法二：直接由转换系统来构造确定有穷自动机ＤＦＡ

1）确定DFA

设有正规式e为(a|b)*(aa|bb)(a|b)*试构造一个确定有穷自动机(ＤＦＡ)Ｍ，使得Ｌ(Ｍ)＝Ｌ(e)

已知此正规式的转换系统如下图。它的状态集Ｋ＝{S, 1, 2, 3, 4, 5, 6, Z}，其中Ｓ为初始状态，Ｚ为终止状态。Σ={a, b}，所以

①构造一张表，共3列，分别为I，Ia，Ib;

②求ε—CLOSURE(S)，ε—CLOSURE(S)={S，5，1}，将{S，5，1}

填到表格的第一行第一列；

③令I={S，5，1}，求Ia，Ib(分别为{5，3，1}和{5，4，1}）并填入表格的第一行Ia、Ib列;

④检查上一步Ia, Ib两个子集是否在I列中出现，将未出现的Ia或Ib作为

表格第二或第三行I列的值，类似步骤（3）求第二行的Ia, Ib的值。再检查，再求第三行的Ia,Ib的值。直到所有I的Ia, Ib都已求，并且没有新的状态子集加入第一列为止

⑤将I中各子集DFA中一状态并给予重命名。

⑥确定DFA的初态为重命名后的状态0（重命名前为{S，5，1}含原初态S），终态为3，4，5，6（它们在重命名前都含原终态Z）

2)DFA化简

基本思想：把（DFA）Ｍ的状态集分别划成一些不相交子集，使得任何不

同的两个子集的状态是可区分的，而同一子集中的任何两个状态是等价的。

最后，从每个子集选出一个状态以代表该子集，同时消去其它等价状态。

如：上例

先将K=｛0，1，2，3，4，5，6｝划分成两组：

终态集｛3，4，5，6｝和非终态集｛0，1，2｝

由状态图可知{3，4，5，6}a={3，6}均为终态，{3，4，5，6}b={4，5}也均为终态，所以{3，4，5，6}是不可分的，即等价。

考察｛0，1，2｝a，因为{０}a＝{２}a＝｛１｝（非终态），{１}a＝｛３｝（终态），故｛0，1，2｝可区分为｛0，2｝，｛１｝。

再考察{0，2}b，因为{０}b＝{2} （非终态），{2}b＝｛5｝（终态），故｛0，2｝可区分为{0}, {2}。

补充：

(1) 转换系统的定义

所谓转换系统是一个具有唯一开始状态Ｓ和唯一最终状态Ｚ的一种

特殊状态图。其条件是：

1)没有弧引向开始状态Ｓ只引出

2)没有弧从终止状态Ｚ引出只引入

3)转换系统的弧可以用空符号ε标记。

(2) 转换系统与有穷自动机状态转换图的区别

1) 有穷自动机状态转换图开始状态和终止状态不唯一

2) 有穷自动机状态转换图弧上没有空符号ε标记

3) 有穷自动机状态转换图开始状态有引入，终止状态有引出

(3) 有穷自动机状态转换图与转换系统的关系

定理：对于任何一个有穷自动机状态转换图存在一个相应转换系统。

\（4）状态图→转换系统：

设状态图具有Ｓ１，Ｓ２，…，Ｓn的开始状态,Ｚ１，Ｚ２，…，Ｚm的终态。

1) 首先，我们增加一个新状态Ｓ作为转换系统唯一开始状态，并增加n条标记为ε，分别引到Ｓ１，Ｓ２，…，Ｓn的弧。

2) 然后再增加一个新状态Ｚ作为转换系统最终状态，并增加m条标记为ε的弧自

Ｚ１，Ｚ２，…，Ｚm引到Ｚ。

20、会利用解方程的方法把左线性或右线性文法转换为正规表达式（掌握）

P63-64【小题】

（1）由右线性文法构造正规表达式

例：已知正规文法（右线性文法）Ｇ：

Ｓ∷＝aS｜

Ｂ∷＝

Ｃ∷＝aC｜a

1)写成正规表达式方程组，用“+”代替“|”，用“=”代替“∷＝”

Ｓ＝aS＋aB （1）

Ｂ＝bC （2）

Ｃ＝aC＋a （3）

2) 求解形如X=aX+b的方程，（从只含一个非终结符的方程开始）

其中a，b是终结符，即是字母表Σ上的正规表达式，Ｘ是文法非终结符（变量）。

X=a*b 是方程的解

3)为了求出文法开始符号Ｓ的解，我们先解方程（３），类似于X=aX+b 的解X= a*b，

的解为C=a*（4）

4)将（4）代入（2），得B=ba*a （5）

5)将（5）代入（1），得S=aS+aba*a，显然S=a*aba*a （即文法所对应的正规式），

正规式对应的正规集是｛a m aba n｜m ≥0, n≥1｝

4)—5)是使用代入法求其他变量的解

（2）由左线性文法构造正规表达式

求解形如X=Xa+b的方程X=ba* 是它的一个解

21、LL(1)分析法（全套理解+掌握）P85-90

（P87伪代码除外）【小题或简答或解答】

1）自顶向下分析方法

LL：从左（left）到右扫描输入符号串并建立它的最左推导（Leftmost derivations）数字1是指向前看一个符号来决定选择同一个非终结符不同规则2）LL（1）分析器的组成：总控程序，分析表，分析栈

3）LL（1）语法分析程序的机器模型是一个下推自动机

4）LL（1）分析器的工作过程

其步骤如下：

a）将符号#及文法的开始符号Ｓ依次置于分析栈的底部，

各指示器调整至起始位置(分析栈的栈顶元素和输入串的首字符)

然后反复执行第（2）步

b）设在分析的某一步，分析栈及余留的输入符号串处于如下格局

#X1X2…X m-1X m a i a i+1…#

其中，Ｘ１，Ｘ２，…，Ｘm为分析过程中所得的文法符号，此时，可视栈顶符号Ｘm的不同情况，分别做如下的动作:

①Ｘm∈ＶＮ（Ｘm，a i）查分析表Ｍ

设Ｍ［Ｘm,a i］为一产生式(如X m→UVW)

将Ｘm从分析栈中退出，并将ＵＶＷ按反序推入栈中（即用该产生式推导一步），从而得到新的格局:

#X1X2…X m-1WVU a i a i+1…#

若Ｍ［Ｘm，a i］＝“ＥＲＲＯＲ”，则调用出错处理程序进行处理;

②若Ｘm＝a i≠#，

表明栈顶符号已与当前正扫视的输入符号得到匹配，

将Ｘm（即a i）从栈中退出，并将输入符号指示器向前推进一个位置；

③若Ｘm＝a i＝#

表明输入串已完全得到匹配，此时即可宣告分析成功而结束分析工作。

5）FIRST集

①定义：假定α是文法G的任一符号串，或者说α∈(V TＵVＮ)*，我们定义

FIRST（α）＝｛a｜α?*a…，a∈ＶＴ｝

特别是，若α?*ε，则规定ε∈FIRST（α）

即FIRST（α）是α的所有可能推导的开头终结符或可能的ε

②单个符号FIRST集Ｘ∈(ＶＮＵＶＴ)

只要连续使用下列规则，直至每个FIRST集不再扩大为止。

a.若X∈ＶＴ，则FIRST（Ｘ）＝｛Ｘ｝。

b.Ｘ∷＝aα（a∈ＶＴ），或Ｘ∷＝ε

把a或（和）ε加入FIRSTＸ）中。

c.Ｘ∷＝Ｙ１Ｙ２…YＫ，

若Ｙ

１∈ＶＮ，则将FIRST（Ｙ１）（除ε）FIRST（Ｘ）；

若前m个Y均有Y::= ε的规则，则将第m+1个的Y的

FIRST（除ε）FIRST（Ｘ）；

若Ｙ１Ｙ２…ＹＫ每个非终结符号都可能推导出空符号串，即Ｙ１Ｙ２…ＹＫ?*ε，则把ε也加进FIRST（Ｘ）中。

③符号串FIRST（α）α＝Ｘ１Ｘ２…Ｘn，

可按如下步骤构造FIRST（α）。

a.FIRST(X1) （除εFIRST（α）中

b.若ε∈FIRST（Ｘ

１），FIRST（Ｘ２）（除εFIRST（α）如此等等。(若前m个Y均有Y::= ε的规则，则将第m+1个的Y的

FIRST（除ε）FIRST（Ｘ）；)

c.Ｘ１Ｘ２…Ｘn，每个非终结符号都可能推导出空符号串

则再将ε加进FIRST（α）中。

6）FOLLOW集

①定义：假定S是文法G的开始符号，对于G的任何非终结符A，

FOLLOW（A）={ a | S ?*…Aa…, a ∈ＶＴ}

特别是，若S ?*…A，则规定#∈FOLLOW（A）

即：FOLLOW（A）是所有句型中出现在紧接A之后的终结符或#

②每个非终结符ＡFOLLOW的算法

可反复应用如下规则，直到每个FOLLOW集不再扩大为止。

a.对于文法的开始符号Ｓ，令#∈ＦＯＬＬＯＷ（Ｓ）。

（因为S ?* S 由定义#∈FOLLOW（S））

b.Ａ∷＝αＢβ的规则，且β≠ε，

则将FIRST（β）（除ε）?FOLLOW（Ｂ）中。

c.Ａ∷＝αB或Ａ∷＝αBβ的规则，且β ?*ε(易被忽略，注意！！！！)，

则FOLLOW（Ａ）中全部终结符均属于FOLLOW（（Ｂ），其中α可以为ε。

7）构造分析表M算法

前期准备：非终结符的FIRST（A）

规则右部的FIRST（α）（符号串）

非终结符的FOLLOW（A）

对于Ｇ中每一个规则Ａ∷＝α，可按如下算法确定表中各元素：

①对FIRST（α）中每一终结符a，置Ｍ［A, a］＝“Ａ→α”

(表示分析栈中是A，遇到以a开头的符号串选用产生式Ａ→α)

②若ε∈FIRST（α）或是（α=0），则对属于FOLLOW（Ａ）中的

每一符号b (b为终结符或＃)，置Ｍ［Ａ，b］＝“Ａ→α”；

（表示分析栈中是A，遇到以b开头的符号串选用产生式Ａ→α）

③把Ｍ中所有不能按规则①、②定义的元素均置为出错。