编译原理：词法分析

词法分析是编译环节的第一部分，编译器在这个阶段的任务是接受一个个的词（token）并判断是否合法，如果合法，则送入缓冲区中等待下一步的语法分析。

一、词法分析的任务

词法分析的主要工作就是识别源程序中的单词符号，输入是源程序、输出是单词符号

单词符号：

• 关键字
• 标识符
• 常数
• 运算符
• 界符

 

二、抽象模型：DFA 与 NFA

词法分析的抽象数学模型就是 DFA(Deterministic Finite Automaton) 和 NFA(Nondeterministic Finite Automaton)，是一种有限自动机，下面用 DFA做概念举例

1. 构成

• $Q$：状态集合
• $\Sigma$：字母表
• $\delta$：迁移函数

  描述从状态 q_n 接受字符 x 后变为状态 q_m 的过程，表示成为：$\delta(q_n, x) = q_m$

• $q_0$：开始状态
• $F$：接受状态（结束状态）

 

2. 表达方法

状态图

• 圆圈节点：状态
• 有向弧线：迁移函数
• 被一个无源弧线指向的圆圈节点：开始状态
• 双圈：接受状态

迁移表

• 箭头指向：开始状态
• 带星：接受状态

 

3. NFA 和 DFA 的比较

定义起来基本上是一样的，不同点如下：

1. DFA 的每次转移路线都是确定的，但是 NFA 并不，具体一点 DFA 就是状态 $q_n$ 接到字符 A 后只能跳转到状态 $q_m$，而 NFA 在状态 $q_n$ 接到字符 A 后可能跳转到多个状态 $q_{m1}, q_{m2}, ...$，NFA 将遍历所有这些可能。
2. NFA 允许接受空字符 $\varepsilon$ ，也就是可以同时存在多个状态

简单举两个例子:

 

4. DFA 的应用举例

设计一个 {0，1} 上不包含一对 1 且中间被奇数个 0 隔开的任何串：

一般来说，针对一个特定的要求，NFA 由于更接近人类思考的流程，构建起来远远比 DFA 方便，且状态图更少，但是 NFA 作为一个算法时的运行效率不是那么高，需要转化为更靠近代码执行的 DFA

 

5. NFA $\rightarrow$ DFA：惰性创建法

这里说再多都没有一个例子实在

Ready GO：

1. 开始状态 {$q_0$}
2. {$q_0$} 接受字符 0 可到的状态集 {$q_0,q_1$}

   {$q_0$} 接受字符 1 可到的状态集 {$q_0$}

   出现了新的状态{$q_0, q_1$}

3. {$q_0, q_1$} 接受字符 0 可到的状态集 {$q_0, q_1$}

   {$q_0, q_1$} 接受字符 1 可到的状态集 {$q_0, q_2$}

   出现了新的状态{$q_0, q_2$}

4. {$q_0, q_2$} 接受字符 0 可到的状态集 {$q_0, q_1$}

   {$q_0,q_2$} 接受字符 1 可到的状态集 {$q_0$}

   没有任何新的状态，算法结束

得到的就是 NFA 的状态转移表啦：

根据状态转移表很容易画出来状态图：

 

值得留意的是，如果是带有空字符的 NFA （也就是 $\varepsilon$-NFA）的话，得理解它所有空字符转移都是一个状态，化成 NFA 的时候需要注意，举个例子：

 

6. DFA 的最小化

从 NFA 转化得到的、自己写出来的 DFA 往往不是最优的，这里要做的就是对 DFA 的 “ 精修 ”，把之前罗里吧嗦的 DFA 优化一下

核心思想：找到等价状态，合并

核心规则：

 

举例
简化以下 DFA：

1. 画个状态化简表

   

2. 把终结状态和非终结状态的交汇点打叉，表示这些状态对不等价
   
3. 例用规则 2 反复遍历，打叉

   

4. 剩下的就都是不可分辨的状态啦，按可达性分组
   
5. 合并状态，得到结果
   

 

三、语言模型：正则表达式

注意这里所说的正则表达式还是数学层面上的，和标志正则表达还是有点差别

DFA 是一种抽象模型，计算机无法理解，所以需要有一种媒介让计算机理解 DFA 所定义的规则，这种规则就是正则表达式，反过来，一个字符串如果符合正则表达，就是合法的，因此，正则表达除了在词法分析之外，在爬虫、文本处理等方面也大有用途

