# 第三章 词法分析

> 简而言之，词法分析的任务就是从左到右逐个字符的对源程序进行扫描，产生一个个的单词符号

## 1. 对于词法分析器的要求

**功能：**&#x8F93;入源程序，输出单词符号

**单词符号的种类：**

* 基本字：begin、repeat
* 标识符：变量名、数组名、过程名
* 常数
* 运算符：+、-、\*、/、...
* 界符：逗号、分号、括号、空格

**输出单词的形式：**（单词种别，单词自身的值）

* **单词种别**通常用**整数编码**表示
  * 一码一符：**基本字**、**运算符**、**界符。**&#x5982;：（while，-）
  * 多码一符：**标识符**、**常数。**&#x5982;：（id，100）

**注：词法分析器作为一个独立子程序，但是其处理不作为一遍。并非词法分析器一遍扫描源程序，然后将结果交给语法分析器。**

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99KzdrrZohHLv6UIru%2F-M99L0q133g5WDK6wA9e%2Fimage.png?alt=media\&token=063263d6-0836-465e-9de3-cd821196068b)

## 2. 词法分析器的设计

### **2.1 词法分析器的结构**

![词法分析器的结构](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99KzdrrZohHLv6UIru%2F-M99LUYdeI9y-MQSbV8d%2Fimage.png?alt=media\&token=224767f9-48ce-4556-8390-81357712f085)

### **2.2 输入、预处理**

**问题：**&#x53EF;能某一个单词长度超过了扫描缓冲区，多出缓冲区的部分只能重新加载到缓冲区中，会导致之前加入的内容丢失

**解决方法：**&#x4E24;个半区互补使用，单词的长度限制  = 半区的长度

### 2.3 单词符号的识别：超前搜索

**导致超前搜索的原因：**&#x7531;于语言规则不够严格，程序员可以把基本字当做标识符使用等，导致词法分析器需要去扫描到该代词的前面，才可以确定单词的种类。

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99N8LSFZPh3iyuio-N%2F-M99PQvyVQGmHhTy5HqM%2Fimage.png?alt=media\&token=9fb5b2e2-feee-4b85-9c83-cb34c3fb8dd6)

对于第一行需要扫描到**逗号**才可以确定 DO 是基本字；对于第二行需要扫描到**点**才可以确定DO99K是标识符

**几点限制就可以不必使用超前搜索**

* **所有基本字都是保留字**；用户不能用它们作为标识符
* **基本字作为特殊的标识符来处理**，使用保留字表
* 基本字、标识符和常数（或标号）之间没有确定的运算符或界符作为间隔，则必须**使用一个空格作为间隔**

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99N8LSFZPh3iyuio-N%2F-M99QoiXvUMLB--FaI6T%2Fimage.png?alt=media\&token=e9d816f5-7f32-407a-89cd-564e2b6d3aba)

### 2.4 状态转换图

**状态转换图是一张有限方向图**

* **结点**代表状态，用圆圈表示
* 状态之间用**箭弧**连接，箭弧上的标记（字符）代表射出该状态下可能出现的输入字符或者字符类
* 一张转换图只包含**有限个状态**，其中有一个为**初态**，**至少要有一个终态**
* <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99W_hWpMJFRlWYnowO%2F-M99X1uNBunaBI_BC4w8%2Fimage.png?alt=media&#x26;token=eb90f130-ee53-4118-a2d9-2a26ade96518" alt="" data-size="original">&#x20;

**状态转换图可用于识别（接收）一定的字符串**

* 若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记付连接成的字（串）等于 $$\alpha$$ ，则称 $$\alpha$$ 为该状态转换图所识别（接收）
* 识别标识符的状态转换图：<img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99W_hWpMJFRlWYnowO%2F-M99YkENjET0wH_EfBT-%2Fimage.png?alt=media&#x26;token=64984f59-55e2-4716-b68c-02250bec99da" alt="" data-size="original">&#x20;
* 识别整数的状态转换图：<img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99W_hWpMJFRlWYnowO%2F-M99YQta7j2ayCWedyxF%2Fimage.png?alt=media&#x26;token=c086bdbb-a0e0-4b16-be88-1f61ced2ac6a" alt="" data-size="original">&#x20;
* **注：终态上一个 \* 代表到达终态时回退一个字符**

### 2.5 词法分析器的示例

