编译原理笔记4:从正规式到词法分析器(1):构造词法分析器的一般步骤、从正规式到 NFA,Thompson 算法-阿里云开发者社区

开发者社区> marsCatXDU_李经纬@西电> 正文

编译原理笔记4:从正规式到词法分析器(1):构造词法分析器的一般步骤、从正规式到 NFA,Thompson 算法

简介:
+关注继续查看

一般方法和步骤

  1. 用正规式描述模式(描述词法规则);
  2. 为每个正规式构造一个 NFA ,这个 NFA 识别正规式表示的正规集(即,将正规式转成 NFA。正规式和NFA在这里就描述同一个正规集了,他们两个是等价的);
  3. 将上一步得到的 NFA 转换成与之等价的 DFA ,这一步叫做”确定化“;
  4. 优化上一步得到的 DFA,使其状态数最少,这一步叫做 ”最小化“;
  5. 从 上一步 得到的 DFA 来构造词法分析器。

在上面的步骤中,我们通过 NFA 构造 DFA 而非直接构造 DFA ,是因为有专门的算法工具来一步步完成从正规式->NFA->DFA->分析器的工作。这样我们就可以省略中间的手工劳动步骤。
3_6
虚线框内部的,就是 Lex 的工作内容和原理。

我们使用的时候,直接从正规式使用工具转化为词法分析器就可以了。接下来我们从正规式开始一步步搞懂词法生成器是怎么一回事。

从正规式到NFA

先复读一下正规式:正规式是用来描述词法规则的,也就是描述:记号该长成什么样子、数字该长成什么样子之类。

Thompson 算法

它的任务,是将正规式转化为与其等价的 NFA。

也就是说,它可以将任意的字母表 Σ 上的正规式 r ,转化为一个能够接受 L(r) 的 NFA N。

想要构造一个正规式,我们需要从最简单的正规式(也就是 ε 和一个个字母)开始,通过一步步添加运算,逐步把它构造成我们想要的目标正规式。最简单的正规式就是 ε 和字母表上的一个个字符。
3_7
NFA 的构造步骤和正规式的构造步骤是相同的,构造两种东西的每一步都可以对应起来。因此,NFA 也要从最开始的小 NFA 开始构造。

每一种 NFA 都能和一个正规式相对应,如下图所示
3_8
回忆NFA,再观察上图中的正规式和NFA 3~6 可以发现这样的一个问题:

Q:我们知道自动机可以有多个终态,可是 3-6 的这几个自动机直接使用已有的自动机作为自己的一部分,怎么可以假设这些被包含的自动机只有一个终态呢?

A:这是因为图中的 NFA 都是递归构造出来的——也就是说,我们认为上面3-6自动机中的 N(P)、N(Q) 自动机也都是用 Thompson 构造算法构造的,而只要是该算法构造出的 NFA,就一定都是只有一个终态的。

而且,其实对于任意的多终态 NFA,我们都可以把它转化一个单终态NFA——方法非常简单,只需要将它的所有终态引出一条 ε 边,指向一个唯一的新终态即可。

例:用 Thompson 算法构造正规式 r=(a|b)*abb 的 NFA N(r)

先从最小的正规式对应的 NFA 开始构造,再把得到的 NFA 进行组合,得到最终的 NFA 。
3_9
注意:

  • 该算法中,NFA 的构造与正规式的构造步骤是一一对应的;
  • 构造一个新的 NFA ,最多会增加两个状态(始、终),对于连接运算,则会减少状态。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
纯C实现的词法分析和lex实现的词法分析的对比
版权声明:您好,转载请留下本人博客的地址,谢谢 https://blog.csdn.net/hongbochen1223/article/details/50523336 (一):写在前面 在上面的学习当中,我们通过简单的lex例子,进一步扩展lex例子,通过和yacc的融合来进行简单英语语法分析。
813 0
CI中的控制器中要用model中的方法,是统一写在构造器方法中,还是在每一个方法中分别写
Q:     CI中的控制器中要用model中的方法,是统一写在构造器方法中,还是在每一个方法中分别写 A:     建议统一写,CI框架会自动识别已经加载过的类,所以不用担心重复加载的问题     class C_User extends CI_Controller { ...
617 0
IDA反汇编/反编译静态分析iOS模拟器程序(二)加载文件与保存数据库
启动windows版的IDA,在Quickstart界面点击New,弹出一个对话框选择文件。也可以按取消后再把文件拖进IDA。由于Mac版的IDA没注册,没有save功能,所以只好先把Mac上的东西拷贝到windows再打开了。
1056 0
IDA反汇编/反编译静态分析iOS模拟器程序(四)反汇编的符号信息与改名
首先看看windows IDA和xcode的反汇编有什么不同。因为不确定直接分析UIKit的代码会不会有法律问题,还是自己写个例子吧。分析UIKit的时候因为没有完整的debugging symbols,所以得到的反汇编信息会比自己写的代码较少。
848 0
IDA反汇编/反编译静态分析iOS模拟器程序(五)F5反编译
反编译是IDA最让人振奋的功能,它的本质是IDA的一个插件,不过会被当做hex-rays的另一个产品。既然是产品,那当然就另外收费,demo版是没有的。
1056 0
应用统计学与R语言实现学习笔记(十二)——主成分分析
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/ESA_DSQ/article/details/78062883 Chapter 12 Priciple Component Analysis 本篇是第十二章,内容是主成分分析。
957 0
19
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载