实验一基于的词法分析实验_词法分析程序的自动生成器（一）——概述

客官°小女子只卖身不卖艺 2023-01-06 11:46 175阅读 0赞

![1de3c9bf70652ea4cea8fbfee5a4b503.png][]

**碎碎念：**

这学期学完了编译原理课程，刚开始学就对写编译器很感兴趣，结果发现学的东西是有正则文法，正则表达式，有穷自动机。刚开始很不清楚学习这个和写编译器有什么关系，查了很多资料，才明白，这种是词法分析程序的自动生成器的理论基石。早期的lex，再到flex，都是人们为了自动构造词法分析器而制作出的工具。而现在的编译原理语言，大多数选择手写词法分析程序。但是，既然学了这么多自动机，尤其像NFA到DFA的转换算法，以及DFA的化简算法，书上说的这么明白，不去实现一下，觉得手痒。于是就动手去写了类lex。(其实差远了)

刚开始接触编译原理，走了很多弯路，才搞清楚两者的关系，为了方便大家，我总结如下：

**1.大多数编译原理书上学的词法分析，包括龙书，虎书。介绍的正则表达式，有穷自动机，都是词法分析程序的自动生成器。**

**2.而大多数编译器考虑到性能和效率，都会采用手工构造的方式直接编写词法解析器。再介绍一下就是用程序设计语言，直接来写词法分析程序。**

**学习方法：**

搞清楚这个之后，我说一下我的想法，对目前的我来言，觉得提高编程能力最快的方法就是：**不是去死学语言语法，没有人能通过死读书去记住这么多语法规则，而是你知道一个东西的具体应用，也知道它的输入和输出，以及其中算法的思想或者是伪代码描述，去亲自结合算法去思考它的数据结构，去思考算法的实现。在这个过程中，多去利用搜索引擎去看看别人实现它的思路，主要去看看被人用了什么技术，然后去学习专门的技术，边学边用的技术很重要，实现了之后，再去看别人是怎么实现的，再去完善自己的代码。这也是轮子哥提倡的学习编程最好的方法，缺点就是花费的时间有点多。**

基于这个思想，我就花费时间写了一个类似lex的词法分析程序的自动生成器。在这个过程中，看了很多资料，收获了很多，今天分享出来。

--------------------

我这个人很喜欢教东西的时候，替别人考虑，万一读不懂怎么办？所以我首先简单说一下，这个教程的使用方法：**本教程，主要是把构造词法分析器自动生成器的方法串起来教给你。因为所有书，包括龙书，虎书，都没有串起来讲，都只是介绍单独一个算法，例如从正则到NFA,或者从NFA到DFA,DFA的最小化。并没有说其中实现的细节。我不会去讲，DFA和NFA是什么，这在任何一本编译原理书上都可以找到。我只是帮你串起来。代码不一定会透露出来，因为我水平有限，害怕误人子弟，但是我提供一种思路把。希望大家不要被我局限，因为我真的很辣鸡。**

**具体实现：**

**一.概述**

主要思想：

正则表达式是描述单词符号的一种方便的工具，适合于人阅读。但机器阅读正则表达式是十分困难的，而且，用正则表达式直接进行词法分析，不仅工作量大，速度缓慢。因此，我们引入一种专门为机器设计的表达形式-有穷自动机。我们可以通过Thompson算法把正则表达式转换成有穷自动机。

**简介概括，就是我们把程序设计语言的每一种单词类别整理成若干个正则表达式，通过Thompson算法分别转换成ε-NFA，再把ε-NFA连接起来，组成一个大的NFA，通过子集法把NFA转换成DFA，必要时，把转换成的DFA使用分割法化简成最小的DFA，再通过基于DFA的词法分析驱动程序即可进行词法分析。**

主要过程如下：

![dc6ef51a0e0e658b0fb0758b2075f23a.png][]

最后强调一下输入，输出。

1输入：识别描述词法规则的正则表达式

2输出：对应能识别对应语言的有穷自动机

3词法分析过程：在基于DFA的词法分析程序驱动器下，根据生成的DFA对相应语言进行词法分析。

下期预告：

1.Thompson算法把正则表达式解析成NFA。不显式的构造抽象语法树的过程中生成NFA，构造正则表达式的抽象语法树的过程和构造算术表达式的抽象语法树的过程类似，都一样会存在运算符优先级和括号处理的问题。（这个困扰当时非常困扰我的一个地方）

碎碎念：

勿在浮沙筑高台，基础是关键，本辣鸡去学习C++了。

[1de3c9bf70652ea4cea8fbfee5a4b503.png]: /images/20221119/6293c0c68bf3493c9741922bdacbbcea.png
[dc6ef51a0e0e658b0fb0758b2075f23a.png]: /images/20221119/caef5deb84954683985e76ba908c24b7.png