**助记符：**&#x76F4;接用编码表示不便于记忆，因此用助记符来表示编码

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99aFNvzr6j6lJGMcey%2F-M99amfe7vKlXfKsNCJm%2Fimage.png?alt=media\&token=7e983ece-3498-4fad-920a-3bd1f4978e12)

**状态转换图的实现**

思想：每个状态结点对应一小段程序

具体方法：

1.  对**不含回路的分叉结点**，可用一组`IF-THEN-ELSE`语句实现

    <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99aFNvzr6j6lJGMcey%2F-M99bvM9E7rQVuNj0kW6%2Fimage.png?alt=media&#x26;token=422510c9-2473-48fd-8d8a-31eabc8d1d1a" alt="" data-size="original">&#x20;

    ```c
    GetChar( );
    if (IsLetter( ))
        {… 状态 j 的对应程序段… ;}
    else if (IsDigit( ))
        {… 状态 k 的对应程序段… ;}
    else if (ch=‘/’)
        {… 状态 l 的对应程序段… ;}
    else
        {… 错误处理… ;}
    ```
2.  对**含回路的状态结点**，可对应一段由 `WHILE` 结构和 `IF` 语句构成的程序

    <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99aFNvzr6j6lJGMcey%2F-M99dKZCAdv4wTyfDzjN%2Fimage.png?alt=media&#x26;token=2fec6b79-2c06-49bd-a0e0-c2b754dfe36d" alt="" data-size="original">&#x20;

    ```c
    GetChar( );
    while (IsLetter( )or IsDigit( ))
        GetChar( );
    … 状态 j 的对应程序段…
    ```
3. **终态结点**表示识别出某种单词符号 `RETURN(C, VAL)`&#x20;

缺点：利用`WHILE`结构和`IF`语句列出所有情况，进行处理，这种方法一点都不灵活

**状态转换图的代码一般化**

* 变量 `curState` 用于保存现有的状态
* 用二维数组表示：`stateTrans[state][char]`&#x20;

```c
curState = 初态GetChar();
GetChar();
while( stateTrans[curState][ch] 有定义){
    //存在后继状态，读入、拼接
    Concat();
    //转换入下一状态，读入下一字符
    curState= stateTrans[curState][ch];
    if cur_state是终态 then 返回 strToken中的单词
    GetChar( );
}
```

## 3. 正规表达式与有限自动机

> 通过介绍词法分析器的设计和代码实现，发现不难，但是很繁琐，很多步骤都是有规律的，所以是否有方法可以自动产生词法分析程序！

### 3.1 正规式和正规集

* **正规集**可以用**正规表达式**（简称**正规式**）表示
* 正规式是表示正规集的一种方法
* 一个字集合是正规集，当且仅当它可以用正规式表示

> 一句话总结：**正规式**是抽象出的规则，**正规集**是根据正规式具体实现的集合
>
> 例如：正规式：x + 1（x 为 整数）；正规集：所有整数加一的式子构成的集合

递归定义

1. $$\epsilon$$ 和 $$\phi$$ 都是 $$\sum$$ 上的正规式，他们所表示的正规集为 $$\{ \epsilon \}$$ 和 $$\phi$$&#x20;
2. 任何 $$a \in \sum$$ ， $$a$$ 是 $$\sum$$ 上的正规式，它所表示的正规集为 $$\{ a \}$$&#x20;
3.  假定 $$e_1$$ 和 $$e_2$$ 都是 $$\sum$$ 上的正规式，他们所表示的正规集为 $$L(e_1)$$ 和 $$L(e_2)$$ ，则：

    * $$(e_1 \mid e_2)$$ 为正规式，正规集为 $$L(e_1)\bigcup L(e_2)$$&#x20;
    * $$(e_1 \cdot e_2)$$ 为正规式，正规集为 $$L(e_1) L(e_2)$$&#x20;
    * $$(e_1)^*$$ 为正规式，正规集为 $$(L(e_1))^*$$&#x20;

    仅由**有限次**使用上述三步骤而定义的表达式才是 $$\sum$$ 上的正规式，仅有这些正规式表示的字集才是 $$\sum$$ 上的正规集

等价变形

* 交换律： $$e_1 \mid e_2 = e_2 \mid e_1$$&#x20;
* 结合律： $$e_1 \mid (e_2 \mid e_3) = (e_1 \mid e_2) \mid e_3$$&#x20;
* 结合律： $$e_1  (e_2  e_3) = (e_1  e_2 ) e_3$$&#x20;
* 分配率： $$e_1 \mid (e_2 \mid e_3) = e_1e_2 \mid e_1 e_3$$&#x20;
* 分配率： $$(e_1 \mid e_2) \mid e_3 = e_1e_3 \mid e_2 e_3$$&#x20;
* $$e\epsilon = \epsilon e = e$$&#x20;
* $$e_1e_2 <> e_2e_1$$&#x20;

