词法分析程序之正规式转换成NFA |
您所在的位置：网站首页 › 组距式分组中位数计算公式 › 词法分析程序之正规式转换成NFA |
词法分析程序之正规式转换成NFA
|
文章目录
前言正规式变成NFA前备知识中缀表达式和后缀表达式（细节处理）输入正规式和转换NFA测试结果完整代码
前言
编译原理课里面书本有一个作业——使用C++实现： 将正规式变成NFANFA确定化（变成DFA）DFA最小化（化简）自己学习过程中，深刻知道自己动手写东西是多么的重要。所以，我开始从0开始写这个作业。 每个自学的人都要明白自己和科班的人差距在哪里——基础！基础！所以一定要花时间去补回来。 正规式变成NFA 前备知识在动手之前，一定学会分析要怎么做怎么做，有哪几个类，不要上去就是一段代码——参考某大佬的话。 （1）第一步，我们需要分析程序的流程是什么——画一个简单的思维导图：
接下来我们可以使用Thompson方法实现正规式转NFA。 （2）NFA如何表示——需要什么的数据结构？ 我们知道MFA是有节点信息、带信息的边的有向图。所以我们可以设计这样的数据结构 节点 struct NodeState{ string StateName;//节点状态 };边：（有向边） struct Edge{ NodeState startNode;//开始节点状态 NodeState endNOde;//终止节点状态 char TransSymbol;//边上的转化符号_空转化符我们使用#号表示 };NFA单元——一个大的NFA可以有NFA单元组成。 struct NFACeil{ NodeState startNode;//开始节点状态 NodeState endNOde;//终止节点状态 int EdgeCount;//边数 Edge Edgeset[MAX];//该NFA拥有的边数 };（3）了解Thompson方法原理（参考编译原理书本即可） 将输入的r分解为最基本的子表达式，然后利用3条规则构造NFA。不断重复，直到输入的r的所有子表达式都得到了NFA。规则1、2和3 是NFA构建的基本单元，含有两个状态以及状态转换的边。 规则1：构造符号为“”，即空字符的NFA规则2：构造符号为a的NFA，a属于符号集的一个字符规则3：构造空集的NFA 图片来自： https://blog.csdn.net/gongsai20141004277/article/details/52949995
上面的过程用程序来实现就是传入一个符号，得到一个NFA单元——NFACell init(char element) 之后使用下面规则合并得到的NFA单元： s|t——NFACell do_aORb(NFACell a,NFACell b)st——NFACell do_aANDb(NFACell a,NFACell b)s*——NFACell do_aStar(NFACell a) 图解：  上面这些过程我们需要具体程序来实现。
中缀表达式和后缀表达式（细节处理）
我们需要把中缀表达式转后缀表达式，以便处理符号优先级和去除括号。进而简化我们的代码书写。而在这个过程中很重要的一点是把经过检查后得到的有效正规式（中缀表达式）做一个预处理： 加入+号，将省略的连接符显式加进去，表明这两个正规式的关系，如ab变成a+b，ab变成a+b,说明该正规式由a*和b组成。要加入加号的情况有4种： /* 给中缀表达式添加 +号 */ string joinAddSymbol(string regxValid){ //------------------需要添加+号的情况--------------------// // ab -》 a+b ----ab // //ab*->a+b*------ab 情况1 // // // // a(b|c)-》a+(b|c)--a( 情况2 // // (a|b)c-》(a|b)+c--)b 情况3 // // // // a*b-》 a* + b----*b 情况4 // //-----------------------------------------------------// if(regxValid.length() return_string[index++] = '+';//插入+号 }else if( isLetter(pre) && now=='('){ //情况2 a( return_string[index++] = '+';//插入+号 }else if(pre==')' && isLetter(now)){ //情况3 )b return_string[index++] = '+';//插入+号 }else if(pre=='*' && isLetter(now)){ //情况4 *b return_string[index++] = '+';//插入+号 } //上面的某些分支可以合起来写，但是为了逻辑清晰则分开写。 } //最后写入now符号 return_string[index++] = now; return_string[index++] = '\0';//添加结束符号 string newRegex(return_string);//创建为string cout cout if((e>='a' && e='A' && e int n = regex.length(); bool res = true; for(int i=0;i res = false; break; } } return res; } /* * 判断输入的正则式是否含有括号，其括号是否匹配 */ bool isMatchParenthesis(string checkregx){ stack s; int n = checkregx.length(); int i=0; while(!s.empty() && i s.push(checkregx[i]); } if(checkregx[i]==')'){ if(s.empty()){ cerr bool res1 = isMatchParenthesis(regex);//括号是否匹配 bool res2 = isCharacter(regex);//是否为合法字符 return res1 && res2; }转化NFA： /**表达式转NFA处理函数,返回最终的NFA结合 * 利用三条规则 */ NFACell regex2NFA(string expression){ int length = expression.size(); char element; NFACell Cell, Left, Right; stack STACK; for (int i = 0; i case '|'://或 Right = STACK.top(); STACK.pop(); Left = STACK.top(); STACK.pop(); Cell = do_aORb(Left, Right); // displayNFA(Cell); // cout cout |
NFA——是一个五元组：M = ( K , ∑ , f , S , Z ) ,∑有穷字母表，即是正规式的字母表，而其他的像K 状态集，f 转移函数，S 非空初态集，Z 终态集。【本文地址】
今日新闻 |
推荐新闻 |