1. 一个自动机是一个五元组，分别是
2. 使用子集法的步骤是：
1) 将起始状态求闭包，得到S0。
2) 将S0做f函数转换，得到在任意符号集元素下的状态集。
3) 对状态集求空闭包，并以空闭包为终点，记录mov函数。
4) 如果空闭包不存在，将空闭包记录。
5) 循环2至5直到新产生的空闭包不再被记录。
2019-12-21 20:50:22
201KB
1
内涵C++源码，UML类图，算法思想文档。内容主要包括：自定义正则文法（在ProgramManager类中自定义），根据正则文法和输入的正则表达式构建NFA，NFA自动构建DFA，DFA最小化，DFA匹配字符串。其中含有大量的中文注释，并提供了测试方法。本人还是学生，希望各位大神多多指点。
2019-12-21 20:25:43
17.1MB
1
（1）Lex输入文件的解析：
·主函数main()实现对Lex输入文件结构的解析
·int checkType(char c)函数判断是定义段开始？定义段结束？规则段？
（2）正规表达式的解析：
·void replaceID(string &re)函数将用户标示id转换成re
·通过对正规表达式的解析的解析可以将规则段的模式部分全部转换成正规表达式
（3）一个正规表达式到NFA的转换算法的实现
·void generateNFA(const string & re,vector
- &tnfa,vector &isTer,int index)函数完成正规表达式到NFA的转换
其中：re：正规表达式
tnfa：数据结构是vector
- ，即NFA的每个结点是list
(关于NFA的数据结构的描述见后面)
isTer：统计tnfa中接受状态结点（isTer[i]!=0表示结点i为接受态）
（3）多个NFA的合并
·void joinNFA(vector
- &nfa1,const vector
- &nfa2)
函数完成了NFA nfa1和nfa2的合并，从总体来看起到所有NFA的合并
·合并NFA的基本原理：将nfa2的开始的点中的内容全部拷贝给nfa1的开始结点然后，再把nfa2中除了开始点以外的点连接到nfa1的末尾即可，注意结点编号的变化
（4）NFA的确定化算法的实现
·void TODFA()函数完成NFA到DFA的转换
·在进行NFA确定化算法的同时，自动机的接受态集合也做相应的变换
vector nfaIsTer vector dfaIsTer
2019-12-21 20:17:29
1.93MB
1