词法分析器的作用

词素(Lexeme)
词法单元(Token): Token-name + Attribute-value

词法单元的规约(正则表达式)

一些概念

字母表：一个有限的符号集合
串：字母表中符号组成的一个有穷序列
（相关术语：前缀，后缀，子串，真前缀，真后缀，真子串，子序列）
语言：给定字母表上一个任意的可数的串的集合
串的运算：连接(x=dog, y=house, xy=doghouse)，幂(x=dog, x^3=dogdogdog)
语言的运算：并，连接，Kleene闭包，正闭包

语言的运算

正则表达式

正则表达式的归纳
扩展运算符

词法单元的识别

状态转换图

状态(state)：表示在识别词素的过程中可能出现的情况
边(Edge)：从一个状态指向另一个状态

状态转换图的例子

有穷自动机

有穷自动机 等价于 状态转换图
区别在于：自动机是识别器，对输入串回答yes or no
分为两类：不确定的有穷自动机(Nondeterministic Finite Automate, NFA)
确定的有穷状态自动机(Deterministic Finite Automate, DFA)
区别：
NFA: 一个符号标记离开同一个状态的多条边
DFA: 对于每个状态和字母表中的每个字符，有且仅有一条离开该状态、以该符号为标号的边
NFA: 可以有边的标号是ε
DFA: 没有标号为ε的边
相同：都可以识别正则语言，两者之间存在等价性

词法分析器生成工具及设计