1. 基础算符

1. + ：表达“或”的关系
2. ()* ：括号中的字符 0 次或多次出现

举例 (字符集 $\Sigma =$ {0, 1} )

• 任意以 010 结束的串：$(0+1)^*010$
• 任意包含 01 的串：$(0+1)^* 01 (0+1)^*$

 

2. 正则式 $\rightarrow$ NFA

方法一
这个方法其实和程序设计的思路一样的，无非是一个选择结构和一个循环结构，空转移大法好：

可以看出来这么转化的话会嵌套出现一堆 $\varepsilon$ 转移，肯定不是最简的，这就需要对 NFA 进行化简：

当然如果转化成 DFA 的话又需要进行 DFA 化简，总结一下：

• NFA 化简：去无意义空转移
• DFA 化简：合并等价状态

缺陷：这个方法会产生大量无用的空转移，最后将导致恐怖的计算化简难度

 

方法二

下文 NFA $\rightarrow$ 正则式的逆过程

 

3. NFA $\rightarrow$ 正则式

step 1. 将 NFA 转化为如下形式：
I. 只有一个接受状态
II. 没有射入到开始状态的弧
III. 没有从接受状态射出的弧
看起来不好转化是吧，但是掌握空转移大法就能搞定一切，
只要给引入新的开始状态和结束状态就行，看下图

原本 q₁ 是开始状态，q₃ q₄ 是结束状态，但是不符合条件怎么办呢，直接引入一个 q₀ 作为新的开始状态，一个 q_f 作为新的结束状态，用 $\varepsilon$ 弧连接，完美实现转化

step 2. 利用拓展 NFA 逐步转化为正则式
先来说下什么是拓展 NFA，之前所说的 NFA、DFA 都是接受一个字符然后转移到下一个状态，拓展 NFA 是指允许接受一个字符串然后转移到下一个状态，这个字符串就是正则式的一部分，当开始状态接受一个字符串直接转移到结束状态的时候，这个字符串就是所求正则式，看下面的例子：

将正则式交给特定的工具就能够生成词法分析器了（当然要是头铁想要硬生生造轮子自己写正则解析器也没人拦你）

 

4. 正则与非正则的证明

再说一个比较偏理论的东西，有些需求是无法使用正则式表达的，换句话说就是非正则的，那么如何证明呢？用两个例题解释以下比较直观

证明正则

例题：如果 L 是一个语言，a 是一个符号，则 L/a（称作 L 和 a 的商）是所满足如下条件串 w 的集合：wa 属于 L。例如：如果 L = {a, aab, baa}，则 L/a = {$\varepsilon$, ba}，证明：如果 L 是正则的，那么 L/a 也是。

证明： 假设一个 DFA A， L(A) 是其定义的语言

假设另一个DFA B， 当且仅当 $\delta_A(q,a)\in F_A$ 时，$q\in B$

则：当 $\delta_A(q_0,wa)=\delta_A(\delta_A(q_0,w),a) \in F_A$ 时

$\delta_B(q_0,w)\in F_B$

即：B = L/a，B 是正则的

 

证明非正则

正则语言的泵引理

假设 $L \subseteq \sum^*$ 存在字符串$w\in L$ 且 $\left|w\right|\geq n$（n为泵长度，可理解为正则语言等效的DFA的状态个数），如果可以将 w 写成 $w=xyz$ 的形式时，以下说法成立:

理解：如果 $|w| \ge n$ ，那么显然中间某状态有重复，这个重复状态就是体现在 y

使用要点

通过泵引理可以用反证法证明 L 不是正则语言。证明的时候需要注意以下几点：

1. 假设要证明的语言为正则语言
2. n 是未知的
3. w 可以在满足 $w\in L$和 $\left|w\right|\geq n$ 的条件下自由选择
4. x,y,z 也是未知的
5. 找到一个 k，使得 $xy^{k}z\notin L$，也就是说和泵引理的第三条矛盾

一个证明L不是正则语言的例子

