转化为NFA"/>
编译原理实验——正则表达式转化为NFA
目录
- 1、实验目的与内容
- 2、程序总体设计思路和框架
- 3、主要的数据结构和流程描述
- 4、测试结果与说明
- 5、实验收获与反思
- 附录
- 参考资料
1、实验目的与内容
输入:一个正则表达式(例如“(a|b)*abb”)
输出:对应的一个NFA的mermaid语法
graph LR
0((0))-->|a| 1((1))
1((1))-->|$| 5((5))
2((2))-->|b| 3((3))
3((3))-->|$| 5((5))
4((4))-->|$| 2((2))
4((4))-->|$| 0((0))
5((5))-->|$| 4((4))
5((5))-->|$| 7((7))
6((BEG))-->|$| 4((4))
6((BEG))-->|$| 7((7))
7((7))-->|$| 8((8))
8((8))-->|a| 9((9))
9((9))-->|$| 10((10))
10((10))-->|b| 11((11))
11((11))-->|$| 12((12))
12((12))-->|b| 13((END))
对应的NFA:
2、程序总体设计思路和框架
总程序分为两份代码,第一份代码将一个正则表达式(regular expression)转化为后缀形式,第二份代码把得出的后缀式转化为NFA并且输出对应NFA图形的mermaid语法。
如下图:
ReExToNFA.cpp:
ReExToNFA2.cpp:
一个正则表达式中有四种运算符号:闭包运算符(*)、连接符(.)、或运算符(|)和括号,运算符的优先级依次递减,在中缀形式中连接符通常被省略,所以构建出的后缀式要补上连接符。得到后缀式之后,使用MYT算法根据后缀式构建NFA。
这里简单讲一下中缀转后缀的算法流程:
3、主要的数据结构和流程描述
结构体NFA的定义如下:
struct NFA
{set<int> Q; //状态集合set<char> sigma; //输入字符集合vector<int> delta[128][128]; //状态转化函数,一个状态对应的一个输入可能有两个以上的转移,使用数组不行!!!int q0; //开始状态set<int> F; //接收状态的集合NFA() //构造函数{//memset(delta, -1, sizeof(delta));//-1表示为此状态没有此输入。}
} NFAinstance;
注释中已经有了详尽的说明。
4、测试结果与说明
测试结果以及输出见第2部分。
5、实验收获与反思
本实验的关键点在于:
1、中缀式到后缀式的转化。
2、MYT算法将后缀式转化为NFA。
解决了这两个问题,代码就能顺利写出了。
附录
ReExToNFA.cpp
ReExToNFA.cpp2
参考资料
[1] 中缀表达式转换为后缀表达式
[2] 《编译器设计原理》,西安电子科技大学出版社,谌志群,王荣波,黄孝喜
[3] 基于MYT算法和自顶向下算法从正则表达式到NFA
更多推荐
编译原理实验——正则表达式转化为NFA
发布评论