当前课程知识点：编译原理 > 第3章 词法分析 > 3.3 有限状态自动机 > 有限状态自动机
同学们
在我们生活的系统中呢
存在着不同的状态
这些状态可以说是系统的基本特征
譬如十字路口的红绿灯
就像孩子们的儿歌中
唱到的那样
交通灯 会说话
黄灯说 请注意
红灯说 快停下
绿灯说 请走吧
儿歌当中的注意 走和停
是我们过马路时候的状态
状态是可以将事物
区分开来的一种标识
离散状态系统当中的状态是有限的
在此基础上我们构建出
一种具有离散输入/输出
系统的数学模型
这就是有限状态自动机
自动机接收一定的输入
执行一定的动作
产生一定的结果
可以使用状态迁移
来描述整个工作过程
例如描述十字路口过马路的过程
在“停”的状态下
接收到了输入信号“绿灯”
状态就会迁移到“走”的状态
接下来我们对刚才“儿歌”当中的
状态转移进行物理建模
FA模型是由一条写有字符的输入带
一个读头和一个有限控制器构成
输入带上面存放的
是输入的符号串
读头可以从左向右
读取输入带上面的符号
但是不能修改
而且不能往返移动
有穷控制器拥有
有穷个状态数
根据当前的状态和当前读头
读取的输入符号
来控制自动机进入下一个状态
接下来我们给出
确定的有限状态自动机(DFA)
它的形式化定义
确定的有限状态自动机的形式化定义
包括五大要素
有限状态集Q
有限输入符号集T
转移函数
唯一的开始状态q0
还有一个终态的集合F
状态转移函数
表示的是
当前的状态qn下
如果遇到了输入符号t
那么状态会转移到qm
也就是说
在确定的有限状态自动机下
一个状态面临一个输入符号的时候
最多只能够转移到一个状态
有限状态自动机还可以用
状态转化图进行直观的描述
结点就是有限状态自动机的状态
除了普通状态之外
有两个特殊的状态
唯一的开始状态
由start箭头指向
还有就是可能多个的终止状态
用双圈来表示
如果对于输入a来说
存在一个从状态p到q的转换
那么就在p和q之间画一条有向边
并且标记为a
例如我们看到的
左边的对于DFA的定义
我们来看它的两种直观的表述
首先我们可以确定
有四个状态q0 q1 q2和q3
一个初始状态q0
两个终止状态q0和q3
两个输入分别是0和1
那么接下来我们根据
状态转移函数的定义
增添了从状态q0到q2标记为0的弧
从q0到q1标记为1的弧
从q1到q3标记为0的弧
从q1到q0标记为1的弧
从q2到q0标记为0的弧
从q2到q3标记为1的弧
从q3到q1标记为0的弧
以及从q3到q2标记为1的弧
一共是8条弧
同样 这个状态转移图
也可以用状态转移矩阵来表示
下面我们就让有限状态自动机动起来
看看它究竟是如何接收语言的
给定一个符号串 t
如果存在一个对应于输入串 t
从初始状态到某个终止状态的
转换序列
我们就认为这个输入串 t
可以被有限状态自动机接收
由一个有穷自动机M接收的所有串
构成的集合就是
这个有穷状态自动机定义
或者接收的语言
我们记作L(M)
接下来我们就来探究一下
这个baab是否可以被
右边的这个有限状态自动机接收
我们可以套用刚才FA的物理模型
将baab首先放在输入带上去
而M就是状态转移控制器
一开始
初始状态是1号状态
读头下输入的字符是b
那么将停留在1号状态
接下来读头继续后移
读取到了符号a
状态转移到2号状态
读头继续后移
读取到的是a
状态将在2号状态停留一次
读头再次后移
读取到了b
此时状态转移到了3号状态
读头继续后移
此时读头获取到了
字符串的结束符号
读取字符的工作就结束了
而对于baab来说
我们发现的确存在一条
从1号的开始状态到3号终止状态
这样的一个转化序列
baab是可以被M接收的
我们也不难发现
M接收的字符串
有这样的一个特点
就是以“ab”结尾
既然有限状态自动机
可以接受特殊描述的单词
那么反过来
我们也可以为不同种类的单词
譬如关键字 标识符
复合运算符 界符 常数等等
去构建对应的有限状态自动机
那么我们就来实践一下
构造能够识别C语言中
关键字then的有限状态自动机
从没有识别到新的单词的
初始状态开始
在扫描源程序字符流的过程中
在不断的接收字符
进入到了不同的识别状态
分别进入到了识别字符串
“t”“th”“the”“then”的状态
那么在接收到了“then”的状态
究竟扫描到的“then”
属于关键字
还是只是标识符的一部分
取决于在这个状态下面
扫描到了什么
如果并没有扫描到的数字
或者是字符的话
我们便成功的扫描到了
关键字“then”
否则 我们只是获取到了
标识符的一部分
在刚才我们对有限状态自动机的讨论当中
我们从实际生活的状态系统当中
发现有限状态自动机的本质
就是状态的转移
接着我们给出了FA的形式化定义
并且对这种状态的转移机制
进行了物理建模
而且还用两种非常直观的方式
描绘了确定的有限状态自动机
也解析了DFA识别单词的过程
还构建了识别C语言中
一个关键字then的DFA
不过我们目前所看到的
状态转换都是唯一的
但是在我们生活当中
会碰到这样的情况
比如说现在有个小朋友她正在哭
我们给了她一块糖
她可能继续哭
也可能会止住哭声
同样输入的是“一块糖”
却转移到了不同的状态
那么大家下去之后
可以思考一下
状态的转移是否是唯一的呢
碰到这类情况
我们应该怎样处理
下一节课我们将为大家来分析
不确定的有限状态自动机
这节课就到这里
谢谢大家
-1.1 什么是编译原理
--什么是编译原理
--什么是编译程序
--讨论：翻译程序、汇编程序、编译程序、解释程序的区别和联系。
--练习1
-1.2 编译的基本过程
--编译的基本过程
--编译的基本过程
--练习2
-1.3 编译程序的组织
--编译程序的组织
--编译程序的组织
--练习3
-编译原理概述
-2.1 文法与语言
--文法与语言
--文法与语言
-2.2 文法和语言的形式定义
--练习1
-2.3 文法的类型
--文法的类型
--文法的类型
--练习2
-2.4 上下文无关文法及语法树
--练习3
-2.5 上下文无关文法的句型分析
--练习4
-编译理论基础作业
-3.1 词法分析概述
--词法分析概述
--词法分析概述
--练习1
-3.2 正规文法和状态转换图
--练习2
-3.3 有限状态自动机
--有限状态自动机
--有限状态自动机
--练习3
-3.4 NFA与DFA的等价性
--练习4
-3.5 正规表达式与正规集
--练习5
-3.6 正规文法与正规式
--正规文法与正规式
--正规文法与正规式
--练习6
-3.7 正规式与FA
--正规式与FA
--正规式与FA
--练习7
-词法分析作业
-4.1 自顶向下语法分析及其面临的问题
--练习1
-4.2 文法的等价转化
--文法的等价转化
--文法的等价转化
--练习2
-4.3 LL(1)文法与递归下降分析法
--练习3
-4.4 构建FIRST集合FOLLOW集合
--练习4
-4.5 LL(1)分析器工作原理
-- LL(1)分析器工作原理
-4.6 LL(1)分析表构造算法
--练习5
-5.1 自底向上的语法分析及优先分析
--练习1
-5.2 LR分析器
--LR分析器
--LR分析器
--练习2
-5.3 活前缀和LR(0)项目
-- 活前缀和LR(0)项目
--练习3
-5.4 构造识别活前缀的FA
--练习4
-5.5 LR(0)分析表构造算法
--练习5
-5.6 SLR(1)分析法
--练习6
-5.7 LR(1)分析法与LALR分析法
--练习7
-6.1 语义分析和语法制导翻译概述
--练习1
-6.2 常见中间语言简介
--常见中间语言简介
--常见中间语言简介
--练习2
-6.3 简单算术表达式和赋值语句翻译
--练习3
-6.4 布尔表达式和复制语句翻译
-6.5 拉链和回填
--拉链与回填
--拉链与回填
--练习4
-6.6 程序控制语句翻译
--程序控制语句翻译
--程序控制语句翻译
--练习5
-6.7 for循环语句的翻译
-6.8 GOTO语句和情况语句的翻译
--练习6
-6.9 含数组元素的算术表达式的翻译
--练习7
-6.10 数组元素赋值语句的翻译
--练习8
-7.1 符号表概述
--符号表概述
--符号表概述
--练习1
-7.2 符号表的建立
--符号表的建立
-- 符号表的建立
--练习2
-8.1 运行时存储空间组织概述
-8.2 运行时分配策略
--运行时分配策略
--运行时分配策略
--练习
-9.1 线性窥孔优化
--线性窥孔优化
--线性窥孔优化
-9.2 基本块及其优化方法
-9.3 循环概念
--循环概念
--循环概念
-9.4 循环优化
--循环优化
--循环优化
-代码优化作业
