编译技术入门与实践之词法分析（Lexical Analysis）

您所在的位置：网站首页 › behavior所有词性 › 编译技术入门与实践之词法分析（Lexical Analysis）

编译技术入门与实践之词法分析（Lexical Analysis）

2023-05-03 06:36| 来源: 网络整理| 查看: 265

0 写在前面

开此系列专题，主要目的在于留下学习痕迹，同时方便后续知识总结、梳理和技术交流。

我本人的研究方向为智能芯片，编译器设计实现为日常实验中经常需要面对的问题。

由于初涉此领域，文中相关知识总结可能出现错误，欢迎批评指正。

0.1 本文学习课程链接

http://Bilibili.Com, 2022, https://www.bilibili.com/video/BV1TJ411v7ys?p=2. Accessed 20 Apr 2022.

1 课程内容梳理（四小节内容，两次课后作业）1.1 词法分析（Lexical Analysis）在整体架构中的位置

1.2 词法分析（Lexical Analysis）中的理论知识结构RE，正则表达式NFA，非确定有限自动机DFA，确定有限自动机minimal DFA，最小确定有限自动机

Minimal NFA？

Minimal RE？

词法分析几个算法的掌握程序要求（自学Cooper教授的课件）

要求掌握正则表达式的概念和写法不同的语言/工具可能有不同的表示法，需要注意细节能够手工构造RE to NFA，NFA to DFA 能够理解DFA to min DFA的算法思想其他算法实现细节及练习，以后工作中用到的时候再回来做知识地图（Knowledge Map）：你知道算法在这里，有开源实现，知道自己能重新实现工具：正确性验证、可视化 Regulex：https://jex.im/regulexregex2nfa：https://cyberzhg.github.io/toolbox/regex2nfamin_dfa：https://cyberzhg.github.io/toolbox/min_dfanfa2dfa：https://cyberzhg.github.io/toolbox/nfa2dfaregexr：https://regexr.com fsm_simulator：https://ivanzuzak.info/noam/webapps/fsm_simulator 课后作业（词法分析） 学习Cooper课件

看完之后阅读/观看另外三位老师的课程，查缺补漏（1-9，其中1-3为前言内容，可择机学习）玩一玩推荐的这几个可视化演示的小站点多数是Github开源，可直接看到算法源代1.3 数学知识补充

主要关于以下几个问题

问题的定义和解空间的确定解的存在性解的构造算法、找到最优解的算法数学算法通过计算机程序实现的问题

几个数学概念

命题逻辑数学建模形式语言与自动机理论、计算理论整数规划、最优化方法等

思维框架

物理世界的属性和关系进行抽象，得到概念上的模型在模型上，通过一些计算法则和约束条件，推演得到结论将模型中的结论映射回物理世界，验证是否满足要求1.3.1 解的空间和解的存在性

具体问题抽象成模型之后，所有可能的答案构成了一个集合/空间

1.3.2 找到解的算法、寻找最优的解、验证最优解

找到解的算法：穷举法、构造法、其他各种搜索算法

寻找最优解：

何为最优解？

给定约束条件，目标，在可行解中找到目标最大化的解编译器中约束条件是目标代码功能应与源代码等同，目标是运行时间最短贪婪法、动态规划、剪枝查找、模拟退火、启发式算法...（编译器中一般面对离散空间）

如何验证最优解？

一般而言，验证一个解是最优的要比找到这个最优解容易在真是工程中，验证有时也不容易一般性的，是有一个差不多可以当作最优解的范围1.3.3 数学算法通过计算机程序实现的问题

可能碰到的问题

数字的有效范围和精度范围问题，至今仍是一大类安全隐患（溢出覆盖，网络安全领域）算法的时间复杂度算法的空间复杂度数学模型同真是世界之间的映射关系的精确程度：大量的Tradeoff数学建模的精度程度，若模型过于精确，可能runtime out，若过于简单，可能不能很好的simulate real world1.3.4 编译原理中的基本知识点编译器中大量的算法处理的是离散空间的最优解问题大量的问题是NP难问题；即不存在的多项式时间（时间复杂度，runtime out）的解法因此，编译器中大量使用启发式算法寻找近似解启发式（Heuristic），现阶段更精确的讲解，可学习人工智能中的AI Search相关知识（相信我，你不想学）1.4 前端编程练习用语言PL/0的准备

What is PL/0？

一个用于编译器教学的语言

https://en.wikipedia.org/wiki/PL/0这里有完整的语法和历史介绍，阅读这一页就可以进行下一步练习了里面提供了一些例子，可以用于前一小节的RE的测试中理论上图灵完备实际上受限于可编写的程序的规模（跟C++之父为什么要发明C++同样原因）

PL/0的作用？

根据语言规范，使用flex/bison实现词法分析和语法分析翻译到LLVM IR，用这个过程学习LLVM IR的操作掌握后，可以在工作自己创造新的语言，DSL或通用都可以

课后练习（PL/0部分）

阅读PL/0的语言规范，尝试自己动手写example用上一小节提到的可视化工具尝试用RE实现词法分析的匹配部分从Github或Gitee上找参考的例子预习flex工具的语法及使用，跑个例子2 Lexical Analysis（Scanner）2.1 Overview2.1.1 Compiler中的时间度量

在编译器设计中，会讨论许多时间，Design Time，Build Time，Compile Time，Run Time，...

在实际工程中，事务的时间度量可以简单分为下面几类：

Design Time & Build Time 用于度量编译器运行之前的时间开销

这两者是用于度量编译器设计和实现的成本的，并不会影响编译时间（Compile Time）

Compile Time 用于度量用户运行编译器的时间（即源代码转换为目标代码的时间）

用户对编译时间（Compile Time）十分敏感Compile Time 用于度量编译程序的启动开销，一定程度上可以反应编译器的质量，其并不会影响运行时间

Run-time 用于度量实际应用程序的性能

编译的一个重要目标是最小化运行时间，这意味着需要降低翻译引入的开销2.1.2 DFA vs NFA

针对DFA，这里需要解释两个名词：

Deterministic，指确定，描述该自动机在任意状态下，进行转换时，其下一状态固定且可预测Finite，指有限，描述该自动机的状态空间有限，即总状态可数

DFA（Deterministic Finite Automaton），确定有限自动机。

其中的确定性（Deterministic），意为每给定一个字符，其状态转换仅有一种可能，即下一状态唯一，这也是前面所述，固定可预测的基本含义。更直观的解释如下图所示。

那么一个有限状态机的某个状态针对某个字符是否可以有多个下一状态？

答案是在计算机科学中，这种情况是允许的，这种自动机，称为NFA（Nondeterministic Finite Automaton），即非确定有限自动机，NFA是计算机科学中众多奇怪术语中的一个，但是NFA十分有用。

首先明确一个基本概念，就是NFA和DFA是等价的，即这两者可以相互转换，而且有时构建一个NFA比构建一个DFA更简单。这可以用于简化复杂问题DFA的求解。

2.1.2.1 DFA

理论上说，每一个正则表达式同一个自动机等同，更精确的来说是确定有限自动机（DFA，deterministic finite automaton）。

DFA的转换规则

开始状态为

，每接受一个字符，进行一次状态转换DFA接受一个单词x，仅在单词x离开DFA时，使DFA处于接受状态，或者终态若DFA遇到一个没有明确状态转换的字符，转出错处理态，并一直处于此状态

自动机的补集（DFA）

求解一个DFA的补集，从逻辑上讲十分简单，只需要进行如下两步骤

将非终止态转换为终止态将终止态转换为非终止态

这样就可以实现接受原来DFA不接受的字符，但是当DFA使用RE表示时，并不直观。

2.1.2.2 NFA

NFA的转换规则

在进行非确定的状态转换时，NFA同时遍历所有的可能状态，所有路径中若某条路径到达终态（可接受状态），NFA即接受当前字符串在进行非确定的状态转换时，NFA最终做出能到达接受态的选择2.1.3 自动词法分析器（Scanner）的结构

Scanner的结构如上图所示，需要经过三步来实现一个自动的词法分析器

开发人员在设计时间编写RE（Design Time）工具依据RE实现一个Scanner（Build Time）编译器运行时，使用实现的Scanner将源代码转换为Token流（单词流，一般为图中所示的对）（Compile Time）

Scanner的学习目标有三个（也是对今后开发Scanner的要求）

简化快速高效的Scanner的构建过程开发适用性广泛的技术学习掌握内在的理论，并进行实践

Scanner Generator的功能

主要有三个

