本文共 304 字,大约阅读时间需要 1 分钟。
编译原理之将正则表达式变为有穷自动机
从正则表达式变为NFA
- 首先先看看简单的基本的正则表达式是如何对应的相关的NFA的
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526115304350.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526115311723.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526115321695.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526115329778.png)
实例将对应的r=(a|b)*abb转成对应的NFA
- 将r当作一个正则表达式,直接带入整体
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526115434989.png)
- 将与连接的直接分解成顺序结构
![在这里插入图片描述](https://img-blog.csdnimg.cn/2020052611564150.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526115712974.png)
- 将或运算进行拆解
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526115731785.png)
基本思路就是不断地增加新地点,有的可能会用不同地方式进行替代,如采用Thompson法进行替代
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526144913431.png)
- 用下图代替ab
![在这里插入图片描述](https://img-blog.csdnimg.cn/2020052614492026.png)
- 用下图代替a*
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526144926276.png)
例题
构建((0|1*)|0)*11对应的NFA
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200526145534521.png)
转载地址:http://yggpb.baihongyu.com/