(1)正规文法转正规式:本程序的数据结构是string类的字符串存储变量,首先,读入的是3型文法,即正规文法,关于文法的检验这里就不再进行(因为第一个实验里已经实现了),读入的还有一个flag,flag为0即为左线性,为1为右线性,对读入的文法先进行第一次归类,即正规式左部相同的放在一起,本程序使用vector容器实现的对象放置,然后对所有的没有外部依赖的元素进行整合,最后依据没有外部依赖的整合后的表达式对其他的正规文法进行转换,最终得到转换结果。
(2)正规式NFA本程序有很多数据结构,但最终的目的数据结构是存储转化好的NFA图的单元cell,里面包含起点、终点、边数以及边集合。
先读入正规式,并对正规式进行合法检测,将正规式中填入连接符号“+”,然后将其转化成后缀表达式,根据后缀表达式,对每一个操作符和操作数进行处理,处理的数据结构为cell类型的堆栈,处理完后,将最终栈内唯一的目的cell元素出栈,最后将其用二维数组的方式展现出来。
输入文件样例:a($|((a|d)(a|d)*))
1