《编译原理简明教程》 第3章

《编译原理简明教程》普通高等教育“十二五”规划计算机教材---太原理工大学---计算机科学与技术学院---冯秀芳、崔冬华、段富等第一章引言第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表第十一章目标程序运行时的存储组织与分配第十二章出错处理第十三章编译程序自动生成工具简介第十四章面向对象语言的编译第十五章并行编译技术目录第3章自动机理论

学习目标

本章主要介绍有穷自动机的理论及借助有穷自动机实现词法分析程序的方法。着重需要掌握以下内容:

确定的有穷自动机DFA

非确定的有穷自动机NFA

NFA到DFA的转换DFA的最小化正规表达式到DFA的转换目录3.1有限自动机的基本概念3.2确定有限自动机DFA的化简3.3正则表达式形式定义3.4下推自动机PDA

文法：是从语言生成的角度定义了语言。

自动机：是从识别语言出发，定义了语言。

自动机---是具有离散输入/出系统的一种数学模型。

自动机理论：是编译程序词法分析的理论基础。

3.1有限自动机的基本概念3.1.1有限自动机的定义和表示法

1.状态转换图的引进和构造

定义1：转换图（TG）是定义在∑上的有向图，满足以下条件a.至少存在一个初始结点b.存在一些终止结点（也可为空）c.每条边上标有∑上的符号（也可为ε）

例：TG接收（or识别）的符号串：从某一初始结点到某一终止结点的序列。TG所接收的符号串集合：

L（TG）L（TG）={ab，bab，babbb，abbb，……}状态转换图：结点-----状态------文法的非终结符初始结点-----初始结点终止结点-----终止结点-----开始符号边------转换关系------终结符号∑={a，b}1.状态转换图构造算法:②以每个非终结符号做其它状态③对于形如Q→q的规则,

对于形如Q→Rq的规则,④以文法开始符号为终止状态例3-1：文法G[Z]：Z→Za|Aa|BbA→Ba|aB→Ab|b①以S做初始状态(S∨)2.应用状态转换图识别句子识别句子：从开始状态到终止状态经过的边上的符号序列。识别句子的步骤：①从开始状态出发，以欲识别符号串的最左字符开始，寻找标有该字符的边，状态变化。②扫描下一个字符，从当前状态出发寻找标有该字符的边，当前状态变化。③重复第②步，直到扫描完所有字符为止，且当前状态为终止状态。定理1

当识别一个符号串∂时，如果能从转换图的开始状态出发行进达到的右端，那么，∂为句子的充要条件是最后的当前状态为终止状态。例：判断ababaaa及bababbb是否句子

当前状态输入串的其余部分语法树SababaaaZAbabaaaZaBabaaaAaAbaaaBaBaaaAbAaaBaZaAbZaa推导：ZZaAaaBaaaAbaaaBabaaaAbabaaaababaaa3.应用状态转换图为正则语言构造正则文法

正则语言→状态转换图→正则文法

ε

a

ab

a|b

b例3-3正则语言{|n≥0}正则文法：Z→CbC→b|BbB→AbA→a|Ba3.1.2有限自动机(FA)FA可看作一个机器模型，由一个带读头的有限控制器和一条字符输入带组成。工作原理：读头从左到右扫描输入带，读到一个字符，状态改变，同时读头右移一个字符，…，直到读头读到

“#”，状态进入终止状态。控制器中包括有限个状态，读入一个字符形成状态转换。

控制器输入带ababa…#

后继状态为自身状态转换后继状态为一个DFA

后继状态为多个NFA3.1.3确定有限自动机(DFA)

定义：DFA是一个五元组=(Κ,Σ,,Ѕ,F)

其中：Κ

是状态的非空有限集

Σ有穷的输入字母表

是从ΚXΣ到Κ的映射，且为单值，

即有转换函数

(,a)=,、∈Κ

表示当前状态为，输入符号为a时，转换到

Ѕ初始状态Ѕ∈ΚF非空的终止状态集FΚ

例：由例3-1的状态转换图构造DFA如下

=({S,Z,A,B},{a,b},,S,{Z})其中：

(S,a)=A,

(S,b)=B

(A,a)=Z,

(A,b)=B

(B,a)=A,

(B,b)=Z

(Z,a)=Z例:=({,,,},{a,b,c},,,{,})

(,a)=,

(,a)=(,b)=,

(,c)=(,a)=,

(,b)=(,a)=,(,b)=定义:

所接收的语言（正则集）L()={β|S,∈F},

见书定义4.5L(D)={ab,ac,aaab,abaa…,acb…,…}β1、状态转换矩阵例3-1

或或

注：空白或0表示空状态（无后继状态）3.1.4DFA在计算机内的表示0ABZZZAB0

输入

状态abSABAZBBAZZZ上例：

输入

状态abc2.表结构表示（见表3.2）S2aAbBA2aZbB状态名射出边数边上的标记转换后的状态3.1.5不确定有限自动机(NFA)定义：NFA是一个五元组，=(Κ,Σ,,Ѕ,F)

其中：Κ是状态的非空有限集

Σ有穷的输入字母表

是从ΚXΣ到Κ的子集的映射

Ѕ开始状态Ѕ

ΚF终止状态FΚ

例：=(Κ,Σ,,Ѕ,F)其中Κ={,,}Σ={a,b}Ѕ={,}F={}(,a)={}(,b)={,}(,a)=Φ(,b)={}(,a)=Φ(,b)={}得出：

输入

状态ab

