| 语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言规定的基本字符集∑（字母表）上的字符串的一个子集，称为正规集。
|
|
|
|
|
| 对于字母表∑，其上的正规式及其表示的正规集可以递归定义如下：
|
|
|
| （1）ε是一个正规式，它表示集合L（ε）=｛ε｝。
|
|
|
| （2）若a是∑上的字符，则a是一个正规式，它所表示的正规集为｛a｝。
|
|
|
| （3）若正规式r和s分别表示正规集L（r）和L（s），则：
|
|
|
|
|
|
|
|
|
|
|
| 仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式，其中运算符“｜”“.”“*”分别称为“或”“连接”“闭包”。在正规式的书写中，连接运算符“.”可省略。运算符的优先级从高到低顺序排列为“*”“.”“｜”。
|
|
|
| 设∑=｛a，b｝，下表列出了∑上的一些正规式和相应的正规集。
|
|
|
|
|
|
|
| 若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如，b（ab）*=（ba）*b，（a｜b）*=（a*b*）*。设U、V和W均为正规式，正规式的代数性质如下表所示。
|
|
|
|
|
|
|
|
|
| 有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为确定的有限自动机和不确定的有限自动机两类。
|
|
|
| （1）确定的有限自动机（Deterministic Finite Automata，DFA）。一个确定的有限自动机是一个五元组（S，Σ，f，s0，Z），其中：
|
|
|
|
|
| .Σ是一个有穷字母表，其每个元素称为一个输入字符。
|
|
|
| .f是S×Σ→S上的单值部分映像。f（A，a）=Q表示当前状态为A、输入为a时，将转换到下一状态Q。称Q为A的一个后继状态。
|
|
|
|
|
.Z是非空的终止状态集合， 。
|
|
|
| 一个DFA可以用两种直观的方式表示：状态转换图和状态转换矩阵。状态转换图简称为转换图，是一个有向图。DFA中的每个状态对应转换图中的一个节点，DFA中的每个转换函数对应图中的一条有向弧，若转换函数为f（A，a）=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。
|
|
|
| （2）不确定的有限自动机（Nondeterministic Finite Automata，NFA）。一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别如下：
|
|
|
| ①f是S×Σ→2S上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一的。
|
|
|
|
|
|
|
| 任何一个NFA都可以转换为DFA，下面先定义转换过程中需要的计算。
|
|
|
|
|
| 若I是NFAN的状态集合的一个子集，定义ε_CLOSURE（I）如下：
|
|
|
| .状态集I的ε_CLOSURE（I）是一个状态集。
|
|
|
| .状态集I的所有状态属于ε_CLOSURE（I）。
|
|
|
| .若s∈I，那么从s出发经过任意条ε弧到达的状态s'都属于ε_CLOSURE（I）。
|
|
|
|
|
| 由以上的定义可知，I的ε_闭包就是从状态集I的状态出发，经ε所能到达的状态的全体。
|
|
|
|
|
| 假定I是NFAN的状态集的一个子集，a是Σ中的一个字符，定义：
|
|
|
|
|
| 其中，J是所有那些可从I中的某一状态节点出发经过一条a弧而到达的状态节点的全体。
|
|
|
|
|
| 设NFAN=（S，Σ，f，s0，Z），与之等价的DFAM=（S'，Σ，f'，q0，Z'），用子集法将非确定的有限自动机确定化的算法步骤如下：
|
|
|
| ①求出DFAM的初态q0，即令q0=ε_CLOSURE（｛s0｝），此时S'仅含初态q0，并且没有标记。
|
|
|
| ②对于S'中尚未标记的状态qi=｛si1，si2，…，sim｝，sij∈S（j=1，…，m）进行以下处理：
|
|
|
|
|
| .对于每个a∈∑，令T=f（｛si1，si2，…，sim｝，a），qj=ε_CLOSURE（T）。
|
|
|
| .若qj尚不在S'中，则将qj作为一个未加标记的新状态添加到S'，并把状态转换函数f'（qi，a）=qj添加到DFAM中。
|
|
|
| ③重复进行步骤②，直到S'中不再出现未标记的状态时为止。
|
|
|
|
|
|
|
|
|
| 对上图所示的自动机进行化简所得的DFA如下图所示。
|
|
|
|
|
|
|
|
|
|
|
|
|
| 对于Σ上的NFAM，可以构造一个Σ上的正规式R，使得L（R）=L（M）。
|
|
|
| 拓广状态转换图的概念，令每条弧可用一个正规式作标记。为Σ上的NFAM构造相应的正规式R，分为如下两步：
|
|
|
| 第一步：在M的状态转换图中加两个节点，一个x节点，一个y节点。从x节点到NFAM的初始状态节点引一条弧并用ε标记，从NFAM的所有终态节点到y节点引一条弧并用ε标记。形成一个与M等价的M'，M'只有一个初态x和一个终态y。
|
|
|
| 第二步：按下面的方法逐步消去M'中除x和y的所有节点。在消除节点的过程中，用正规式来标记弧，最后节点x和y之间弧上的标记就是所求的正规式。消除节点的规则如下图所示。
|
|
|
|
|
|
|
|
|
| 同样地，对于Σ上的每个正规式R，可以构造一个Σ上的NFAM，使得L（M）=L（R）。
|
|
|
|
|
|
|
|
|
| ②通过对正规式R进行分裂并加入新的节点，逐步把图转变成每条弧上的标记是∑上的一个字符或ε，转换规则如下图所示。
|
|
|
|
|
|
|
| 最后所得的图即为一个NFAM，x为初态节点，y为终态节点。显然，L（M）=L（R）。
|
|
|
|
|
| 构造词法分析器的一般步骤为：用正规式描述语言中的单词构成规则；为每个正规式构造一个NFA，它识别正规式所表示的正规集；将构造出的NFA转换成等价的DFA；对DFA进行最小化处理，使其最简；最后用手工编码或表驱动的方式从最简DFA构造词法分析器。
|
|
|