将Scanner的内在构造编码为表，以便生成词法分析器的骨架Skeleton Scanner 可以通过解释表来模拟DFA每个Scanner使用相同的骨架，独立于RE依据RE创建DFA，并将其转换为表

更详细的Scanner组成如下：

可以看到针对每个字符，词法分析器的骨架，负责查表和读取下一个字符，这两个操纵的时间复杂度均为 O(1)

上图中的程序并不完整，还需要进一步完善。

首先Scanner的输出为对，因此可以做如下修改

修改后的时间复杂度仍为 O(1)

其次为了获取寄存器编号，可以做如下修改

需要明确的是，无论RE是否复杂，每次状态转换的时间开销均为 O(1) ，即RE的复杂程度并不影响Scanner的实现效果（不增加编译时间 Compile Time），当然可能使得最终生成的表占用空间增大。

2.1.4 如何将任意RE转换为DFA，并最终构造Scanner（Knowledge Map，即最终需要学习哪些知识）

总的来说需要进行以下四个步骤

构造一个简单直接的NFA来描述RE可以很简单的使用算法实现要求使用 $\epsilon$ 连接不定态构造一个同NFA等价的DFA使用状态集的概念实现（合并状态）最小化构造的DFA有两种最小化算法Brzozowski和Hopcroft生成Scanner代码（将Minimal DFA转换成表）需要增加专用的信息

将上述结果总结一下，其Knowledge Map（需要学习的知识）如下：

Knowledge MapRE->NFA（Thompson ’s construction）为RE中每个项创建一个确定的自动机以某种固定模式将所有的NFA结合在一起NFA->DFA（Subset construction）构造一个和现有NFA等价的DFADFA->Minimal DFABrzozowski's algorithmHopcroft's algorithmDFA->REAll pairs, all paths problemUnion together paths from s0 to a final state2.2 RE（Regular Expressions，正则表达式）2.2.1 Why Regular Expressions？

首先面临第一个问题，如何定义一个正整数？

这面临的第一个问题是自动机的精确性和语言的模糊性之间的矛盾，如001是否是一个正整数？00呢？

Cooper教授对这个问题给出了如下两张图

左侧的自动机，并不接收001，因为其第一位为0，第二个自动机接收001。

这个例子同时展示了一个重要的问题，就是使用状态转换图的形式描述自动机足够精确，但是并不简洁。

需要一个简洁的表示方法描述自动机，这就是正则表达式（Regular Expressions）

2.2.2 Regular Expressions Detials

首先是其定义，具体的定义如下：

若 $\underline{x} \in \Sigma$ ，则 $\underline{x}$ 为一个正则表达式，其表示集合 $\{\underline{x}\}$ ，或 $L=\{\underline{x}\}$ 。（此处为译文，可以简单理解正则表达式在表示一个集合）

两个正则表达式的之间的关系定义：