### 3.2 确定有限自动机（DFA）

确定有限自动机是**对状态转化图进行形式化表达**

$$(DFA)M = (S, \sum, f, S_0, F)$$ 其中：

1. $$S$$ ：有穷**状态集**
2. $$\sum$$ ：输入**字母表**（有穷）
3. $$f$$ ：状态转移函数，单值部分映射， $$f(S, a) = S'$$，当前状态 $$S$$ ，输入字符 $$a$$ ，下一状态 $$S'$$&#x20;
4. $$S_0 \in S$$ 是**唯一**的一个**初态**
5. $$F \subseteq S$$ ：终态集（**可空**）

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99svswGwx0gesvr1-3%2F-M9ChCU3L8fWqMqAIEDm%2Fimage.png?alt=media\&token=997a842d-6f83-4e98-9aec-26463417872b)

### 3.3 非确定有限自动机（NFA）

$$(NFA)M = (S, \sum, f, S_0, F)$$ 其中：

1. $$S$$ ：有穷**状态集**
2. $$\sum$$ ：输入**字母表**（有穷）
3. $$f$$ ：状态转移函数，单值部分映射， $$f(S, a) = S'$$，通过输入相同的字符 $$a$$ ，下一状态可能会有多个
4. $$S_0 \in S$$ 非空**初态集合**
5. $$F \subseteq S$$ ：终态集（**可空**）

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M99svswGwx0gesvr1-3%2F-M9CiBODo-SV-mkABvW9%2Fimage.png?alt=media\&token=507aed89-7baf-4499-a7c1-f885015a9210)

### **3.4 DFA 和 NFA 的关系**

**区别：**

1. DFA 只有**一个**初态；NFA可以有**多个**初态
2. DFA 的弧上只能是一个**字符**；NFA 弧上的标记可以是 $$\sum ^*$$ 中的一个**字**（甚至是一个正规式）
3. DFA 的一个状态通过一个字符只能到达**唯一的下个状态**；NFA 中一个状态可以通过同一个字到达多**个不同的下个状态**

**联系：**

1. DFA 是 NFA 的特例
2. 对于任何两个有限自动机 $$M$$ 和 $$M'$$ ，如果 $$L(M) = L(M')$$ ，则称 $$M$$ 与 $$M'$$等价
3. **重要结论：**&#x5224;定两个自动机等价性的算法存在
4. 对于每个NFA M 存在一个DFA M'，使得 $$L(M) = L(M')$$
5. DFA 与 NFA 描述能力相同！&#x20;
6. NFA：易于人工设计；DFA：易于计算机使用

### 3.5 NFA 转换为 DFA

1.  添加新初态结点 $$X$$ 和终态结点 $$Y$$ ， $$X,Y  \notin S$$ ，从 $$X$$ 到 $$S_0$$ 中任意状态结点连一条 $$\epsilon$$ 箭弧，从 $$F$$ 中任意状态结点连一条 $$\epsilon$$ 箭弧到 $$Y$$&#x20;

    <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9Cm4Mgdadk4Fr-HF9P%2F-M9CoAkbT8MzgG-K6mpn%2Fimage.png?alt=media&#x26;token=d29955f4-f0ef-4468-ac1b-589e3fe93aa3" alt="" data-size="original"> $$\longrightarrow$$ <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9Cm4Mgdadk4Fr-HF9P%2F-M9CodG_LOsahpvpfhqo%2Fimage.png?alt=media&#x26;token=9a899a74-b174-49eb-9bf3-ab89ffb5417c" alt="" data-size="original">&#x20;
