1. 有穷自动机(Finite Automata)
有穷自动机是对一类处理系统建立的数学模型.
这类系统具有一系列离散的输入输出信息和又穷数目的内部状态.
系统只需要根据当前状态和面临的输入信息就可以决定系统的后继行为.系统处理了当前的输入后,内部状态也发生改变,
(1). FA转换图
图中的结点为有穷自动机的状态.初始状态为start箭头指向的结点(也可使用双箭头).终止状态为双圈结点.
带标记的有向边:下图表示Aa -> B (A表示1状态, B表示2状态)
状态图????
[图片上传失败...(image-4529f1-1582632388456)]
由一个有穷自动机M接收的所有串构成 的集合成为是该FA定义的语言,记为L(M).
(2). 最长子串匹配原则
当输入串的前缀与多个终态匹配成功时,总是选择最长的前缀进行匹配.
带到达某个终态后,只要输入带上还有符号,有穷自动机就会继续前进,直到内部状态不会改变为止.
2. 有穷自动机的分类
有穷自动机分为两类:确定的有穷自动机(DFA)和非确定的有穷自动机(NFA).
DFA和NFA可以识别相同的语言.
(1). 确定的有穷自动机(DFA)
M = ( S, Σ, δ, s0, F )
S:有穷状态集 ( 0, 1, 2, 3 )
Σ:输入字母表 ( a, b )
δ:转换函数 ( f(0, a)=1, f(0, b)=0, f(1, a)=1, f(1, b)=2, f(2, a)=1, f(2, b)=3, f(3, a)=1, f(3, b)=0 )
s0:开始状态, s0 ∈ S ( 0 )
F:终止状态集合, F ⊆ S ( 3 )
[图片上传失败...(image-c2428d-1582632388456)]
(2). 非确定的有穷自动机(NFA)
和确定的有穷自动机的区别在于转换函数.这里的转换函数表示一个状态遇到一个输入的所有结果的集和(意味着一个状态遇到相同的输入可能有不同的结果)
下图的 f(0, a) 就有两种结果,0和1.
[图片上传失败...(image-1af8e8-1582632388456)]
(3). NFA和DFA的区别
NFA对某一输入可以有0-多个到达状态，DFA只能有一个到达状态
NFA可以有ε边，DFA的边只能是字母表上的
-
NFA可以有多个开始状态，DFA只能有一个开始状态
可以看出，DFA是NFA的一种特例。并且可以证明，对于每个NFA M存在一个DFA M’使得 L(M)=L(M’)。
3. 从正则表达式到有穷自动机
任何正则表达式都能转化为NFA和DFA,但通常DFA难以理解,而NFA更直观.所以往往都是将RE(正则表达式)先转化为NFA,然后通过固定的算法转化为DFA.
(1). RE ---> NFA
[图片上传失败...(image-a13745-1582632388456)]
[图片上传失败...(image-ba5838-1582632388456)]
(2). NFA ---> DFA
既然NFA中每一个输入都可能让有穷自动机改变为多个不同的状态,那么把这些状态的集合看做一个状态,就可以认为一个输入让有穷自动机做出了唯一的改变,也就转化为了DFA.
[图片上传失败...(image-c656b-1582632388456)]
(3). 三个重要运算
1). 状态集的ε-闭包
状态集中的任意状态S和S通过任意条ε边能达到的所有状态的集合.
状态集I的ε-闭包表示为ε-closure(I)
2). 状态集的a弧转换
状态集中的任意状态S经过一条a弧能达到的所有状态的集合.
状态集I的a弧转换表示为move(I, a)
3). 状态集的a弧转换的闭包
之前两个运算的复合.
Ia = ε-closure(move(I, a))
(4). 子集构造法
新的节点:当前节点状态集中的任意状态经过a弧后所达到的所有状态的集合(包括通过ε)
[图片上传失败...(image-dc0e1d-1582632388456)]
(5). 对错误的处理
1). 词法错误检测
如果当前状态与输入的符号没有办法匹配,则报错,调用错误处理程序.
2). 错误处理
查找已经扫描的字符串中最后一个对应于一个终态的字符,如果找到了,退回.如果没有找到,则证明真的出了错,采用错误恢复策略.
3). 错误恢复策略
恐慌模式:
从剩余的输入中不断删除字符,直到词法分析器能从剩余的开头中发现一个正确的字符为止.?????
