文档介绍：2018/9/27
《编译原理与技术》讲义
1
编译原理与技术
词法分析(2)
2018/9/27
《编译原理与技术》讲义
2
有限自动机
有限自动机(Finite Automata-FA)是种更一般化的状态转换图。分为NFA和DFA。
词法分析器自动生成:
正规式 NFA DFA 词法程序
非确定有限自动机
确定的有限自动机
2018/9/27
《编译原理与技术》讲义
3
非确定有限自动机-NFA
NFA Mn 是一个五元组 Mn =(, S, S0,F,),
其中:
-有限字母表(输入符号集)
S-有限状态集
S0-非空初态集合,S0S
F-终态集合,F S
-状态转换函数,S x *  2S
2018/9/27
《编译原理与技术》讲义
4
确定的有限自动机-DFA
DFA Md 是一个五元组 Md =(, S, S0,F,),
其中:
, S, S0,F 同NFA中的定义,而定义如下:

:S x  S , 为一单值映射函数。
2018/9/27
《编译原理与技术》讲义
5
有限自动机的表示
1)状态转换图
开始状态
一般状态
终态
s
(s,a)=t
t
a
s
(s,)=t
t

2018/9/27
《编译原理与技术》讲义
6
有限自动机的表示
2)状态转换矩阵(表)
*
状态(集)
a
b
…
Si
{Sj}
…
Sj
…
…
(Si,a) = {Sj}
2018/9/27
《编译原理与技术》讲义
7
有限自动机的表示
NFA Mn =(, S, S0,F,),其中:
= { 0,1 } , 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}
2018/9/27
《编译原理与技术》讲义
8
有限自动机的表示
中NFA的状态转换图如下:
S0
S3
S1
0,1
0
0
0,1
1
1
0,1
S2
S4
2018/9/27
《编译原理与技术》讲义
9
有限自动机的表示
中NFA的状态转换矩阵(表)如下:
*
状态(集)
0
1
S0
{S0, S3 }
{S0, S1 }
S1
∅
{S2}
S2
{S2}
{S2}
S3
{S4}
∅
S4
{S4}
{S4}
2018/9/27
《编译原理与技术》讲义
10
有限自动机识别的语言
下面FA识别(接受)的串是什么?
S0
S1
S2
0
1
FA识别(接受)串∈* , 如果存在一个从FA的初态到某个终态的(状态)转换路径,该路径上所有标记的字符依次连接为。
FA M 所识别的语言 L(M)
L(M) = {| M 识别∈* }