词法分析与有限状态自动机.ppt

2018/4/17
华东师大计算机科学技术系
1
第三章词法分析与有限状态自动机
词法分析程序的主要功能是识别单词,这将涉及3型文法、正则表达式和有限状态自动机。本章将讨论这三者间的关系。
有限状态自动机(Finite-state Automate machine FA)
2018/4/17
华东师大计算机科学技术系
2
有限状态自动机
基本概念
FA的非形式描述
有限状态自动机由3部分组成:
⑴一根输入带:输入带可以理解成由一系列带块组成,每个带块上只含有一个输入符号(终结符号),其全体构成集合VT,特殊符号“”表示输入符号串的结束,VT。
⑵一个输入头:初始时,输入头指向第一个带块(即指向输入带最左端的带块),输入头每次将输入头下方带块上的输入符号读入,然后输入头向右移动一个带块。
2018/4/17
华东师大计算机科学技术系
3
基本概念
⑶一个有限状态控制器:有限状态控制器所能处于的状态的全体组成状态集合Q,Q中有若干特殊状态:一个初始状态q0和若干最终状态qf。开始时有限状态控制器处于初始状态,以后有限状态控制器所处状态由状态转换函数决定。
2018/4/17
华东师大计算机科学技术系
4
基本概念
例1 令VT={0,1,2,3} Q={S,A,B}
2
0
3
0

S是初态
用‘-’表示
A是终态
用‘+’表示
有向弧表示转换
2018/4/17
华东师大计算机科学技术系
5
FA的工作过程
初始时,FA处于初态,输入头指向第一个输入符,随着带上符号的读入,FA从一个状态转向另一个状态。若遇到如下情况,FA结束工作:
输入头指向‘’、 FA处于终态。称输入串被FA接受。(如2030 )
输入头指向‘’、 FA不在终态。称输入串不被FA接受。(如203 )
FA无法转换。称输入串不被FA接受。(如1031 )
2018/4/17
华东师大计算机科学技术系
6
FA的形式描述
定义1:有限状态自动机M是一个五元组:
M=(VT,Q, ,q0,Qf),其中:
VT:有限非空终结符集合
Q: 有限非空状态集合
: 从Q×VT到Q的幂集2Q上的状态转换函数
q0:初始状态,q0Q
Qf:最终状态集,Qf  Q |Qf|≥1
2018/4/17
华东师大计算机科学技术系
7
FA的形式描述
对q, q1 Q a VT (q,a)={q1}的含义为:当前状态为q,若输入头所指符号为a,则转向下一状态q1,输入头右移。
∵是Q×VT 2Q上的一个单射
一般地(q,a)={q1,q2,……qn} qi Q i=1,2,…n
因此称FA M为不确定的FA,记为NFA。
若映射是Q×VT Q,即对任何qQ,ai VT,(q,ai)至多只有一个元素q’,称FA M是确定性的FA,记为DFA。
2018/4/17
华东师大计算机科学技术系
8
FA的形式描述
对FA的拓展
Q0  Q |Q0|≥1 即初态可以是一个集合
: 从Q×VT*到2Q上的单值映射,即输入符可以是一个串,包括
称M为一个传递图或转换系统或NFA。
例1:M1= (VT,Q, ,q0,F)
VT={a,b}, Q={q0,q1,q2} F={q2}
: (q0,a)=q1 (q0,b)=q2 (q1,a)=q1
(q1,b)=q1 (q2,a)=q2 (q2,b)=q1
M1是一个DFA。
2018/4/17
华东师大计算机科学技术系
9
FA的表示
状态转换图和状态转换表
状态转换图:
q Q
若q,q’Q,aVT,且q’(q,a),
初态用‘-’标记、终态用‘+’标记
q
q
q’
a
2018/4/17
华东师大计算机科学技术系
10
状态转换图
例2:例1的DFA M1可表示为:
—
+
q0
q2
q1
a
b
b
a
a,b