例3-7由正则文法构造NFAG[Z]:Z→Za|Aa|BbA→Ba|Za|aB→Ab|Ba|b识别符号串babbabb的过程:步骤当前状态输入串余留部分可能的后继状态选择状态1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ8.

由此可见，在NFA中由于某些状态的转换需从

若干个可能的后继状态中进行选择，这种不确定

性给识别过程带来反复，影响了工作效率。3.1.6NFA到DFA的等价转换定理3：设L是一个为NFA某所接受的符号串集合，则存在一个

接受L的DFA，即L(D)=L(N)。算法：NFA=(Κ,Σ,,Ѕ,F)DFA=(,,,,)

1、若NFA中全部初始状态为,,…,

则令DFA的初始状态=[,,…,][]表示若干状态构成某一状态

2、设Q=[,,…,]是DFA的一个状态

在NFA中，({,,…,},a)={,,…,}

则令([,,…,],a)=[,,…,]。3、重复第2步，直到不出现新的状态为止。4、上面得到DFA的状态集，映射,Σ

不变。5、在DFA中，含有NFA终止状态的状态均为DFA的终止状态。例=(Κ,Σ,,Ѕ,F)其中S={,}K={,,}

Σ={a,b}F={}转换：①=[,]②({,},a)={}({,},b)={,}∴([,],a)=[]([,],b)=[,]③({},a)=Φ({},b)={}({,},a)={}({,},b)={,,}∴([],b)=[]

([,],a)=[]([,],b)=[,,]({},b)={}([],b)=[]({,,},a)={}([,,],a)=[]({,,},b)={,,}

([,,],b)=[,,]∴={[,],[],[,],[],[,,]}=[,]={[],[,],[,,]}

见书例3-9NFA有4个状态，考虑状态集合的一切子集。DFA中有2-1=15个状态，其中有7个无关状态，可删去。

输入

状态ab

[][][,][][][,][][,,][][][,,][][,,]43.2DFA的化简

化简：对于一个DFA，构造另一DFA，使L()=L()且的状态个数不多。3.2.1等价状态和无关状态定义：等价状态,分别为一个状态，L()是从出发导出的所有符号串，若L()=L()，则称，是等价状态。定义：无关状态无用状态：从开始状态不能到达的状态。死状态：不能到达终止状态的状态。例：L()=L()={a},是等价状态

死状态

无用状态

3.2.2自动机的化简

——求自动机状态最少化问题

1、不等价状态的区别

对于状态，有(,a)=,(,a)=

若与等价，则称,等价，否则,不等价。(,a)=，(,b)=，、等价吗？上例合并等价状态

删除无关状态2.自动机的简化算法：

划分状态K=(终止状态集,非终止状态集)

进一步划分,

对于(,a)=,(,a)=

若,属同一状态集合，则,将放在同一集

合，否则分两个集合。

重复，直到每个集合不能再划分。

同一集合中的状态为等价状态，进行合并。

若有无关状态，则将其删除。

例：解：{,,,}{}(,a)=,(,a)=,(,a)=,(,a)=(,b)=,(,b)=,(,b)=,(,b)=∴{,,,}={,,}{}又∵(,b)=∴{,,}={,}{}{,}{}{}{}

合并，得：3.3正则表达式（正则式）定义：

①ε，Φ是Σ上正则表达式。{ε}，Φ②任意a∈Σ是正则表达式。{a}③若,是正则表达式{},{}则,•,,也是正则表达式。正则式所描述的语言又称为正则集，记L(R)。|

用正则运算符（闭包，连接，并）来构造描述语言的表达式。例：b,0110(01|10)“

”也可用“|”

例：Σ={a,b}见书P48

正则表达式也是描述单词的重要工具。正则表达式：

ε,Φ,a,b,ab,,…L(ε)={ε},L(Φ)=Φ,L(a)={a}L()={ε,a,aa,aaa,

…}L()={ε,aa,ab,aab,…}L()={a,aab,aabab,…}正则集：对于标识符的描述类似于扩充的BNF表示法<标识符>∷=<字母>{<字母>|<数字>}又如可含有正负号的整数和小数可表示为：

(D={0,1,2,…,9})

R={+,-,

ε}(..)Σ={<字母>，<数字>}正则表达式<字母>正则集L(R)={<字母>,<字母><字母>,<字母><数字>,…}例：G=({A},{α,β},A,P)性质：Rф=RR•є=R

R

є≠RR•є≠

фRф=фR=фRє=єR=R=()==()=()P:A→αA|βL(G[A])={β,αβ,ααβ,…}={β|

n≥0}

用正则表达式

β

正则集L(β)={β,αβ,ααβ,…}3.4下推自动机(PDA)例：文法G[Z]:Z→Z(Z)|ε语言：ε,(),(()),((())),()(),…成对括号自动机：下推自动机可解决上述自动机的缺陷3.4.1下推自动机的机器模型由一条输入带，一个有限控制器和一个下推栈组成abaa…#控制器输入带┆栈顶下推栈3.4.2PDA的形式定义定义：PDA是一个七元组=(K,∑,,δ,S,,F)其中：K是状态集合∑字母表

下推字母表（栈符号的有限集）δ从Kx(∑∪{ε})x→Kx

的映射

栈中初始符号∈

S初始状态集SKF终止状态集FK转换函数δ(,a,)=(,β)表示：在状态，输入a，栈顶符号为时，进

入状态，由符号串β代替，同时读头

右移一格。(β的最左符号放在栈顶，即β的逆串放入下推栈)特别：当β=ε时，表示被弹出，读头右移;

当a=ε时，表示读头不动，状态仍转换。例：Z→Z(Z)|ε