自动有限状态机&实现简单分词器
date
May 27, 2021
slug
DFA-and-apply
status
Published
tags
编译原理
type
Post
summary
自动有限状态机&实现简单分词器
自动有限状态机
1 是啥
在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态)。
状态机是啥比如家门就是个状态机，有开门和关门两种状态什么叫有限状态机状态是有限的比如开门和关门是两种状态，不是无限状态
2. 分类
2.1 摩尔型
下一个状态时确定的
比如电视机的开或者关，下一个状态永远是确定的
2.2 米粒型
下一个状态不确定，根据输入会有变化
比如家里电视10个台，就是10种状态，这个变化和我的输入有关
我们编程主要用到米粒型的自动机
2.2.1 例子
这是判断是否字符串含有ab
上面两个太麻烦了，这样麻烦是因为状态太多了，所以该轮到自动机出场了！
首先还是要个循环
首先 start是个函数，其实是状态机，state就是状态，他俩都是函数，这个函数要返回下个状态，每个状态可以看成一个函数，因为我们做的是米粒型状态机，所以下个状态是不确定的
如果字符串c是a，那就返回下一个状态 foundB，否则就返回start，start是初始状态
如果字符串是a，就返回下个状态foundB，否则就返回start，start是初始状态，这里是根据c不同返回不同的状态，所以是米粒型的自动机，如果返回一个固定的，和c无关，就是摩尔型自动机
foundB也是个状态机
假设我们只找abc，找到就停止，那最后返回end就行了
end 是个摩尔型自动机
2.2.2 应用 ----尝试自己实现一个语言
要实现个语言的编译器，需要两步
分为前端和后端
- 前端
- 就是理解，我们写一大段代码，对计算机来说都是乱码，我们得先让计算机理解我们写的是啥
- 后端
- 生成机器码，性能优化
其实前端也分两步
- 首先要词法分析
- 其次要语法分析
词法分析：
- 就是分词，比如var a = 1，有一些比如var，比如 = ，比如1这样的东西，叫做终结符
- 终结符里面分为token和非token两部分
- 啥是token，就是大概有效输入的意思
- 哪些是token，除了空格，换行，注释都是
- 简单来讲，这个分词就是把代码分成数组，每个token都分开，并且标注这个token代表什么
比如var 是关键字， a是keyword
大概就是把代码传入一个函数，这个函数帮我分词
- token分为有效和无效
比如这种情况
这个就是无效token，因为 keyword不能以数字开头
（其实大部分语言都不拿数字开头，因为自动机实现起来麻烦，哈哈哈）
var 1 = 1 这个在分词阶段不会报错，因为这是语法错误，不是词法错误
2.2.3 小练习，实现分词的自动机
效果如下
