来自Washington University at St.Louis, Becchi
很专业和全面的一整套程序。
2021-05-19 15:44:10
187KB
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