2.  根据下面三条规则进行分裂，让箭弧上的标记变为单个字符

    * <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9Cm4Mgdadk4Fr-HF9P%2F-M9CpM_6uzOZukn82is4%2Fimage.png?alt=media&#x26;token=066173ae-83e3-4e80-906d-a441de18f305" alt="" data-size="original">&#x20;
    * <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9Cm4Mgdadk4Fr-HF9P%2F-M9CpTliOnHpmVUjq9LX%2Fimage.png?alt=media&#x26;token=91727085-ae11-44be-89a6-4a674ac79384" alt="" data-size="original">&#x20;
    * <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9Cm4Mgdadk4Fr-HF9P%2F-M9CpaXuhg_EJKoGeaZV%2Fimage.png?alt=media&#x26;token=eb84b219-6348-4544-a31a-0cc2b25746e1" alt="" data-size="original">&#x20;

    <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9Cm4Mgdadk4Fr-HF9P%2F-M9CodG_LOsahpvpfhqo%2Fimage.png?alt=media&#x26;token=9a899a74-b174-49eb-9bf3-ab89ffb5417c" alt="" data-size="original"> $$\longrightarrow$$ <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9Cm4Mgdadk4Fr-HF9P%2F-M9CpqUtSk04yioPUz6I%2Fimage.png?alt=media&#x26;token=7327ae21-5dbc-494c-b33d-08abe1aa29e6" alt="" data-size="original">&#x20;
3.  确定化：消除 $$\epsilon$$ 和下一状态唯一化（采用子集法）

    * 找出第一行第一列的 $$\epsilon - closure(\{X\})$$ ，并求出这一列的 $$I_a$$ 和 $$I_b$$&#x20;
    * 检查$$I_a$$ 和 $$I_b$$ 是否在表中的第一列出现，未曾出现的话，就加入第一列中进行计算
    * 重复上述过程，直至第二、三列的子集全部出现在第一列中为止



![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9CqQmpaPZiBzzFUtJb%2F-M9CtB3Eq_Z-Ak18mc6W%2Fimage.png?alt=media\&token=bbeb0dc8-a1bd-48ee-aebd-e81afbedc711)

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9CqQmpaPZiBzzFUtJb%2F-M9CtJdCP-sjxINQK3OY%2Fimage.png?alt=media\&token=c1d6d8de-9c0c-4af6-89f0-4220b0466fe6)

### 3.6 正规式与有限自动机的等价性

定理：

* 对任何FA M，都存在一个正规式 $$r$$ ，使得 $$L(r) = L(M)$$&#x20;
* 对任何正规式 $$r$$ ，都存在一个FA M ，使得 $$L(M) = L(r)$$&#x20;

### 3.7 NFA M 转化为 正规式 $$r$$&#x20;

1. 同 NFA 转化为 DFA 的第一步骤
2.  NFA 转化为 DFA 的第二步骤的逆过程

    <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9CqQmpaPZiBzzFUtJb%2F-M9Cv6UoZuuDmth1UgLJ%2Fimage.png?alt=media&#x26;token=c7d0c783-627b-497b-a48e-4456684420c9" alt="" data-size="original"> <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9CqQmpaPZiBzzFUtJb%2F-M9CvIrVZrBGHQqQaEQC%2Fimage.png?alt=media&#x26;token=b40a29ac-68f6-424e-9589-b467fc3926c8" alt="" data-size="original">&#x20;
3. 通过第二步骤可以将 NFA 的所有箭弧化成一条，即可得出正规式 $$r$$&#x20;

### 3.8 正规式 $$r$$ 转化为 NFA M&#x20;

1. <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9CqQmpaPZiBzzFUtJb%2F-M9CwKd5Dxcwp5-y7NMg%2Fimage.png?alt=media&#x26;token=4c2f5ebb-e8a4-4dca-88d6-3c34c1443571" alt="" data-size="original">&#x20;
2. <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9CqQmpaPZiBzzFUtJb%2F-M9CwSyhypw-N0dZkKFH%2Fimage.png?alt=media&#x26;token=f392be25-d99e-480a-a82d-ae5902bb2791" alt="" data-size="original">&#x20;
3. <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9Cm4Mgdadk4Fr-HF9P%2F-M9CpqUtSk04yioPUz6I%2Fimage.png?alt=media&#x26;token=7327ae21-5dbc-494c-b33d-08abe1aa29e6" alt="" data-size="original">&#x20;
4. 还可以通过子集法将NFA 转化为 DFA

### 3.9 确定有限自动机的化简

**两个状态等价：**&#x5982;果从状态 $$s$$ 出发能读出某个字 $$\alpha$$ 而停止于终态，那么同样，从 $$t$$ 出发也能读出 $$\alpha$$ 而停止于终态；反之亦然

**化简基本思想：**&#x628A; M 的状态集划分为一些不相交的子集，使得任何两个不同的子集的状态都是可区别的，而同一个子集的任何两个状态是等价的

第一步：首先划分为终态和非终态

