词法分析
# 词法分析(lexical analysis)程序设计
逐个读入源程序字符并按照构词规则切分成一系列单词(Token)。
单词是语言中具有独立意义的最小单位，包括保留关键字、标识符、常量、运算符、标点符号、分界符等。
词法分析是编译过程中的一个阶段，在语法分析前进行 。也可和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
词法分析程序和语法分析程序的关系：
词类编码原则:
界符和运算符:一字一码
常数可统归一类，也可按类型（整型、实型、布尔型等），每个类型的常数划分成一类。一类一码。
所有的标识符分为一类。一类一码。
2
3
词法分析中如何识别单词
识别单词：逐个从源程序中读取字符，根据构成单词的词法规则拼成一个有意义的单词; 词法规则描述工具: (1)状态转换图 (2)巴克斯范式BNF (3)自动机DFA (4)正则(规)表达式(5)正则文法(3型文法); 本章节3.3-3.6将介绍以上5种描述工具及它们之间的等价性，如何互相转换，如何实现(lex);
# 单词的形式化描述工具
# 1.正规文法
# 2.正规式
正规式也称正则表达式,是描述单词的构成语法的有效工具，是定义正规集的数学工具。 正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），用以描述单词符号。
# 4.有穷自动机
有穷自动机作为一种单词识别器，能准确地识别正规集，即识别正规式所表示的集合。应用有穷自动机理论，为词法分析程序的自动构造寻找有效的方法和工具。
有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata, DFA)和不确定的有穷自动机(Nondeterministic Finite Automata, NFA) 。
# 4.1.确定的有穷自动机DFA
状态图：
DFA在计算机内部表示为一个矩阵数据结构：
例子：
DFA M所能接受的符号串的全体记为L(M).
# 4.2.不确定有穷自动机NFA
例子：
NFA状态集合I：
# 4.3.相互转换
# 子集法：
例子：
# 4.4.DFA的化简
例子：
# 最小状态DFA：
# 分割法：
把一个DFA的状态分成一些不相交的子集，不同子集的状态都是可区别的，同一子集中的任何两个状态都是等价的.
例子：
