二、词法分析

从左到右扫描，产生一个个单词符号。词法分析一般作为语法分析的子程序。

单词符号的分类

• 保留字：比如C语言中的if，else等
• 标识符：用于标记常量、数组、类型、变量等
• 常数
• 运算符：+、-、*、/、<、>等
• 界符（分隔符）：分号，逗号等

一般用二元式作为输出单词的形式：
(单词种别，单词自身的值)
单词种别一般是一个整数码。

正规表达式与正规集

以一个例子来说明正规表达式：
标识符的定义是以字母开头的字母数字串，那么就可以表示为 letter(letter | digit)*
这就是标识符的正规表达式，简称正规式。
正规集就是用正规表达式所能生成的所有组合，设 R 为一个正规式，则 L( R ) 表示 R 的正规集。

有限自动机

如果学过AC自动机或者是字典树的话，会帮助理解有限自动机，因为二者的实现原理是类似的。
有限自动机分为确定有限自动机（DFA）和非确定有限自动机（NFA）
DFA和NFA的主要区别有两点：
1.DFA只有一个初始状态，而NFA可以有若干个初始状态
2.NFA的状态转换函数f不是单值函数，也就是说可以从一个结点通过相同的字符跳转到多个结点。
相同点：都可以用五元组来表示

DFA

表示方法为M_d = (S，Σ，f，s₀，Z)
S：有限状态集，每个元素为一个状态，罗列了所有会出现的字符
Σ：有穷输入字母表，每一个元素称为一个输入字符，跳转边上的字符从Σ中取
f：一个从 SxΣ 到 S 的单值映射，也就是跳转关系
s₀∈S：唯一的初始状态
Z⊂S：一个终态集

NFA

表示方法为M_n = (S，Σ，f，Q，Z)
与DFA不同的部分：
f：一个从 SxΣ* 到 S 的子集映射，SxΣ*表示可以通过空值进行跳转
Q⊂S：非空初态集

下面是DFA和NFA的转换图画法示例

由正规表达式到有限自动机的构造★ 构造非确定有限自动机

第一步：画出如图所示的拓广转换图

第二步：运用如下三条转换规则对拓广图进行扩展

书上的一个例子2.6：

NFA的确定化

每个NFA都能相应地构造出一个与之等价的DFA
我们采用子集法对其进行确定化，也就是将多个状态合并为DFA中的一个状态。
首先介绍一下ε_CLOSURE(I) ，这个表示从状态I经过若干条ε边所能到达的所有状态以及状态I自身的集合
那么同理 a_CLOSURE(I) 表示从状态I经过一条a边和若干条ε边所能到达的所有状态以及状态I自身的集合。可以简化为 I_a 表示。

书上的一个例子2.8：

对例2.6进行确定化：

由于画图比较复杂，略。