第二步：对某个 $$I^{(i)}$$ ，令 $$I^{(i)} = \{ S_1, S_2, \cdots,S_k \}$$ ，若存在一个输入字符 $$a$$ 使得 $$I_a^{(i)}$$ 不会包含在现行 $$\pi$$ 的某个子集 $$I^{(j)}$$ 中，则至少应把 $$I^{(i)}$$ 分为两个部分。

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9CxAP68Pq8KL_eOgB_%2F-M9D0L9MsXLywBsEDo9i%2Fimage.png?alt=media\&token=d11b3371-467b-40af-a20b-76834353edb1)

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9CxAP68Pq8KL_eOgB_%2F-M9D1ukqUR1HtdCslHnJ%2Fimage.png?alt=media\&token=0254fd25-e7d0-43e7-83f3-5826cd8f1ed5)

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9CxAP68Pq8KL_eOgB_%2F-M9D2AkeSWuUb6d-FGop%2Fimage.png?alt=media\&token=2751077d-4b2e-400f-ba53-39ad328faf55)

### 3.10 正规文法

2型（上下文无关文法，非确定下推自动机）

* $$A \rightarrow \beta$$ ，其中 $$A \in V_N ; \beta \in (V_T \bigcup V_N)^*$$&#x20;

3型（正规文法，有限自动机）

* 右线性文法
  * $$A \rightarrow \alpha B 或者 A \rightarrow \alpha$$ ，其中 $$\alpha \in V_T^* ; A,B \in V_N$$&#x20;
* 左线性文法
  * $$A \rightarrow B\alpha 或者 A \rightarrow \alpha$$ ，其中 $$\alpha \in V_T^* ; A,B \in V_N$$&#x20;

### 3.11 正规文法与有限自动机的等价性

定理：

* 对每一个右线性正规文法 $$G$$ 和左线性正规文法 $$G$$ ，都存在一个有限自动机 (FA) M，使得 $$L(M) = L(G)$$&#x20;
* 对每一个FA M，都存在一个右线性正规文法 $$G_R$$ 和左线性正规文法 $$G_L$$ ，使得 $$L(M) = L(G_R) = L(G_L)$$&#x20;

### 3.12 正规文法 转化为 有限自动机

**右线性文法** $$\rightarrow$$ **有限自动机** （根据 A 经过 0 到达 B 的方法 连线）

<img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9D2K-Qg6GvuOy8uAgT%2F-M9DFWmsIOgRan6P8vOA%2Fimage.png?alt=media&#x26;token=af36f574-3448-4b3c-851c-d264c72d7d1f" alt="" data-size="original"> $$\rightarrow$$ <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9D2K-Qg6GvuOy8uAgT%2F-M9DFjII3WORzVRCqwv2%2Fimage.png?alt=media&#x26;token=f8b63dd8-0a98-46d5-83f6-1b0bcc1aa56c" alt="" data-size="original">&#x20;

**左线性文法** $$\rightarrow$$ **有限自动机** （根据 C 经过 0 到达 F 的方法 连线）

<img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9D2K-Qg6GvuOy8uAgT%2F-M9DGoG1DQj90ALpwmWS%2Fimage.png?alt=media&#x26;token=7872a04e-79e0-4628-9145-84618655ddac" alt="" data-size="original">  $$\rightarrow$$ <img src="https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9D2K-Qg6GvuOy8uAgT%2F-M9DGxNb-dODgTQSc0rz%2Fimage.png?alt=media&#x26;token=7a64c21c-c6fa-45f1-9e28-053d162298d7" alt="" data-size="original">&#x20;

### 3.13 总结

通过这一节所有的内容梳理了正规表达式、有限自动机之间的关系、联系和转换。

给出下面的图，一目了然

![](https://123904567-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9-HnMHifkICpaw8S2c%2F-M9D2K-Qg6GvuOy8uAgT%2F-M9DJuVVuX4RBSc0xkmE%2Fimage.png?alt=media\&token=fb7b132c-ea71-4c17-9710-0a36108ddb44)

## 4. 词法分析器的自动产生 -- LEX&#x20;

工作过程：

* 首先，对每条识别规则 $$P_i$$ 构造出一个相应的非确定有限自动机 $$M_i$$&#x20;
* 通过转化：NFA $$\rightarrow$$ DFA
* 化简 DFA

可见 LEX 的工作过程就是我们上面总结的相互转化，它大大简化了词法分析过程，程序员只需要把正规式或者正规文法输入到 LEX 中，即可以自动生成出最简化的 DFA
