《编译原理简明教程》普通高等教育“十二五”规划计算机教材---太原理工大学---计算机科学与技术学院---冯秀芳、崔冬华、段富等第一章 引言
第二章 形式语言理论基础第三章 自动机理论基础第四章 词法分析第五章 语法分析—自顶向下分析方法第六章 语法分析—自底向上分析方法
第七章 语义分析及中间代码的生成第八章 代码优化第九章 目标代码的生成第十章 符号表第十一章 目标程序运行时的存储组织与分配第十二
章 出错处理第十三章 编译程序自动生成工具简介第十四章 面向对象语言的编译第十五章 并行编译技术目 录第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|Bb
A→Ba|a B→Ab|b①以S做初始状态 (S ∨)2.应用状态转换图识别句子识别句子：从开始状态到终
止状态经过的边上的符号序列。识别句子的步骤：①从开始状态出发，以欲识别符号串的最左字符开始，寻找标有该字符的边，状态变化。②扫描下
一个字符，从当前状态出发寻找标有该字符的边，当前状态变化。③重复第②步，直到扫描完所有字符为止，且当前状态为终止状态。定理1 当识
别一个符号串? 时，如果能从转换图的开始状态出发行进达到的右端，那么， ? 为句子的充要条件是最后的当前状态为终止状态。例：判断a
babaaa及bababbb是否句子 当前状态 输入串的其余部分 语法树 S
ababaaa Z A babaaa
Z a B abaaa A a A
baaa B a B aaa
A b A aa B a Z
a A b Z a a推导：Z Za Aaa
Baaa Abaaa Babaaa Ababaaa ababaaa3.应用状态转换图为正则语言构造正则文法
正则语言 → 状态转换图 → 正则文法 ε
a
ab a|b
b例3-3 正则语言{ |n≥0 }正则文法： Z→Cb C→b
|Bb B→Ab A→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.5
L(D)={ab,ac,aaab,abaa …,acb …, …}β1、状态转换矩阵例3-1
或
或 注：空白或0表示空状态（无后继状态）3.1.4
DFA在计算机内的表示上例：2. 表结构表示（见表3.2）状态名射出边数边上的标记转换后的状态3.1.5不确定有限自动机(NFA
)定义： NFA是一个五元组， = (Κ, Σ, ,?, F) 其中：Κ 是状态的非空有限集 Σ 有
穷的输入字母表 是从ΚXΣ到Κ的子集的映射 ? 开始状态 ? Κ F
终止状态 F Κ 例： = (Κ,Σ, ,?,F)其中 Κ={ , , } Σ={a,b}
?={ , } F={ } ( ,a)={ } ( ,b
)={ , } ( ,a)= Φ ( ,b)={ } ( ,a)= Φ
( ,b)={ }得出：例3-7 由正则文法构造NFAG[Z]: Z → Za|Aa|Bb A
→ Ba|Za|a B → Ab|Ba|b识别符号串babbabb的过程:步骤 当前状态 输入串余留部分 可能的
后继状态 选择状态 1 S babbabb B B 2
B abbabb A,B A 3 A bbabb
B B 4 B babb Z
Z 5 Z abb A,Z A 6 A
bb B B 7 B b
Z Z 8 . 由此可见，在NFA中由于某些状态的转换需从
若干个可能的后继状态中进行选择，这种不确定 性给识别过程带来反复，影响了工作效率。3.1.6 NFA到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终止状态的状态均为D
FA的终止 状态 。例 =(Κ,Σ, ,?,F) 其中 S={ , } K={ , ,
} Σ={a, b} F={ }转换：① =[ , ]② ({ ,
},a)={ } ({ , },b)={ , }∴
([ , ],a)=[ ] ([ , ],b)=[
, ]③ ({ },a)= Φ ({ },b)={ }
({ , },a)={ } ({ , },b)={
, , }∴ ([ ],b)=[ ] ([
, ],a)=[ ] ([ , ],b)=[ , ,
] ({ },b)={ } ([ ],b)=[ ]
({ , , },a)={ } ([ , ,
],a)=[ ] ({ , , },b)={ ,
, } ([ , , ],b)=[ , ,
]∴ ={[ , ],[ ],[ , ],[ ],[ , ,
]} =[ , ] ={[ ],[ , ]
,[ , , ]} 见书 例3-9 NFA有4个状态，考虑状态集合的一切子集。DFA中有 2
-1=15个状态，其中有7个无关状态，可删去。[ ][ ][ , ][ ][
] [ , ][ ][ , , ] [ ] [ ][
, , ][ ][ , , ]43.2 DFA的化简 化简：对于一个
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, 01 10(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 ф =R R ? ?=R R ?≠R
R ? ? ≠ ф 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 下推自动机的机器模型由一条
输入带，一个有限控制器和一个下推栈组成控制器输入带栈顶下推栈3.4.2 PDA的形式定义定义：PDA是一个七元组 =
(K,∑, ,δ,S, ,F)其中： K 是状态集合 ∑ 字母表 下推字母表（栈符号的有限集）
δ 从Kx(∑∪{ε})x →Kx 的映射 栈中初始符号 ∈ S 初始状态集
S K F 终止状态集 F K转换函数 δ( ,a, )=( ,β)表示：在状态 ，输
入a，栈顶符号为 时，进 入状态 ， 由符号串β代替，同时读头 右
移 一格。 (β的最左符号放在栈顶，即β的逆串放入下推栈)特别：当β = ε时，表示 被弹出，读头右移;
当a = ε时，表示读头不动，状态仍转换。例： Z → Z(Z)| ε其中 K={ }, ∑={(,)}, ={
A,( } S={ }, =A, F={ } δ( ,(,A )=( ,(A ) δ( ,(,( )=( ,(( ) δ( ,),( )=( ,ε) δ( ,ε,A)=( ,ε)= (K,∑, ,δ,S, ,F) 识别过程： (()(())) 过程如下: 见书P50另一个例子 当前状态 下推栈 输入符号A (()(()))A( ()(()))A(( )(()))A( (()))A(( ()))A((( )))A(( ))A( ) A ε ε |
|