连接：若 $\underline{xy}$ 是一个正则表达式，其表示 $L(\underline{\mathrm{x}}) L(\underline{\mathrm{y}})=\{p q \mid p \in L(\underline{\mathrm{x}})$ and $L(\underline{x}) \cup L(\underline{y})$ 选择：若 $\underline{x} | \underline{y}$ 为一个正则表达式，其表示 $L(\underline{x}) \cup L(\underline{y})$ Kleene Closure（克林闭包）：若 $\underline{x}^{*}$ 是一个正则表达式，其表示 $L(\underline{x})^{*}=\bigcup_{0 \leq k\infty} L(\underline{x})^{k}$ Positive Closure（正闭包）：若 $\underline{\mathrm{x}}^{+}$ 是一个正则表达式，其表示 $L(\underline{x})^{+}=\bigcup_{1 \leq k\infty} L(\underline{x})^{k}$

额外说明：

若 $\varepsilon$ 是一个正则表达式，其表示空集

以上为正则表达式的基本定义，该定义基于字母集。

2.2.3 Compiler中的RE的功能

Design Time

首先RE可以用于识别微语法（microsyntax，此处即指词法，指词法规则），即可以将字符串映射到词性，将单词的拼写，同其词性映射。

Build Time

使用基于自动机的理论研发的工具实现将RE转换为DFA，然后将RE转换为实现词法分析的代码。

Runtime

基于RE的词法分析器应用十分广泛Compilers, text editors, input checking on web pages, software to filter URLs2.3 NFA（Non-deterministic Finite Automata，非确定有限自动机）

在开始本节之前，再次回顾Scanner的产生过程RE->NFA->DFA->Minimal DFA->Scanner，每个步骤需要完成的操作或需要使用的算法如下所示

NFA的直观理解如下图所示

前面（2.1）介绍了NFA的一些基本转换规则，重述如下

NFA的转换规则

在进行非确定的状态转换时，NFA同时遍历所有的可能状态，所有路径中若某条路径到达终态（可接受状态），NFA即接受当前字符串在进行非确定的状态转换时，NFA最终做出能到达接受态的选择

需要注意的是，在NFA中 $\epsilon$ 可用于连接两个状态，表示两个状态等价

2.3.1 Why NFA？

为什么需要NFA？首先看一个RE， $(\underline{a} \mid \underline{b})^{*} \underline{a b b}$ 的DFA 状态转换图，如下所示

需要明确的是，每一个RE对应一个或多个DFA，这里面隐含了下面几条信息

每一个RE至少有一个DFA与之对应这个DFA可能很难直接构建

当然，可以使用自动化技术进行构建

再看看针对上述RE，对应的NFA是怎样的

可以看到NFA相比于DFA更加简单，直观

相比于DFA，NFA有如下优势

NFA同RE之间的关系更加直接可以使用 $\epsilon$ 连接两个DFA来实现一个NFA可以通过重写NFA来消除 $\epsilon$ 某种程度上，NFA模型描述更加直观2.3.2 NFA 和 DFA 之间的联系

DFA是一个特殊的NFA

DFA没有 $\epsilon$ 转换DFA的状态转换是单值转换NFA的转换规则可等价为一个DFADFA可以由一个NFA模拟NFA也可以由DFA模拟

综上所述，在描述语言方面，NFA同DFA等价

2.3.3 RE转换为NFA（Thompson's Construction）

可以使用Thompson's Construction实现

其基本思想为

RE中每一个符号、操作符，均对应一个NFA模式通过使用 $\epsilon$ 按照一定的优先级连接这些模型，并设定终止态（接受态），就可以将RE转换为NFA

具体来说针对RE的四种基本操作

首先使用如下四种操作操作将RE分割为几个子集

然后按照如下优先级，使用 $\epsilon$ 将各部分相连

括号（Parentheses）闭包（Closure）两种闭包在这里等价，正闭包可以转换为Kleene Closure（拿一个出来即可）连接（Concatenation）选择（Alternation）2.3.4 Example of a ( b | c )*

2.3.5 NFA转换为DFA（Subset Construction）

以上一小节的最终得到的NFA为例，其对应的DFA如下图所示。

上述过程采用的算法称为子集构造算法，该算法可以创建一个DFA，用以模拟NFA。

该算法包含两个关键的函数

$Move \left(s_{i}, \underline{a}\right)$ ，指 s_i

可以通过 $\underline{a}$ 到达的所有状态 $FollowEpsilon\left(s_{i}\right)$ ，指 s_i

可以通过 $\epsilon$ 到达的所有状态

算法流程

设定DFA的开始状态为NFA开始状态 n_0

将

可通过 $\epsilon$ 到达的所有状态加在一起 $d_0=FollowEpsilon\left(n_{0}\right)$ $D=\{d_0\}$ 对所有的 $\alpha \in \sum$ ，计算 $FollowEpsilon (Move \left.\left(d_{0}, \alpha\right)\right)$ 若经过上式计算，得到一个新的状态，将其添加到

按照第三步不断迭代，直到没有新的状态可添加

用伪代码表示为下图

可以看到这种算法描述虽然更严谨，但是看起来很复杂。

个人理解上，这个步骤最好同之前的RE-->NFA过程结合起来看。因为这样就可以清楚的了解，NFA的实际情况仅有几种（RE的基本四种运算（其实是三个，两个闭包可以等同）+基础的一个），在通过子集构造（本质为相同集合状态合并），就可以得到DFA。

具体的转换例子如下所示，使用上面介绍的算法（Subset Construction）

首先进行第一步取 n_0 及其 $\epsilon$ 转换作为初始状态 d_0

第二步，第一次遍历字母表，查 $FollowEpsilon (Move \left.\left(d_{0}, \alpha\right)\right)$ ，发现a可使得状态发生转换，其状态转换后为 n_1 ，且同时计算了 n_1 的其 $\epsilon$ 转换，如下图中表所示

在本例中，只有三个字母可以使得状态进行转换，因此表中只给出了a，b，c

第三步，将第二步得到的新集合，作为一个整体，添加到

第四步，对新加入的 d_1 进行同第二步相同遍历（注意此时已经在集合（可扩展状态集合）中将 d_0 删除）遍历获得可经过b转换的状态集，和可经过c转换的状态集如下所示

第五步，将这两个集合添加到$D$和$W$中，为下一次遍历做准备

第六步，进入下一次遍历，此次针对 d_2 ，并将 d_1 从中删除（此时中有 d_2 和 d_3 两个状态）

得到如下结果

第七步，进入下一次遍历，此次针对 d_3 ，并将 d_2 从中删除（此时中有 d_3 一个状态）

得到如下结果

第八步，确定终止状态（接受态）

如下所示

经过上面八步，四次迭代，可以得到转换后的DFA以及状态转换表如下所示

以上为NFA转换为DFA的过程，包含了一般的细节，该例要好好理解，建议对照之前的伪代码。

2.4 DFA（Deterministic Finite Automata，确定有限自动机）2.4.1 DFA Minimization（DFA最小化）

直观上，子集构造算法（Subset Construction）将NFA中的前缀进行了合并

Thompson's Construction算法（RE-->NFA）保留了 $\epsilon$ 转换，用于连接不同单字符自动机

Subset Construction算法（NFA-->DFA）消除了 $\epsilon$ 转换，但是留下了复杂的细节

上述两个算法的直观对比如下所示

可以看到经过Subset Construction算法将NFA转换为DFA后，得到的DFA中，还是保留了两个bc分支，这两个bc分支可以进一步合并，也就是说得到的DFA还可以进行优化（如下所示），得到一个更简洁的DFA，其中最简洁的称为Minimal DFA（最小DFA），这也是本节相关算法的目的。

接下来介绍两个可以实现Minimal DFA的算法

2.4.1.1 Brzozowski's Algorithm

该算法的关键思想是，使用两次子集构造算法（Subset Construction Twice）

首先需要定义一下该算法中使用的三个函数

对一个确定的NFA

为当前NFA（Thompson's Construction算法后得到的NFA）的反向NFA，具体步骤为两步，一是使初始状态变为终止状态，二是在原来的终止状态后面添加一个开始状态，并使用 $\epsilon$ 将该开始状态同之前的终止状态相连接。这样就得到了一个反向的NFA。直观上来讲就是做上图的转换 subset(N)

为该反向NFA的Subset Construction算法的结果，即该反向NFA经过子集构造算法后得到的DFA reachable(N)

为删除初始状态不可达的状态后的NFA 然后，该算法的具体操作可以使用上述三个函数定义如下

$\text { reachable(subset(reverse( reachable(subset(reverse( }(N)))))$

最后得到的结果就是一个Minimal DFA

这里是不是很迷惑，经不住问一个为什么？为啥这么反过来两次就可以得到一个Minimal DFA。这里Cooper教授给了下面两句话，可以让你有点信心，毕竟这里属于算法范围，还是顶尖的计算机科学家（都是哲学家）研究出来的。这里主要注意一下第一句，就是并不是所有人可以通过直觉发现最后的结果。

接下来为了更加的具体，使用一个例子来说明到底这个算法都做了什么

仍以上面的 abc|bc|ad 为例

假设已经通过Thompson's Construction算法将RE转换为了NFA，也就是得到了一个NFA，如下图所示

接下来就可以使用Brzozowski's Algorithm

Step 1 The First Reverse & Subset

这里可以对比一下直接使用Subset Construction得到的DFA同这里得到的反向DFA

直接使用Subset Construction

Brzozowski's Algorithm的第一次Reverse + Subset的结果

可以发现相比于直接使用Subset，Brozozowski的第一次Reverse+Subset将原来的DFA中尾部可以合并的状态进行了合并。（这个也可以直观上进行理解，子集构造算法的本质就是状态合并，这里在构造反向NFA时，将所有的终止状态后面增加了一个开始状态，并使用 $\epsilon$ 进行连接，这样在使用Subset时，第一个就是将所有的同等状态进行了合并，这样就合并了尾部的状态）

Step 2 The Second Reverse & Subset

这里进行Brzozowski's Algorithm的第二次反向+子集构造，可以得到的结果如上图所示

可以发现经过这次操作，得到的DFA合并首部可合并的状态。

经过上面两步，就得到了最终的DFA，该DFA没有多余的状态，是一个Minimal DFA。

何时使用Brzozowski's Algorithm？

如果认真分析了上述算法，可以发现该算法可以由NFA直接生成一个Minimal DFA，就是说通过Thompson's Construction算法得到NFA后可直接使用Brzozowski's Algorithm得到Minimal DFA。

Brzozowski's Algorithm的关键知识点

该算法最终会得到一个最小Minimal DFA该DFA的大小同RE描述的语言的规模有关，与RE的复杂程度无关该算法的结果为DFA，因此使用该DFA进行模式识别时（词法分析），每个字符时间开销为 O(1)

编译器开发人员可以使用最原始，最直观的RE（不同奔着最简洁的DFA去，算法会帮你构造好）2.4.1.2 Hopcroft’s Algorithm（这个不太好理解）

该算法的关键思想是

搜索NFA中行为等价的状态集合使用新的状态表示该集合

接下来定义何为行为等价（Behaviorally equivalent）：

两个状态 s_i 和 s_j 行为等价，当且仅当：

对 $\forall c \in \sum$ ， s_i

和

的状态转换到相等的状态 s_i

和$s_j$状态转换后的路径相等

集合的一个划分的定义：

集合S的一个子集，该子集中每个状态（元素）均属于S。（很直观）

Hopcroft's Algorithm算法遍历NFA状态集合的所有划分（子集）。

Hopcroft's Algorith算法需要搜索的划分 $P=\left\{p_{0}, p_{1}, p_{2}, \ldots p_{n}\right\}$ 需要具有的下面两个特性：

If $d_{i} \& d_{j} \in p_{s}$ and

takes $d_{j} \rightarrow d_{y}$ and $d_{j} \rightarrow d_{y}$ , then $d_{x} \& d_{y} \in p_{t}, \forall c, i, j, s, t$ If $d_{i} \& d_{j} \in p_{s}$ and $d_{i} \in F \quad then \quad d_{j} \in F$

初始划分： P_0 包含两个集合 $\{D_A\} \& \{D-D_A\}$ ，其中集合 D_A 中为终止状态

特性一其实给出了如何重定当前划分（更新）

Assume $s_{i} \& s_{j} \in p_{s}$ , and $\delta^{-1}\left(s_{i}, \underline{a}\right)=s_{x}, \& \delta^{-1}\left(s_{j}, \underline{a}\right)=s_{y}$ If $s_{x} \& s_{y}$ are not in the same set $p_{t}$ , then $p_{s}$ must be split 这里有一个推论： $s_{i}$ has transition on $\underline{a}, s_{j}$ does not $\Rightarrow \underline{\text { a splits }} p_{s}$ A single state in a DFA cannot have two transitions on a Each $p_{s}$ will become a DFA state

看了上面这些是不是觉得不像人话，那我来翻译翻译:dog:

首先，假设划分中有一个集合，集合中有两个状态，这两个状态在同一个字符下进行状态转换后得到另两个状态，这两个新得到的状态必须同处该划分的一个集合中，否则，需要对当前划分进行更新，将两个初始状态拿到两个不同的集合中；其次，由于DFA中每一个状态转换确定且唯一，因此划分接受某个字符时不能有两种或两种以上的后续划分。其实细品这两个是在说同一个意思。（个人理解，参考即可，感谢）

接下来更具体的介绍Hopcroft算法

具体来说，该算法的关键思想，如下：

Splitting Q Around Transitions on $\alpha$ Splitting Q Around S and $\alpha$

上述两个关键思想可以使用图来简单理解

首先是第一个 Splitting Q Around Transitions on $\alpha$

该思想简单解释一下就是，若一个划分中的状态集合在同一个字符下进行状态转换，可能到终止集合，也可能到非终止集合，那么该状态集合根据该字符进行再划分。（这个关键思想解答了了何时需要再划分的问题）

第二个关键思想Splitting Q Around S and $\alpha$

说人话就是需要找到Q中通过 $\alpha$ 转换到终止状态集合S的那部分的最大集合，此处即为 Q_1 ，以此进将其划分出去（这个关键思想解答了如何划分的问题）

接下来，为了更具体的介绍Hopcroft算法，给出该算法实现的一种方法（伪代码）

为第二个关键思想中介绍的需要分割的集合 q_1

为

的子集，该子集中的所有状态均通过同一个字符状态转换到

，

是除去

剩余的那部分

其实看了伪代码，还是挺好理解的，可以将算法分为以下几个步骤

Step 1：划分初始集合，将所有的终止状态设置为一个集合，非终止状态为另一个集合Step 2：从Worklist中选择一个集合S，并将其从Worklist中删除，此步用于确定当前操作的集合Step 3：遍历字母表Step 3-1：找到Image（何为Image可看第二个关键思想介绍）Step 3-2：遍历现有划分，针对包含状态在Image中的集合

做如下操作Step 3-2-1：依据状态是否属于Image将q划分为 q_1

和

Step 3-2-2：若 q_2

不为空进行如下操作Step 3-2-2-1：从现有划分中将集合

删除，并加入

和

Step 3-2-2-2：若q仍处于Worklist中（尚未针对q进行划分更新），则将其从worklist中一出，并将 q_1

和

添加到Worklist中Step 3-2-2-3：若3-2-2-2不成立，则选择 q_1

和

中节点数目较少的那个集合添加到WorklistStep 3-2-2-4：若当前集合S同q相同，则转Step 3，否则转Step 3-2

看到这里是不是还是比较蒙，那我用人话解释一下，首先先给出一个简单的划分，区分终止集合和非终止集合，然后在非终止集合中，找到可以通过同一字符状态转换到终止集合的子集合，将非终止集合划分为两部分，重复这个步骤。（这种说法忽略了细节）

Example

如下图所示，为严格按照伪代码得到的结果

将伪代码同表格对应起来可以得到如下过程

首先初始化Worklist和Partition

然后对Worklist中的集合进行遍历，从Worklist中取出一个集合，针对每个字符（此处为e、f、i），查找对应的Image，并依据Image和Partition中每个集合的交集，对集合进行重划分，并更新Partition和Worklist

以其中一次遍历为例，如下图所示，此时从Worklist中取出一个集合 p_0 ，针对每个字符（e、f、i），搜索对应的Image，并依据Image和Partition中各个集合的相交情况，对Partition进行重划分，同时更新Worklist

在代码中当确定了 q_1 和 q_2 后，需要更新Worklist和Partition，也就是下部的几个if语句，这里解释一下每个if语句处理的情况（个人在学习中的理解，经过后续编程实现后，有了更深的认识会回来调整此部分）

首先进行下一步判断的前提是 $q_2 \ne \emptyset$ ，也就是说，若其为空，不用更新Partition和Worklist，因为此时整个划分为对应的Image的一个子集在 $q_2 \ne \emptyset$ 的前提下，首先需要从Partition中移除

，因为此时$q$已经分割为了 q_1

和

，因此需要移除

，将

和

加入Partition中接下来是更新Worklist，Worklist的作用是以其中的每一个集合为基准，查找Image，为使得算法更加高效，其更新规则同Partition并不相同，分为了下面两种情况若

在Worklist中，也就是说，

是一个还没有拿出来的基准集合，此时使用 q_1

和

将

替换即可，此时的操作同Partition的操作相同反之，若

不在Worklist中，因为

本来是Partition的一个集合，因此若出现此情况，说明

为当前基准，此时将

和

中较小的那个放入Worklist中即可同时若

为当前基准，则直接break，因为不能对当前基准重划分 2.4.2 DFA转换为RE（Kleene's Construction）

DFA转换为RE在编译器中不怎么用（个人感觉），但是有时有用，可以用于构造一个最简化的RE，可能在某些场景中有广泛的使用，但是由于个人对这里相关的知识了解不深，暂未想到。还是给出算法步骤如下：

Kleene's Construction算法的大意，是首先搜索DFA，找到各个状态之间的直连路径，构造 $R^0_{ij}$ 矩阵，然后逐步搜索最长路径，最后合并，从而得到最简结果。（没有详细研究，个人学习目的是学习编译器的实现原理，因此没有详细研究，大概看了看，勿怪）

2.5 Scanner2.5.1 Using DFA Minimization to Build a Scanner

到目前为止，根据Knowledge Map，已经学习了

使用Thompson's Construction实现RE-->NFA使用Subset Construction实现NFA-->DFA使用Brzozowski's Algorithm or Hopcroft's Algorithm实现DFA-->Minimal DFA简单介绍了使用Kleene's Construction实现Minimal DFA-->RE

接下来就需要学习如何使用一个Minimal DFA建立一个Scanner（词法分析器）（是的，学了这么多才学完了Scanner的基础理论，编译原理果然是计算机科学的精华:dog:）

2.5.1.1 What's the problem we face ?

首先需要明确Minimal DFA --> Scanner面临的主要问题：

Minimal DFA使得token（词性）识别更加困难

其实这一点很好理解，认真研究上面两个求解Minimal DFA的算法，可以发现，这两个算法将终止状态进行了合并，当然这样可以很快的判断一个字串是否可以接受（Accept），但是这样就难以区分，它到底属于ab还是abc，也就是无法区分词性，只知道字串合法。因此得出如下结论：

不能针对所有的Words求解Minimal DFA（即相同词性的求解Minimal DFA，不同词性的不能合并）2.5.1.2 What's the solution of the problem ?

从具体操作上来说，需要做到如下两点：

保护终止态不能使用一个RE来表示所有的词性（这样难以区分词性）

具体的解决方案是

若采用的是Hopcroft's Algorithm初始划分Partition不能将所有的终止状态作为一个集合，应根据词性划分为不同集合若采用的是Brozozowski's Algorithm每一个语法类别使用一个或多个RE表示每一个RE可以得到一个Minimal DFA给所有的Minimal DFA添加一个Start State，然后使用一次Subset Construction算法2.5.2 Building a Scanner from a Collection of REs

简单总结一下迄今为止学习到的知识，能帮助我们在实现Scanner上走到哪一步

首先我们可以针对某种输入语言的每一个单词创建一个RE，并将它们连接起来（一个原始的REs，不用思考）并使用前面学到的算法获得一个Minimal DFA

明确了我们能做到哪一步之后，就明白了现阶段面临的问题，实现一个Scanner，换句话说，REs到Scanner的过程还差最后一步，即从Minimal DFA到Scanner。Cooper教授在课件中提到，在实际应用中，构造Scanner并不同自动机理论书上写的那样简单。具体来说需要面临哪些问题呢？

首先需要明白DFA并不是一个Scanner

这两者的第一个区别在于功能的不同

DFA的功能

DFA可以识别一个单独的单词

Scanner的功能

接受输入流，并将其划分为单独的单词，并对它们进行分类

对应的解决方案是需要Scanner相比于DFA需要实现一些额外的细节

接受所有的单词DFA遇到EOF时停止Scanner需要找到一个单词并返回该单词当Scanner停止时，立即进行下次调用对单词进行分类Scanner需要返回语法类别和词性实现从终止状态到语法类别的映射Scanner需要维护足够多的终止状态来维护这种映射可以使用查表法实现（使用向量记录每项的接受过程（路径））

第二个区别在于REs可能有歧义

这个问题很好理解，单个的RE含义清晰，但是当多个RE连接到一起时，就不是这样了，举例来说

then是一个关键词还是一个标识符给定的字串可能符合多个状态（可以有多个断句方法）如 donut，到底是do、don、donu还是donut遇到错误状态 s_e

时，需要回退

解决的方法如下

针对一个给定的状态，词性优先级高的优先确定其词性标准的方法是使用优先级策略 Lex和flex均可以实现优先级策略一般采用最长的匹配路径实现在DFA和输入流上的回退功能

如何实现在手工编写的Scanner中识别关键字？

一种可选的实现策略为

建立关键字的hash表，将关键字分割为标识符（这里有点没看懂）将关键字预加载进hash表Scanner将所有的表示符送该表，若匹配成功，则发现一个keyword否则，使用DFA处理

这种策略对一个标识符的词素处理了两次

如果一个Scanner创建了标识符表，这种情况就难以避免为了更加优化，Scanner要最小化处理一个字符的时间一些程序员采用了分离的关键词表，这使得可能出现不仅处理两次的情况

如何处理空格？

不同的语言对空格的处理方式不尽相同

大多数Algol-like语言（一般包括C、C++等，Algol-like的相关资料见参考资料）

空格将暗示一个字的结束，但是也存在特殊情况，如下x + y = z vs x+y=z，这两者的处理结果应相同

在上述情况下，空格是不必要的（空格不应放在特殊位置）

但是对于其他语言，如Python，情况就大不一样

在Python中，空格十分重要，空格串定义了块结构，在这种情况下，Scanner需要计算空格的数目，并在块开始和结束时插入token

如何处理注释？

在大多数情况下，注释是可以直接丢弃的（一些特殊情况除外）

基于表的Scanner的表大小

首先要明确一个事实，状态转换表可能十分巨大，甚至超过L1 cache的大小

那么状态转换表能否压缩呢？

答案是可以的，如下图所示，但是这样处理状态转换表，要求Scanner做相应的修改

具体来说如何压缩状态转换表呢，一般采用如下方法：

以动作为基准对字符进行分类，划分为不同的组，这里的动作指的是状态转换方式状态转换表中相同的列合并使用class来索引表，而不是字符

这种思想在ASCII字符集（or EBCDIC）上工作的很好，而这些字符集的特点是紧凑，面向字节，这使得对字符分类时，类向量的长度很小

针对大型字符集如16bit unicode

具体来说，压缩表的算法如下图所示

一般来说，具有两步

Scanner生成器需要识别相同的列确定映射关系，即构建CharClass和压缩表

加快识别测试的技巧

在构建表时，记录每一列的非错误项数量依照非错误项数量，对每一列进行排序，仅比较具有相同pop count的列或者维护更加复杂的签名（如状态的数目）

如何尽量避免回退（Rollback）？

一些REs会造成 O(n^2) 的回退

如

和它的DFA输入 “ababababc”输入“abababab”

上述情况中出现的回退情形是可以避免的，可以采用如下两种方法

让Scanner记录常用输入的错误路径通过简单的修改，构造maximal munch Scanner

什么是maximal munch scanner？

下图是一个Maximal munch Scanner的框架

Maximal Munch Scanner的特性

使用位向量来跟踪失败路径在InitializeScanner()函数中，同时初始化InputPos和FailedFailed需要的空间正比于输入流大小但是可以通过优化实现来削减需要的空间避免回退构建一个更高效的Scanner设计不会出现二次回退的语言

基于表的Scanner vs 直接编码Scanner

基于表的Scanner（Table-Driven Scanner）大量使用索引

读取下一个字符对该字符进行分类转换到下一个状态跳转top

另一个可选的Scanner编码策略：直接编码（Direct-Coded Scanner）

对程序中的状态进行编码每个状态对应独立的代码在本地和直接分支时进行状态转换测试生成丑陋的的代码（代码可读性差）相比于Table-Driven Scanner更加高效需要进行很少的内存操作，但是可能有很多分支

表查询的开销

每次查询字符类别或者查询状态转换表均会引入地址计算和内存访问操作

也就是说，每次查表操作均为引入多个操作，使得每个字符会造成很多开销，因此避免查表会使得Scanner运行更快

2.5.3 Building Faster Scanners from the DFA

典型的例子是Direct-Coded Scanner，典型的例子如下图，对状态进行了直接编码，每一个状态对应一段独立代码，最后的代码风格丑陋，但是相比于Table-Drive Scanner更加高效

2.5.4 Building a Scanner Generator

如何编写自己的Scanner Generator？

RE解析Top-down，递归下降的解析在解析的过程中可以使用Thompson's Construction算法（边解析，边构建NFA）实现Subset Construction算法实现起来很单调，但是并不难DFA最小化（DFA Minimization） Hopcroft or Brzozowski 编写压缩表可以实现终止态到token type的映射

首先针对RE解析，自动机的终止态可以用于判断语法类别，这里有两点需要注意

Thompson's Construction会在每一步创建新的终止态每一个由Thompson's Construction算法生成的NFA都仅有一个终止态OOPs，面向对象需要一个字一个字的创建NFA，然后使用 $\epsilon$ 转换将它们连接起来

经过上述步骤，接下来就可以针对获得的NFA使用Subset Construction算法，需要明确的是，单独使用Subset，是不会改变终止态的

接下来，Scanner Generator可以使用两种算法最小化NFA（Hopcroft or Brzozowski），这两种算法并没有明显的高下之分，但是需要注意的是这两种算法均会合并终止态，为了保证最后创建的Minimal DFA可以用于词性分类，需要维护终止态

在最小化时维护终止态，有两种可选方案

针对不同字创建DFA，并对其最小化，然后将所有的Minimal DFA连接起来，并进行一次Subset这种方法需要进行许多pass，但是这些pass均是在小DFA上进行的最后的DFA并不是Minimal DFA，但是其终止态很明确使用Hopcroft算法，但是改变初始化初始化（创建Partition和Worklist）时，不再将所有的终止态放在同一个集合，而是依照语义类别划分为不同集合Hopcroft算法在运行中，会对Partition中的集合进行切分，但是并不会将集合进行合并

Hand-Coded Scanner的使用

许多现代编译器使用手写Scanner，而不是生成的Scanner

从DFA简化设计理解开始同时有一些事情并不适合工具生成的Scanner（tool-based）计算一个整数的数值在lex or flex中，许多线程使用sscanf函数，并且多次接收字符可以使用原来的编译技巧，并且更好的计算数值可以将一些相似的状态合并在一起Scanner写起来很有趣紧凑、好理解、debug简单。。。2.5.5 Building Scanners

关键点

目前为止所学的所有技术，均可以帮我我们自动构建Scanner需要写REScanner构建NFA、DFA、Minimal DFA，然后实现代码（table-drive or direct-coded）这种方法可以生成快速，高效的Scanner

对于大多数现代语言特性来说，这种自动构建Scanner的方法有效，但是有两点主要注意

当设计一门编程语言时，要仔细考虑是否引入某一特性现有语言的独特特性，如忽视空格，非保留关键字，还没有证明十分有用（这些特性并不重要，不一定非要加入自己的语言种）

最后，并不是所有的东西均可以使用正则语言描述，因此需要进行下一步，即语法分析（Syntax Analysis）的学习，然后设计语法分析器（Parser）

3 PL/0 语言

本节开始学习PL/0语言，主要学习资料是Wikipedia上面的相关介绍

3.1 Introduction

PL/0是一门专门用于编程语言教学的语言，其语法结构同Pascal十分相似。一般用于作为，编译器教学的对象。PL/0最初由Niklaus Wirth在 Algorithms + Data Structures = Programs这本书中提出。

语言采用非常有限的结构

没有真实数字（不提供浮点数据表示）提供有限的数学操作符除了if和while外，没有其他控制结构

虽然语言结构上的限制导致难以使用这门语言开发实际应用程序，但是它可以帮助编译器保持紧凑和简洁（现代语言由于其丰富的语法结构和强大的功能，使用的编译器往往十分复杂庞大）。

3.2 Grammar（文法 or 语法规则）

下面是使用EBNF格式定义的语法规则

program = block "." ; block = [ "const" ident "=" number {"," ident "=" number} ";"] [ "var" ident {"," ident} ";"] { "procedure" ident ";" block ";" } statement ; statement = [ ident ":=" expression | "call" ident | "?" ident | "!" expression | "begin" statement {";" statement } "end" | "if" condition "then" statement | "while" condition "do" statement ]; condition = "odd" expression | expression ("="|"#"|""|">=") expression ; expression = [ "+"|"-"] term { ("+"|"-") term}; term = factor {("*"|"/") factor}; factor = ident | number | "(" expression ")";

首先直观上来说，其语法规则十分简单（仅使用这么几个形式化语句就可以描述其语法），因此针对PL/0实现一个递归下降的解析器十分简单。因此PL/0常用于编译器构造课程中。当然由于语言特性过于简洁，在实现编译器时，可以根据需要对编译器进行扩展，丰富语言功能。常见的扩展如语法扩展continue，参数传递，或者实现一些数据结构如数组、字符串、浮点数字等。

接下来，按照给出的EBNF学习一下PL/0的语法。

1.如下，一个program由block和一个.组成，也就是说，每个程序以.结尾

program = block "." ;

2.每个block如下所示，其含义是，可声明常数const，且可一次声明多个；可声明变量，且可声明多个，但是变量不能赋值；可以指定procedure（过程名），并在其中声明另一个块（递归定义），且其后必须有一个statement

block = [ "const" ident "=" number {"," ident "=" number} ";"] [ "var" ident {"," ident} ";"] { "procedure" ident ";" block ";" } statement ;

3.statement中定义了赋值语句的规则，一个赋值语句后面可以是表达式，可以是调用另一个procedure，可以是一个?+标识符，可以是!+表达式，可以是一个begin...end（这里也是一个递归定义），可以是if...then...，可以是while...do...

statement = [ ident ":=" expression | "call" ident | "?" ident | "!" expression | "begin" statement {";" statement } "end" | "if" condition "then" statement | "while" condition "do" statement ];

4.condition，定义何为条件语句，主要用于3中的if和while语句，condition可以是odd+表达式（用于判断一个表达式的结果是否是奇数），可以是两个表达式之间的关系

condition = "odd" expression | expression ("="|"#"|""|">=") expression ;

5.expression，定义表达式的格式，词语加减

expression = [ "+"|"-"] term { ("+"|"-") term};

6.term，定义词语的组成，操作数乘除

term = factor {("*"|"/") factor};

7.factor，定义操作数可以使用的表示方法，可以是一个标识符（变量），可以是直接的数字，可以刻是一个表达式（需要使用括号括起来）

factor = ident | number | "(" expression ")";

PS：发现没有，5、6、7直接决定了优先级

3.3 Use in education（Why PL/0）

编译领域的主要文章十分喜欢PL/0，因为其引入了几个有影响力的概念（这些概念同样出现在其他语言的语法中），如步长自适应、递归下降解析、EBNF、P-code、T-diagrams（Tombstone diagram，就是课上讲的那个类似俄罗斯方框的那个，详情看参考文献））。一些年前，大学课程偏离了Wirth的课程集，代之通过使用lex和yacc的经典的递归下降技术。最近的一些实现延续了这个方法，同时结合了现代的面向对象和设计模式的概念，使得学生在实现PL/0时更靠近当代编程风格。

3.4 Compiler Construction（编译构造）

1976年，Wirth写了一本关于编译器构造的书，并给出了PL/0的编译器源码。上面给出的规则就是该书第一版使用的语法规则，该书名为Compilerbau。在之后的版本中，随着Wirth的研究不断进展，书中提高的语法规则不断改动。具体来说，他将const和procedure改为大写。这种改变使得PL/0同Modula-2更加接近。同时，Wirth的朋友和合作者 C. A. R. Hoare ，正在研究communicating sequential processes 概念（CSP并发模型），在该模型中使用了！标记，和？标记来表示通信原语。Wirth将这两个符号添加到PL/0中，但是并没有在书中提及这两个符号的语义。

3.5 PL/0 Example

Wikipedia中给出了三个例子，这三个例子中都提到了！的用法变化，需要可以查看，这里不再copy。

3.6 PL/0 相关资料

4 Flex4.1 Introduction

Flex（fast lexical analyzer generator），是一个开源词法分析器生成工具。专门用于自动化生成scanner（or lexers）。Flex经常同YACC或bison（YACC，的一个版本）一同用于构建语法实现（实现编译）。Flex并不是GNU项目的一部分（bison是）。

Flex只能生成c或c++代码。在其他语言中使用Flex生成的代码可以使用类似SWIG的工具。

Bison，是GNU项目中的一个语法分析器（Parser），Bison的输入一般为使用BNF描述的上下文无关文法，并生成可以处理tokens的语法分析器，可以将tokens转换为语法明确的类别。（现阶段刚完成词法分析相关理论的学习，这里主要介绍Flex）

4.2 Installation

我的实验环境使用Ubuntu Desktop 22.04，更换了清华源，下面依次介绍一下基本的环境构建过程

4.2.1 Ubuntu 22.04 换清华源

我个人在处理类似问题时，比较喜欢首先参考官网资料，清华源中关于Ubuntu换源的介绍在下面这个网址，当然我也写在了参考资料部分，可以参考。

https://mirrors.tuna.tsinghua.edu.cn/help/ubuntu/

这里存在一些问题，清华源镜像的官方帮助并没有更新Ubuntu 22.04的文档，但是我浏览了镜像内容，发现其实该镜像源已经完成了Ubuntu 22.04 的镜像工作，因此，在参考官方文档的基础上做一些小小的改动即可。具体的操作如下：

修改/etc/apt/sources.list 文件即可（记得备份），这里就不再给出具体的修改命令，给出修改后的文件内容如下：

deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ jammy main restricted universe multiverse # deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ jammy main restricted universe multiverse deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ jammy-updates main restricted universe multiverse # deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ jammy-updates main restricted universe multiverse deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ jammy-backports main restricted universe multiverse # deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ jammy-backports main restricted universe multiverse deb https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ jammy-security main restricted universe multiverse # deb-src https://mirrors.tuna.tsinghua.edu.cn/ubuntu/ jammy-security main restricted universe multiverse

PS:技术上来说更改代号名即可，这个技巧同时也可以用于安装不同版本的软件，比如在Ubuntu 22.04上安装Ubuntu 16的软件，换代号即可。Ubuntu 22.04 的代号是Jammy Jellyfish。各个版本的代号可以在Ubuntu官网查到，当然也可以去参考资料中找。

PS:不要忘了apt update哦

4.2.2 安装Flex & GNU Bison

可以通过apt直接安装，给出如下命令：

sudo apt install git curl sudo apt install build-essential sudo apt install flex bison4.2.3 zsh & oh-my-zsh（可忽略，更详细的教程可看我另一篇文章，专门介绍构建一个好看的shell的）

这一节是简单记录一下安装并美化zsh的过程，很久之前写过一篇博客，但是最近Github由于众所周知的原因难以即时访问，以前的方法需要进行修改。整理过程如下：

Step 1：install zsh & git

sudo apt install zsh git

Step 2: clone and unzip oh-my-zsh, powerline-fonts, powerline

cd ~/Desktop git clone https://gitee.com/mirrors/oh-my-zsh.git git clone https://gitee.com/yanzhongqian/powerline.git git clone https://gitee.com/PedroNull/powerline-fonts.git

Step 3: 修改oh-my-zsh中的install.sh文件（自带的install.sh文件默认访问Github，这里修改为Gitee）（该文件在oh-my-zsh的tools文件夹下），改为如下：

# Track if $ZSH was provided custom_zsh=${ZSH:+yes} # Default settings ZSH="${ZSH:-$HOME/.oh-my-zsh}" REPO=${REPO:-mirrors/ohmyzsh} # 第一个修改的地方 REMOTE=${REMOTE:-https://gitee.com/${REPO}.git} # 第二个修改的地方 BRANCH=${BRANCH:-master} # Other options CHSH=${CHSH:-yes} RUNZSH=${RUNZSH:-yes} KEEP_ZSHRC=${KEEP_ZSHRC:-no} command_exists() { command -v "$@" >/dev/null 2>&1 }

Step 4: run install.sh

sh install.sh

Step 5: install powerline-fonts

cd powerline-fonts ./install.sh

Step 6: fontconfig 配置字体（将powerline的两个文件放到对应的位置）

mv ~/Desktop/powerline/font/PowerlineSymbols.otf ~/.local/share/fonts/ sudo fc-cache -f -v mkdir -p ~/.config/fontconfig/fonts.conf mv ~/Desktop/powerline/font/10-powerline-symbols.conf ~/.config/fontconfig/fonts.conf/

Step 7: 更改zsh的theme

gedit ~/.zshrc

Step 8: 更改默认shell为zsh

chsh -s /bin/zsh4.3 Flex 基础

这里简要介绍一下flex的基本功能和输入文件编写规范

4.3.1 Flex 的基础功能

这里简单分析一下Flex -h 的内容

Usage: flex [OPTIONS] [FILE]... Generates programs that perform pattern-matching on text. Table Compression: -Ca, --align trade off larger tables for better memory alignment -Ce, --ecs construct equivalence classes -Cf do not compress tables; use -f representation -CF do not compress tables; use -F representation -Cm, --meta-ecs construct meta-equivalence classes -Cr, --read use read() instead of stdio for scanner input -f, --full generate fast, large scanner. Same as -Cfr -F, --fast use alternate table representation. Same as -CFr -Cem default compression (same as --ecs --meta-ecs) Debugging: -d, --debug enable debug mode in scanner -b, --backup write backing-up information to lex.backup -p, --perf-report write performance report to stderr -s, --nodefault suppress default rule to ECHO unmatched text -T, --trace flex should run in trace mode -w, --nowarn do not generate warnings -v, --verbose write summary of scanner statistics to stdout --hex use hexadecimal numbers instead of octal in debug outputs Files: -o, --outfile=FILE specify output filename -S, --skel=FILE specify skeleton file -t, --stdout write scanner on stdout instead of lex.yy.c --yyclass=NAME name of C++ class --header-file=FILE create a C header file in addition to the scanner --tables-file[=FILE] write tables to FILE --backup-file=FILE write backing-up information to FILE Scanner behavior: -7, --7bit generate 7-bit scanner -8, --8bit generate 8-bit scanner -B, --batch generate batch scanner (opposite of -I) -i, --case-insensitive ignore case in patterns -l, --lex-compat maximal compatibility with original lex -X, --posix-compat maximal compatibility with POSIX lex -I, --interactive generate interactive scanner (opposite of -B) --yylineno track line count in yylineno Generated code: -+, --c++ generate C++ scanner class -Dmacro[=defn] #define macro defn (default defn is '1') -L, --noline suppress #line directives in scanner -P, --prefix=STRING use STRING as prefix instead of "yy" -R, --reentrant generate a reentrant C scanner --bison-bridge scanner for bison pure parser. --bison-locations include yylloc support. --stdinit initialize yyin/yyout to stdin/stdout --nounistd do not include --noFUNCTION do not generate a particular FUNCTION Miscellaneous: -c do-nothing POSIX option -n do-nothing POSIX option -? -h, --help produce this help message -V, --version report flex version

Usage

使用方法这里可以看到flex需要控制参数和输入文件，但是这两个均是可选的，也就是说flex可以直接运行，不用提前给出输入文件

Table Compression

在前面的基础内容中提到，基于表的Scanner往往受到表大小的影响，在这方面flex给出了一些表压缩选项，可以根据需要选择。

Table Compression: -Ca, --align trade off larger tables for better memory alignment -Ce, --ecs construct equivalence classes -Cf do not compress tables; use -f representation -CF do not compress tables; use -F representation -Cm, --meta-ecs construct meta-equivalence classes -Cr, --read use read() instead of stdio for scanner input -f, --full generate fast, large scanner. Same as -Cfr -F, --fast use alternate table representation. Same as -CFr -Cem default compression (same as --ecs --meta-ecs)

-Ca or --align 指flex可以根据状态转换表大小自动决定

-Ce or --ecs 构建等价的类别，指flex自动合并类别，也是用于缩小表大小，其基础原理也在前面提到过

-Cf 不压缩表

-CF 不压缩表

-Cm or --meta-ecs 构建元等价类别，基本含义同前面那个类似，也是创建新的类别，用于压缩表，这里可能压缩的更加高级，后面实验可以看看

-Cr or --read 使用read函数而不是标准I/O（flex只能生成c or c++代码，这里指的读取输入流所用的函数）

-f or --full 生成快速大的scanner，也就是理论学习部分起到的direct-coded scanner，使用表

-F or --fast 使用可选的表表示形式，这里不太懂，可能使用了更好的表表示形式

-Cem 默认压缩，同--ecs or --meta-ecs功能相同，也就是给出了默认选项

Debugging

Debug控制参数，用于控制debug的情况

Debugging: -d, --debug enable debug mode in scanner -b, --backup write backing-up information to lex.backup -p, --perf-report write performance report to stderr -s, --nodefault suppress default rule to ECHO unmatched text -T, --trace flex should run in trace mode -w, --nowarn do not generate warnings -v, --verbose write summary of scanner statistics to stdout --hex use hexadecimal numbers instead of octal in debug outputs

-d or --debug 允许debug模式

-b or --backup 将备份信息写道 lex.backup

-p or --pref-report 通过stderr输出性能报告，应该是给出运行时间和对生成的scanner的评估啥的

-s or --nodefault 不输出没有匹配成功的文本

-T or --trace flex使用trace模式运行

-w or --nowarn 不生成警告信息

-v or --verbose 将scanner的静态分析报告通过stdout输出

--hex debug时使用16进制而不是10进制输出

Files

这里控制用到的文件，主要是输出文件

Files: -o, --outfile=FILE specify output filename -S, --skel=FILE specify skeleton file -t, --stdout write scanner on stdout instead of lex.yy.c --yyclass=NAME name of C++ class --header-file=FILE create a C header file in addition to the scanner --tables-file[=FILE] write tables to FILE --backup-file=FILE write backing-up information to FILE

-o or --outfile=File 指定输出文件名

-S or --skel=File 指定框架文件名（基础理论部分提到过，scanner一般由skeleton + table组成）

-t or --stdout 将scanner输出到stdout，而不是lex.yy.c文件

--yyclass=NAME 生成的scanner采用的c++类名

--header-file=File 单独生成一个C头文件

--table-file=File 将表写到指定文件

--backup-file=File 将备份信息写道指定文件

Scanner behavior

控制词法分析器（Scanner）行为的参数

Scanner behavior: -7, --7bit generate 7-bit scanner -8, --8bit generate 8-bit scanner -B, --batch generate batch scanner (opposite of -I) -i, --case-insensitive ignore case in patterns -l, --lex-compat maximal compatibility with original lex -X, --posix-compat maximal compatibility with POSIX lex -I, --interactive generate interactive scanner (opposite of -B) --yylineno track line count in yylineno

-7 or --7bit 生成7bit的scanner，应该指的状态编码位数

-8 or --8bit 生成8bit的scanner

-B or --batch 生成批处理scanner，其功能同-I相反

-i or --case-insensitive 忽略模式中的case

-l or --lex-compat 最大化同lex（另一个类似flex的软件）的兼容性

-X or --posix-compat 最大化同POSIX lex的兼容性

-I or --interactive 生成交互式scanner，其功能同-B相反

--yylineno 跟踪yylineno中的行计数，不知道啥意思，实验中看

Generated code

控制生成代码的参数

Generated code: -+, --c++ generate C++ scanner class -Dmacro[=defn] #define macro defn (default defn is '1') -L, --noline suppress #line directives in scanner -P, --prefix=STRING use STRING as prefix instead of "yy" -R, --reentrant generate a reentrant C scanner --bison-bridge scanner for bison pure parser. --bison-locations include yylloc support. --stdinit initialize yyin/yyout to stdin/stdout --nounistd do not include --noFUNCTION do not generate a particular FUNCTION

-+ or --C++ 生成C++ scanner 类

-Dmacro=defn 定义宏大小，一般指批处理中每批大小，应该跟上面那个-B参数对应

-L or --noline 不使用#line 这个参数用于引用某个文件的第几行，这个功能好奇怪，应该是为了增加代码可读性

-P or --prefix=STRING 更改前缀，不再使用yy

-R or --reentrant 生成一个可重入的scanner，也就是说运行一次不结束，可以运行第二次

--bison-bridge 生成一个scanner，可以同bison生成的parser协同

--bison-locations 加入yylloc支持，这里不太懂，需要实验

--stdinit 初始化yyin/yyout到stdin/stdout

--nounistd 不include unistd.h文件，这个文件用于linux/unix系统调用

--noFunction 不生成确定函数

Miscellaneous

混合参数，可视为其他参数

Miscellaneous: -c do-nothing POSIX option -n do-nothing POSIX option -? -h, --help produce this help message -V, --version report flex version

-c POSIX中的do-nothing选项

-n POSIX中的do-nothing选项

-h or --help 帮助信息

-V or --version flex版本信息

4.3.2 Flex输入文件编写规则

flex的输入文件由一系列的RE+c语言代码组成，称为rules。rules用于描述scanner的功能。具体来说输入文件的格式包括三部分。在Flex的使用手册中，给出的输入文件结构如下所示：

definitions %% rules %% user code

即包括definitions，rules & user code 接下来分别学习一下每部分的功能和基本格式

4.3.2.1 Definitions

本节用于name definitions、start conditions

name definitions 用于简化scanner规则（rules，即下面的rules） start conditions 会在后续节中进行解析

name definitions

其采用的格式为

name definition

其中name可由字母或下划线开头，后跟字母、数字、下划线或减号（当然后面也可以不跟东西）。definition从name后面第一个不为空格的字符开始，直到改行末尾。definition可由对应的name引用。举例来说：

DIGIT [0-9] ID [a-z][a-z0-9]*

上面的例子DIGIT定义为一个正则表达式（单数字），ID定义为由字母开头的一串字符。对应来说，在采用上述代码后，后面rule部分的代码会进行如下替换（{name}同(definition)替换）

{DIGIT}+"."{DIGIT}* ([0-9])+"."([0-9])*

除此之外还有一些规则

未缩进的注释，如采用'/*'的多行注释，会直接copy到输出

缩进的文本，或者采用'%{'和'%}'包裹的文本也会在取出这两个标记符号后，copy到输出，'%{'和'%}'不可缩进

%top块的处理同'%{'和'%}'类似，不同的是，%top块中的代码会放到输出文件的头部，在任何flex定义之前。%top块可用于定义宏或者引用特定文件。可以使用多个%top块，flex会维护其顺序。常见的用法如下所示：

%top{ /* This code goes at the "top" of the generated file. */ #include #include }

start conditions

4.3.2.2 rules

rules的定义形式同definitions类似，如下所示

pattern action

其中pattern不可缩进，action必须和对应的pattern在同一行。

在rules节中，可以使用缩进文本或使用'%{'和'%}'包裹的文本声明变量，这些变量位于进行scanning时均会执行的位置。在其他位置也可以使用该语法，但是这些位置的变量并不声明具体含义，可能发生compile-time errors。

Patterns

flex的手册中单独使用了一节，用于介绍pattern，因为这里是flex的核心，也是自动生成的scanner的核心。前面的基础知识中介绍过，一个词法分析器是从正则表达式开始的（RE），这里就是在定义RE

patterns使用正则表达式的扩展集编写具体来说，如下所示

idpattern含义1x匹配字符x2.匹配任意字符，除了换行符3[xyz]匹配字符类，此例中为x or y or z4[abj-oZ]匹配字符类（包含范围），此例中为a or ab or 从j到o的左右字符 or Z5[^A-Z]匹配字符类的补集，即除了该类中的字符的其他字符可被匹配，此例中为除了大写字符之外的所有其他字符6[^A-Z\n]匹配字符集的补集，此例为除了大写字符和换行符之外的所有字符7[a-z]{-}[aeiou]匹配辅音字母8r*r重复0次或多次（r+为重复1次或多次）9r?r重复0次或1次10r{2,5}r重复2-5次11r{2,}r重复>=2次12r{4}r重复4次13{name}调动name定义（definitions节中定义）14"[xyz]\"foo"该例对应的合法字串为[xyz]"foo，这个例子中包含两个意思，一个是双引号的用法，一个是转义符号15\XX可以为a or b or f or n or r or t or v（ANSI-C中的几个制表符），若均不是则匹配X字符16\0空字符（ASCII中编码为0）17\123匹配ASCII中编码为十进制123的字符18\x2a匹配ASCII中十六进制2a的字符19(r)匹配一次r，括号用于控制优先级20(?r-s:pattern)r和s为option参数，其中r为接收参数，s为忽略参数，r和s可以为i，s or x；i意为大小写不敏感（case-insensitive），-i意为大小写敏感（case-sensitive）；s改变.的语义为匹配任意单字节字符，-s改变.的语义为匹配任意单字节字符，除了换行符\n；x意为忽略RE中的注释和空格，除了使用转义字符的空格（并使用双引号）21(?# comment )忽略括号中的RE，一般用于添加注释22rs连接（concatenation）23r|s匹配r或s24r/s匹配r，且要求其后面跟着s。尾部上下文（trailing context）25^r匹配r，但是要求处于行开始处26r$匹配r，但是要求处于行尾27\r匹配r，但是其匹配条件为s，s即为start condition，在definitions中定义28r同上一条相同，但是要求满足三个条件29r同上一条，但是要求满足所有条件30文件终止符31同上，但是要求满足两个条件

优先级（Precedence）

*>|

字符集（Character Class）

flex提供一系列字符集，可以直接用于匹配，如下所示：

[:alnum:] [:alpha:] [:blank:] [:cntrl:] [:digit:] [:graph:] [:lower:] [:print:] [:punct:] [:space:] [:upper:] [:xdigit:]

其定义采用标准C语言中的 isXXX 函数中采用的字符集，如[:alnum:]同isalnum()函数中的匹配规则相同。

Example

下面四个RE的匹配内容相同

[[:alnum:]] [[:alpha:][:digit:]] [[:alpha:][0-9]] [a-zA-Z0-9]

PS：使用手册中通过举例给出了常见的RE编写问题（歧义），值得一看。

4.3.2.3 user code

user code会直接copy到输出（lex.yy.c）的对应位置中。这一节（user code）可忽略，若不编写该节，对应的%%也可去掉。

4.3.2.4 comments

flex采用c-style注释。flex会将注释copy到输出文件的对应位置。注释可在任意位置编写，但是下述两种情况不可编写注释

不可出现在Rules中flex解析RE的地方%option行不可出现注释

下面的注释位置是合法的

%{ /* code block */ %} /* Definitions Section */ %x STATE_X %% /* Rules Section */ ruleA /* after regex */ { /* code block */ } /* after code block */ /* Rules Section (indented) */ { ruleC ECHO; ruleD ECHO; %{ /* code block */ %} } %% /* User Code Section */4.4 Test（flex基本用法简单试验）

假设要生成一个可以识别IPv4地址的Scanner（识别地址并计数），首先给出IPv4地址的RE如下（可以在flex使用手册中找到，在最后面）：

dec-octet [0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5] IPv4address {dec-octet}\.{dec-octet}\.{dec-octet}\.{dec-octet}

接下来编写flex输入文件如下

int num_ipv4; dec-octet [0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5] IPv4address {dec-octet}\.{dec-octet}\.{dec-octet}\.{dec-octet} %% {IPv4address} ++num_ipv4; %% int main(int argc, char **argv){ ++argv, --argc; printf("%d:%s", argc, argv[0]); if(argc > 0) yyin = fopen(argv[0], "r"); else yyin = stdin; yylex(); printf("get %d of ipv4\n", num_ipv4); }

首先使用flex生成scanner源文件

flex lexer.l

然后使用gcc编译源文件

gcc lex.yy.c -lfl -o scanner

接下来编写测试文件testfile.txt，内容如下;

255.255.255.0 255.255.0.0 255.0.0.0 0.0.0.0 1.1.1.1

接下来使用生成的scanner，看是否能识别ip地址

./scanner testfile.txt

运行结果如下

实验结束。

5 By the end

至此词法分析（Lexical Analysis）的理论部分及构建对应的词法分析器（Scanner）的基础理论完结。耗时一周，感谢老师的授课及提供的资料，吴老师Knowledge Map清晰明确，让我可以更好的掌握自己的学习进度，Cooper教授的课件简单易懂，对学习的帮助十分大。

最后再次强调，此次重新学习编译原理的相关知识，主要目的是实现编译器，用于实际实验研究工作，即以实践为目的，对其中的专业名词等，以理解为关键点，并没有过多关注术语的准确性（当然这是不对的），可能有些错误，后续学习时若有新的感悟、理解，或者发现错漏，会进行修改，同时欢迎各位大佬指出问题。

再次，感谢！

参考资料

"ALGOL编程语言，自我小众，却让高级语言由此迎来大发展". 知乎专栏, 2022, https://zhuanlan.zhihu.com/p/161314123. Accessed 27 Apr 2022.

Cooper教授课件

"PL/0 - Wikipedia". http://En.Volupedia.Org, 2022, http://en.volupedia.org/wiki/PL/0. Accessed 27 Apr 2022.

"Extended Backus–Naur Form - Wikipedia". http://En.Volupedia.Org, 2020, http://en.volupedia.org/wiki/Extended_Backus%E2%80%93Naur_form. Accessed 27 Apr 2022.

"Tombstone Diagram - Wikipedia". http://En.Volupedia.Org, 2022, http://en.volupedia.org/wiki/Tombstone_diagram. Accessed 27 Apr 2022.

"Communicating Sequential Processes - Wikipedia". http://En.Volupedia.Org, 2020, http://en.volupedia.org/wiki/Communicating_sequential_processes. Accessed 27 Apr 2022.

"P-Code Machine - Wikipedia". http://En.Volupedia.Org, 2014, http://en.volupedia.org/wiki/P-code_machine. Accessed 27 Apr 2022.

Association, Tsinghua. " Ubuntu | 镜像站使用帮助 | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror". http://Mirrors.Tuna.Tsinghua.Edu.Cn, 1970, https://mirrors.tuna.tsinghua.edu.cn/help/ubuntu/. Accessed 28 Apr 2022.

"Releases - Ubuntu Wiki". http://Wiki.Ubuntu.Com, 2022, https://wiki.ubuntu.com/Releases. Accessed 28 Apr 2022.

【本文地址】

公司简介

联系我们