目的
词法分析的任务，就是输入源程序，对构成源程序的字符串进行扫描和分解，识别出单词符号。
怎么做呢？
根据构词规则，然后使用有限自动机来描述
几个概念
文法
文法是用来描述语言的语法成分结构构造的形式规则， 我们通常用G表示。
文法定义的形式-四元组（Vn,Vt,P,S）: Vn为非终结符集，Vt 为终结符集，P为规则集，S为识别符|开始符，至少要在一个规则中作为左部出现，Vn ∩ Vt = ∅。
乔姆斯基根据文法生成力不同而对正则语言做的分类，把文法分成4个层级，层级越高，规则越多，下面是四个类型：
具体四个类型之间的关系可以参考这个：文法分类
我们目前只需要知道：
¨0型（无限制文法）:
¨1型（上下文有关）:
¨ 2型（上下文无关）:
¨3型（右线性和正规文法）:
正规式（regular expression）
正规式是定义正规集的数学工具，是说明单词的模式(pattern)的一种表示法，用它描述单词符号时一般比正规文法更简洁。
- 正规式和正则表达式都是通过一定的语法规则来描述文法，但不是同一个概念。
- 正规式是一种用来描述正则语言的更紧凑的表示方法
- 正规式可以由较小的正规式按照特定规则递归地构建。每个正规式r定义（表示）一个语言，记为L（r）。
正规集
能用正规式或正规文法表示的集合称为正规集。
状态转换图
可以理解为状态转换图是词法分析程序的设计工具。
有限自动机
有限自动机是一种状态机，它以一串符号作为输入，并相应地改变其状态。有限自动机是正则表达式的识别器。当正则表达式字符串被输入到有限自动机中时，它会为每个文本更改其状态。如果输入字符串成功处理并且自动机达到其最终状态，则接受它，即刚刚输入的字符串被认为是当前语言的有效标记。
有限自动机是对状态图的形式化描述，有限自动机M由五元组（X,Y,S,δ,λ)
- X,Y是S的非空有限集
- X：输入集
- Y：输出集
- S：状态集合
- δ：笛卡尔积SxX到S的映射，也叫M的下一状态函数
- λ：SxY到Y的单值映射，也叫M的输出函数
- 有限自动机 = 内部状态集+控制规则
有限自动机分为两类
DFA 确定有限自动机
- 开始状态唯一
- 一个输入对应一个状态转换
NFA 不确定有限自动机
- 开始状态为一个状态集合
- 一个输入对应多个状态转换
- 有向弧的标记上可以为空
他们有什么关系？
正规文法和正规式等价
一个正规语言可用正规文法表示也可用正规式表示，两者具有等价性。通常正规式在描述语言时比正规文法更为简洁。