• 证明

  $L_{01}=\{0^{n}1^{n}|n\geq 1\}$不是正则语言

  • 假设 $L_{01}$ 是正则语言，令 n 为泵引理常数
  • 选择 $w=0^{n}1^{n}\in L$，则 $\left|w\right|\geq n$ 于是存在 x,y,z 使得 $w=xyz$ 满足条件$\left|xy\right|\leq n$，$\left|y\right|\geq 1$ $\forall k\geq 0:xy^{k}z\in L_{01}$ 因为 $\left|xy\right|\leq n$ 且，$\left|y\right|\geq 1$所以 y 中不包含 1 但最少有一个 0
  • 当 $k=0$ 的时候，$xy^{k}z=xy^{0}z=xz$，xz 中 1 的数量比 0 多，所以 $xz\notin L_{01}$
  • 与泵引理的第三条矛盾，因此 $L_{01}$ 不是正则语言

 

 

四、语法模型：正则文法

要理解那些工具是怎么生成词法分析器的，就必须了解一下文法模型，一般这些工具都是靠解析文法来生成对应词法分析器的

1. 啥是文法？

• 文法：G =（V, T, P, S）
  • V：变量/非终极符号的非空有穷集；
  • T：终极符的非空有穷集，V∩T = Ø；
  • P：产生式的非空有穷集合；
    P是生成式的有穷集合，生成式的基本形式是α→β，这里α和β都是（V∪T）中的元素，即它们都是由变元和终结符组成的符号串，但要求α至少含有一个非终结符；在形式文法定义中生成式集合P是至关重要的，它决定了语言是如何构造出来的。
  • S：开始符号，S是 V 中的元素。
• 由形式文法产生的形式语言记为L(G)；L(G)中的字符串ω都具有如下特点：该字符串仅由终结符组成，即ω∈T；该字符串能由开始符号S派生出来。

以上是不说人话型定义，但是文法这个破玩意儿确实抽象，简单理解为一个特定的规则体系好了，一般长成这个样子（下图为一个上下文无关文法，是进行语法分析的时候使用的)：

2. 什么是正则文法？

由 DFA 定义的文法都是正则文法，正则文法一般负责进行词法分析，正则文法分为两类：

• 右线性文法：生成式的形式必须是A→ωB或A→ω，其中 A，B 都是变量，ω是终结符串（可以是空串）
• 左线性文法：要求生成式必须是A→Bω，或A→ω的形式

 

3. DFA $\rightarrow$ 右线性正则文法

1. DFA 状态对应文法的非终结符
2. DFA 的弧上的字符对应文法的终结符
3. DFA 初始状态对应正规文法的开始非终结符（S）
4. DFA 转移关系对应产生式规则：
   

   若 B 不为结束状态，对应产生式：$A \rightarrow cB$
   若 B 为结束状态，对应产生式：$A\rightarrow cB\ |\ c$

至于怎么把 DFA 转换为右线性文法，把上述过程倒过来就行
可以看出右线性文法从开始到结束是一个自上而下推导的过程

 

4. 左线性文法 $\rightarrow$ DFA

1. 增加结点 N 作为开始结点（注意这里的 N 是增加的，一定不能是文法的开始符号！！）
2. 文法中每个非终结符对应 DFA 一个状态
3. 文法中每一个形如 $B\rightarrow Ac$ 的产生式，对应如下 DFA 结构：
   
4. 文法中每一个形如 $A \rightarrow c$ 的产生式，DFA 中增加一条从开始结点到 A 的弧
5. 以文法的开始符号 S 作为结束状态

同样的，想要把 DFA 转化为左线性文法，把上述过程倒过来就行
可以看出左线性文法从开始到结束是一个自下而上归约的过程

 

5. 左右线性文法的相互转化

注意注意，没有任何可取巧的地方，左右线性文法的相互转化一定是以 DFA 作为桥梁的，必须先化为 DFA，然后通过 DFA 转化为目标文法

 

五、总结

词法分析部分内容的核心是 DFA 和 NFA，一般套路是得到一个语法需求，构造合适的 NFA，然后就能轻松拿到对应的正则表达式，如果要得到对应正则文法，就需要将 NFA 转化为 DFA 然后进行转化，大体上结构如下图：

 

附：利用工具生成词法分析器

emmm，这部分其实就是为了结构完整，不属于原理部分而偏向于技术应用部分，等我苟过期末开始编译实验求生的时候在另写一篇文章对着里进行补充。

传送门：还没造好嘞