# 编译原理：词法分析笔记

***

## 定义

词法分析是将源程序从左至右，逐个字符地扫描，然后产生一个个的单词符号，将源程序转换成单词符号。之后就可以根据单词符号做后续的分析。

## 单词

单词符号分为5类：

1. 标识符，如变量、数组、函数等，如`length`，`nextch`等；
2. 基本字，也叫保留字，如`if`，`while`等等；
3. 常数，如`3.1415926`；
4. 运算符，如`+`，`-`，`*`, `/`, `>=`, `!`, `==`, `&&`等；
5. 界符，如`;`,`(`.`)`,`:`等。

表示方法：

识别出的单词应该用二元式来表示，以便后续处理：（单词类别，单词属性）

> e.g.（标识符的编码，标识符的名称“i”）

## 正则表达式

设正则表达式`r`表示语言`L(r)`，则`L(r)`就是根据`r`的规则递归地定义的。

正则表达式简介书面地规定了一门语言。

归纳步骤：

* `(r) | (s)`：可选 r 或 s；
* `(r)(s)`：连接r和s；
* `(r)*`：称为Kleene闭包，也就是将L连接0次或多次后得到的串集；
* `(r)`：括号不影响其所表示的语言。

> e.g.
>
> `（a | b）*` == `(a*b*)*`，都表示由任意个a和b组成的串，如空串ε、a、ab、ba、baba等。

## 有限状态自动机

有限状态自动机用具体程序的方式实现了正则表达式的匹配。

有限状态机有一系列有限状态的集合和一些从一个状态通往另一个状态的边，其中一个状态是初态，某些状态是终态。

有限状态自动机分为两类：

1. 不确定的有限状态自动机，英文简写NFA。其对边上的标号没有限制，可以以空串ε作为标号，一个符号也可以标记离开同一个状态的多条边（可以有多个同标号的出边，所谓不确定具体去哪个状态）。
2. 确定的有限状态自动机，DFA，有且仅有一条以某符号为标号的离开该状态的边。

DFA是NFA的一个特例，它没有对输入ε的转换动作，且对于状态s和输入符号a，有且只有一条标号为a的边离开s。

DFA的例子：

![](https://ask.qcloudimg.com/developer-images/article-audit/7175224/q9masxhpy3.png?imageView2/2/w/1620)

NFA的例子：![](https://ask.qcloudimg.com/developer-images/article-audit/7175224/fqctwl82ab.png?imageView2/2/w/1620)

## NFA的确定化

由于NFA在转移时具有不同的可能性，所以在具体实现的运行时往往效率较低，因此需要一种方法将NFA转化为确定的DFA。

### 三个重要的操作（概念）：

* 状态集的空闭包集合（ε-闭包）：

若`I`是一个状态集合，其空闭包集合就是`I`中从任意元素出发经过**任意**条ε弧（标号为ε的边）能到达的状态的集合，记为`ε-closure(I)`；

* 状态集的a弧转换：

`I`中的任意状态经过**一条**a弧能到达的所有状态的集合，记为`move(I,a)`；

* 状态集的a弧转换的闭包`Ia`：

就是状态集I的a弧转换的ε闭包，即

$$I\_a = ε-closure(move(I,a))$$

### 确定化的步骤

#### 第一步：规则转换

将NFA转换成标准形式：

![](https://ask.qcloudimg.com/developer-images/article-audit/7175224/965r4x1qdv.png?imageView2/2/w/1620)

#### 第二步：状态合并

为了确定化DFA，我们需要从初态开始，根据ε-闭包将闭包内的状态合并为一个新的状态，然后根据\*（输入的字符）弧转换引出新的状态，直到全部状态都已转换完成。

实例：原来的NFA：

![img](https://ask.qcloudimg.com/developer-images/article-audit/7175224/1iznu3hlfi.png?imageView2/2/w/1620)

首先求初状态的ε-闭包，即{i,1,2}，作为初始集合S；

求出S的a弧、b弧转换的ε-闭包，即Ia、Ib，得到新状态A、B：

A = {1,2,3}，B={1,2,4}

以此类推，求出新状态的的a弧、b弧转换的ε-闭包，直至不再产生新状态（新集合）为止。一般做法是列出列为I、Ia、Ib的表格，每个新状态开一行；每个产生的新集合（状态）都要再去求Ia和Ib，直到不产生新状态（产生表的新行）为止。接下来只需要根据表合并新状态，然后构造DFA即可。

![img](https://ask.qcloudimg.com/developer-images/article-audit/7175224/j2s4rgf6kb.png?imageView2/2/w/1620)

这样就完成了NFA到DFA的等价转化。其中产生新状态和求\*弧转换的表，称为Dtran表。

### NFA确定化实例：

NFA：

![](https://i.328888.xyz/2023/02/15/mXQmt.png)

列表：

![](https://i.328888.xyz/2023/02/15/mgCdk.png)

合并状态：

![](https://i.328888.xyz/2023/02/15/mg22p.png)

根据表构造DFA：[![mgcuH.png](https://i.328888.xyz/2023/02/15/mgcuH.png)](https://imgloc.com/i/mgcuH)

> 参考：[编译原理学习笔记-3：词法分析(一)基本过程、正规式和有限自动机 - 腾讯云开发者社区-腾讯云 (tencent.com)](https://cloud.tencent.com/developer/article/1613187)