E
（ E ）
E E *
E E +
i i
i
E
（ E ）
E E +
E E i
i i
*
例（ i+i*i）
第二节 自动机
文法是语言的生成系统，而自动机是
语言的识别系统。自动机分为,图灵机、
线性有界自动机、下推自动机、有限自
动机
一, 有限自动机的定义
1,确定的有限自动机
DFA Md=(?,S,s0,F,?)
?,S?? →S
例, ?={0,1} s0是初态
S={s0,s1,s2,s3}
F={s0}
?(s0,0)=s2 ?(s0,1)=s1
?(s1,0)=s3 ?(s1,1)=s0
?(s2,0)=s0 ?(s2,1)=s3
?(s3,0)=s1 ?(s3,1)=s2
2,非 确定的有限自动机
NFA Mn=(?,S,s0,F,?)
?,S?? →2 S
例, ?={0,1} s0是初态
S={s0,s1,s2,s3,s4}
F={s2,s4}
?(s0,0)={s0,s3} ?(s0,1)={s0,s1}
?(s1,0)=? ?(s1,1)={s2}
?(s2,0)={s2} ?(s2,1)={s2}
?(s3,0)={s4} ?(s3,1)=?
?(s4,0)={s4} ?(s4,1)={s4}
二, 有限自动机的表示
1,状态转换矩阵
若 │S│= m,│?│=n
则可以用一个 m?n的矩阵表示 S??的状态
变换
S ? 0 1
s0
s1
s2
s3
s2 s1
s3 s0
s0 s3
s1 s2
DFA
F={s0}
S ?
s0
s1
s2
s3
s4
0 1
{s0,s3} {s0,s1}
?
?
{s2} {s2}
{s2}
{s4}
{s4} {s4}
NFA
F={s2,s4}
2,状态转换图
初态,
终态,
?:所有弧上字符的集合
?
s0 s1
s3 s2
? 1
1
1
1
0 0 0 0
DFA
s0 s4 ?
1
1
0 s3
s1
s2
0
0,1
NFA
0,1
0,1
三, 有限自动机识别的语言
1,有限自动机 FA M识别的串 α,
初态 s0至终态 f的某一道路上有向边的标记字
符依次连接所得的字符串恰为 α。
2,FA M所识别的语言,
FA M所识别的所有字符串的集合 。 即
L(M)={α│α??* and ?(s0,α)=f?F}
3,有限自动机的等价
if L(M1)=L(M2)
then FA M1和 FA M2等价
四, NFA和 DFA的关系
1,DFA和 NFA的区别在于状态转换函
数 ?的不同
2,DFA是一个特殊的 NFA
3,NFA和 DFA的等价性
定理 4.1 任一不确定的有限自动机 Mn,
它所识别的语言为 L(Mn)，则必然存在一
确定的有限自动机 DFA Md，它所识别的
语言 L(Md)恰为 L(Mn)，即 L(Md) =L(Mn)
第三节 正则表达式和正则集
?正则表达式与正则文法有相同的表达能
力, 两者是等价的 。
?词法结构 ?正则表达式 ?有限自动机
一, 正则表达式和正则集的定义
1,递归定义
对于给定的字母表 ?，有
（ 1） ?和 ?是 ?上的正则表达式，它们所表
示的正则集分别是 {?}和 {?}；
（ 2）对任一 a??,a是 ?上的正则表达式，
它所表示的正则集为 {a}；
（ 3）如果 R和 S是 ?上的正则表达式，它们所
表示的正则集分别为 L(R)和 L(S)，则
?(R|S)也是 ?上的正则表达式，它所表示
的正则集为 L(R)?L(S)；
?(R?S)也是 ?上的正则表达式，它所表示
的正则集为 L(R)L(S)；
?(R)*也是 ?上的正则表达式，它所表示的
正则集为 (L(R))*。
（ 4）仅有限次使用规则 (1),(2),(3)得到的
表达式，是 ?上的正则表达式，它所表示的集
合是 ?上的正则集。
2,有关运算
（ 1）,|”称为“或”
（ 2）,?”称为“连接”
（ 3）,*”称为“闭包”,,+”称为“正闭包”
（ 4）设 U,V是 ?*的子集，有
UV={??|??U & ??V}
Vn= VV…V
V0={?},V+ =V1?V2?V3?..,
V*=V0?V1?V2?..,
n次
例,ba*
a(a|b)*
(a|b)*(aa|bb)(a|b)*
(A|B)(A|B|0|1)*
(0|1)(0|1)*
二, 有限自动机与正则表达式
1,定理 4.2
设 R是 ?上的一个正则表达式，则存在一个
?上的 NFA M，使得 L(M)=L(R)；反之亦然。
2,正则表达式 ?NFA
i k j A B
i j AB 代之以
i j A|B 代之以
i j
A
B
i j A* 代之以
i k j ? ?
A
例, (a|b)*(aa|bb)(a|b)*
0 2 ? ? ? ?
a a a
b b
b
a
1
3
4
5 6 7
b
三, 正则文法和有限自动机
?每个非终结符对应一个状态,开始符对应初态
?另设一个终态 Z
?A?? 对应
?A??B 对应
A B
A Z ?
?
例, G(S)
S?0U|1V
U?1|1S
V?0|0S
S U
V Z
0
1
1
0
0
1
?
四, 正则表达式的应用
—— 词法分析器的自动生成
正则表达式
? NFA Mn
? DFA Md
?词法分析器
第四节 下推自动机
下推自动机 (简称为 PDA)是上下文无
关文法的识别器。一个下推自动机由一
条输入带,一个有限控制器和一个下推栈
组成
a1 ak $
zk
zk-1
z0
有限状态控制
一, 不确定的下推自动机
1,定义
M=(?,S,?,?,s0,z0,F)
??是一个有限输入字母表
?S为有限状态集
??为有限下推栈字母表,约定对于 ???*,?
的最左字符在栈顶,?=?时下推栈为空
?s0?S,为初态
?z0??,为下推栈的初始符号
?F?S,为终态集
??是状态转换函数,为 S?(??{?})??到 S??*的
一个子集间的映射,
?(s,a,z)={(si,?i)│i=1,2,…,n}
其中 s,si?S,a??,z??,?i??*,它表示在状态 s下,
输入字符为 a,下推栈栈顶符号为 z时,状态转
换为 si,下推栈将 z上托后,将 ?i下推入栈,同时
输入指针右移一位
2,特殊情况
—— 输入指针不变时的转换
δ(s0,ε,z)={(si,?i)|i=1,2,…,n}
3,瞬时状态及其转换
(s1,aw,z?)|— (s2,w,??) 一次移动
(s1,aw,z?)|— (s2,w,??) 0或多次移动
其中,s1,s2?S,a??,w??*,z??,?,???*
M
*
二, 下推自动机识别的语言
1,终态接受和空栈接受
设 (s0,w,z0)为初始瞬时状态, 有
(s0,w,z0) |— (s,ε,α)
?当 s?F时,称 w为 M终态接受
?当 α=ε时,称 w为 M空栈接受
*
2,终态接受语言
L(M)={w|(s0,w,z0)|— (s,?,α),s?F,α? ?*}
3,空栈接受语言
L?(M)={w|(s0,w,z0)|— (s,?,?),s?S}
此时,下推自动机记为 M?=(?,S,?,?,s0,z0,?)
*
*
三, 确定的下推自动机
下推自动机 M=(?,S,?,?,s0,z0,F)满足以
下两个条件之一,(瞬时状态的转换只有一
种可能 )
对任何 s?S,z??以及 a??,有
(1)?(s,?,z) = ?,或者 ?(s,a,z) 有唯一的元素 ;
(2)?(s,a,z) = ?,或者 ?(s,?,z) 有唯一的元素；
则 M是一确定的下推自动机。
四, 一些等价性定理
（ 1）终态 PDA和空栈 PDA的等价性。
（ 2）上下文无关文法和下推自动机的等
价性。
第五节 编译概述
一, 不同语言之间的翻译
1,翻译程序, 等价地变换
2,编译程序, 高级语言 ?低级语言
3,汇编程序, 汇编语言 ?机器语言
二, 编译执行和解释执行
1,编译执行
源程序 目标程序 计算结果
汇编语言程序 目标程序
2,解释执行,一边翻译一边解释执行
编译
编译
运行
汇编程序
初始数据
三, 编译程序的组成
1,词法分析, 输入字符串, 根据词法规则
识别出单词符号 。
2,语法分析, 根据语法规则, 将单词符号
构成各类语法单位, 并进行语法检查 。
3,语义分析与代码生成,
根据语义规则,进行初步编译 。
4,优化,对中间代码进行等价变换,以
使代码更有效 。
5,目标代码生成,生成机器语言程序
或汇编语言程序 。
6,符号表管理,完成符号表的建立,查
找,更新。
7,出错处理
源程序字符串
词法分析器
语法分析器
语义分析、中间代码生成器
代码优化器
目标代码生成器
单词流
语法单位
中间代码序列
中间代码序列
目标程序
符
号
表
管
理
程
序
出
错
处
理
程
序
编译程序的结构
（ E ）
E E *
E E +
i i
i
E
（ E ）
E E +
E E i
i i
*
例（ i+i*i）
第二节 自动机
文法是语言的生成系统，而自动机是
语言的识别系统。自动机分为,图灵机、
线性有界自动机、下推自动机、有限自
动机
一, 有限自动机的定义
1,确定的有限自动机
DFA Md=(?,S,s0,F,?)
?,S?? →S
例, ?={0,1} s0是初态
S={s0,s1,s2,s3}
F={s0}
?(s0,0)=s2 ?(s0,1)=s1
?(s1,0)=s3 ?(s1,1)=s0
?(s2,0)=s0 ?(s2,1)=s3
?(s3,0)=s1 ?(s3,1)=s2
2,非 确定的有限自动机
NFA Mn=(?,S,s0,F,?)
?,S?? →2 S
例, ?={0,1} s0是初态
S={s0,s1,s2,s3,s4}
F={s2,s4}
?(s0,0)={s0,s3} ?(s0,1)={s0,s1}
?(s1,0)=? ?(s1,1)={s2}
?(s2,0)={s2} ?(s2,1)={s2}
?(s3,0)={s4} ?(s3,1)=?
?(s4,0)={s4} ?(s4,1)={s4}
二, 有限自动机的表示
1,状态转换矩阵
若 │S│= m,│?│=n
则可以用一个 m?n的矩阵表示 S??的状态
变换
S ? 0 1
s0
s1
s2
s3
s2 s1
s3 s0
s0 s3
s1 s2
DFA
F={s0}
S ?
s0
s1
s2
s3
s4
0 1
{s0,s3} {s0,s1}
?
?
{s2} {s2}
{s2}
{s4}
{s4} {s4}
NFA
F={s2,s4}
2,状态转换图
初态,
终态,
?:所有弧上字符的集合
?
s0 s1
s3 s2
? 1
1
1
1
0 0 0 0
DFA
s0 s4 ?
1
1
0 s3
s1
s2
0
0,1
NFA
0,1
0,1
三, 有限自动机识别的语言
1,有限自动机 FA M识别的串 α,
初态 s0至终态 f的某一道路上有向边的标记字
符依次连接所得的字符串恰为 α。
2,FA M所识别的语言,
FA M所识别的所有字符串的集合 。 即
L(M)={α│α??* and ?(s0,α)=f?F}
3,有限自动机的等价
if L(M1)=L(M2)
then FA M1和 FA M2等价
四, NFA和 DFA的关系
1,DFA和 NFA的区别在于状态转换函
数 ?的不同
2,DFA是一个特殊的 NFA
3,NFA和 DFA的等价性
定理 4.1 任一不确定的有限自动机 Mn,
它所识别的语言为 L(Mn)，则必然存在一
确定的有限自动机 DFA Md，它所识别的
语言 L(Md)恰为 L(Mn)，即 L(Md) =L(Mn)
第三节 正则表达式和正则集
?正则表达式与正则文法有相同的表达能
力, 两者是等价的 。
?词法结构 ?正则表达式 ?有限自动机
一, 正则表达式和正则集的定义
1,递归定义
对于给定的字母表 ?，有
（ 1） ?和 ?是 ?上的正则表达式，它们所表
示的正则集分别是 {?}和 {?}；
（ 2）对任一 a??,a是 ?上的正则表达式，
它所表示的正则集为 {a}；
（ 3）如果 R和 S是 ?上的正则表达式，它们所
表示的正则集分别为 L(R)和 L(S)，则
?(R|S)也是 ?上的正则表达式，它所表示
的正则集为 L(R)?L(S)；
?(R?S)也是 ?上的正则表达式，它所表示
的正则集为 L(R)L(S)；
?(R)*也是 ?上的正则表达式，它所表示的
正则集为 (L(R))*。
（ 4）仅有限次使用规则 (1),(2),(3)得到的
表达式，是 ?上的正则表达式，它所表示的集
合是 ?上的正则集。
2,有关运算
（ 1）,|”称为“或”
（ 2）,?”称为“连接”
（ 3）,*”称为“闭包”,,+”称为“正闭包”
（ 4）设 U,V是 ?*的子集，有
UV={??|??U & ??V}
Vn= VV…V
V0={?},V+ =V1?V2?V3?..,
V*=V0?V1?V2?..,
n次
例,ba*
a(a|b)*
(a|b)*(aa|bb)(a|b)*
(A|B)(A|B|0|1)*
(0|1)(0|1)*
二, 有限自动机与正则表达式
1,定理 4.2
设 R是 ?上的一个正则表达式，则存在一个
?上的 NFA M，使得 L(M)=L(R)；反之亦然。
2,正则表达式 ?NFA
i k j A B
i j AB 代之以
i j A|B 代之以
i j
A
B
i j A* 代之以
i k j ? ?
A
例, (a|b)*(aa|bb)(a|b)*
0 2 ? ? ? ?
a a a
b b
b
a
1
3
4
5 6 7
b
三, 正则文法和有限自动机
?每个非终结符对应一个状态,开始符对应初态
?另设一个终态 Z
?A?? 对应
?A??B 对应
A B
A Z ?
?
例, G(S)
S?0U|1V
U?1|1S
V?0|0S
S U
V Z
0
1
1
0
0
1
?
四, 正则表达式的应用
—— 词法分析器的自动生成
正则表达式
? NFA Mn
? DFA Md
?词法分析器
第四节 下推自动机
下推自动机 (简称为 PDA)是上下文无
关文法的识别器。一个下推自动机由一
条输入带,一个有限控制器和一个下推栈
组成
a1 ak $
zk
zk-1
z0
有限状态控制
一, 不确定的下推自动机
1,定义
M=(?,S,?,?,s0,z0,F)
??是一个有限输入字母表
?S为有限状态集
??为有限下推栈字母表,约定对于 ???*,?
的最左字符在栈顶,?=?时下推栈为空
?s0?S,为初态
?z0??,为下推栈的初始符号
?F?S,为终态集
??是状态转换函数,为 S?(??{?})??到 S??*的
一个子集间的映射,
?(s,a,z)={(si,?i)│i=1,2,…,n}
其中 s,si?S,a??,z??,?i??*,它表示在状态 s下,
输入字符为 a,下推栈栈顶符号为 z时,状态转
换为 si,下推栈将 z上托后,将 ?i下推入栈,同时
输入指针右移一位
2,特殊情况
—— 输入指针不变时的转换
δ(s0,ε,z)={(si,?i)|i=1,2,…,n}
3,瞬时状态及其转换
(s1,aw,z?)|— (s2,w,??) 一次移动
(s1,aw,z?)|— (s2,w,??) 0或多次移动
其中,s1,s2?S,a??,w??*,z??,?,???*
M
*
二, 下推自动机识别的语言
1,终态接受和空栈接受
设 (s0,w,z0)为初始瞬时状态, 有
(s0,w,z0) |— (s,ε,α)
?当 s?F时,称 w为 M终态接受
?当 α=ε时,称 w为 M空栈接受
*
2,终态接受语言
L(M)={w|(s0,w,z0)|— (s,?,α),s?F,α? ?*}
3,空栈接受语言
L?(M)={w|(s0,w,z0)|— (s,?,?),s?S}
此时,下推自动机记为 M?=(?,S,?,?,s0,z0,?)
*
*
三, 确定的下推自动机
下推自动机 M=(?,S,?,?,s0,z0,F)满足以
下两个条件之一,(瞬时状态的转换只有一
种可能 )
对任何 s?S,z??以及 a??,有
(1)?(s,?,z) = ?,或者 ?(s,a,z) 有唯一的元素 ;
(2)?(s,a,z) = ?,或者 ?(s,?,z) 有唯一的元素；
则 M是一确定的下推自动机。
四, 一些等价性定理
（ 1）终态 PDA和空栈 PDA的等价性。
（ 2）上下文无关文法和下推自动机的等
价性。
第五节 编译概述
一, 不同语言之间的翻译
1,翻译程序, 等价地变换
2,编译程序, 高级语言 ?低级语言
3,汇编程序, 汇编语言 ?机器语言
二, 编译执行和解释执行
1,编译执行
源程序 目标程序 计算结果
汇编语言程序 目标程序
2,解释执行,一边翻译一边解释执行
编译
编译
运行
汇编程序
初始数据
三, 编译程序的组成
1,词法分析, 输入字符串, 根据词法规则
识别出单词符号 。
2,语法分析, 根据语法规则, 将单词符号
构成各类语法单位, 并进行语法检查 。
3,语义分析与代码生成,
根据语义规则,进行初步编译 。
4,优化,对中间代码进行等价变换,以
使代码更有效 。
5,目标代码生成,生成机器语言程序
或汇编语言程序 。
6,符号表管理,完成符号表的建立,查
找,更新。
7,出错处理
源程序字符串
词法分析器
语法分析器
语义分析、中间代码生成器
代码优化器
目标代码生成器
单词流
语法单位
中间代码序列
中间代码序列
目标程序
符
号
表
管
理
程
序
出
错
处
理
程
序
编译程序的结构
