admin管理员组文章数量:1794759
C++实现正则表达式转最小化DFA过程详解
目前学校正在开编译原理这门课。为了加深对正则表达式转最小化DFA的理解，利用c++编写了这个程序。现在把我的程序及实现的方法分享出来，希望能对大家的学习有所帮助。
完整代码：github/GgBondXiang/RexToMinDFA
本文主要从以下几个方面进行讲解，建议搭配代码一起看- 正则表达式
- 操作数
- 运算符
- 算法流程
- 1.正则表达式的预处理
- 2.中缀表达式转后缀表达式
- 3.后缀表达式创建NFA
- 4.NFA转化为DFA
- 5.DFA的最小化
本程序的支持的操作数为小写字母‘a’~‘z’。
运算符正则表达式包含三个运算符
1）或运算符“|”
2）连接运算符“.”，一般省略不写，本程序中用“&”代替
3）闭包运算符“*”，即任意有限次的自重复连接
规定算符的优先顺序为先“*”，再“.”，最后“|”。
算法流程 1.正则表达式的预处理预处理是把表达式中省略的连接运算符加上，方便计算机运算
需要添加“&”的有六种情况，分别为“a a” 、“a （” 、“* a” 、“* （” 、“） a” 、 “） （” 总结起来为当第一位是操作数、“*”、“）”且第二位为操作数或“（”
以表达式"(a|b)* abb"为例，预处理后的表达式为：“(a|b)* &a&b&b”
2.中缀表达式转后缀表达式运算符的优先级为 闭包‘*’ > 连接‘&’ > 或‘|’
转换过程中需要用到一个运算符栈，具体过程如下:
- 如果遇到操作数，直接将其输出。
- 如果遇到运算符：
- 遇到‘（’直接压入栈中；
- 遇到‘）’将运算符出栈并输出，直到遇到‘（’，将‘（’出栈但不输出；
- 遇到‘*’、‘&’、‘|’运算符：
- 如果栈为空，直接将运算符压入栈中；
- 如果栈不为空，弹出栈中优先级大于等于当前运算符的运算符并输出，再将当前运算符入栈。
- 当输入串读取完之后，如果栈不为空，则将栈中元素依次出栈并输出。
下面看这个例子“(a|b)* &a&b&b”
1.遇到“（”，直接入栈所以转换完的后缀表达式为“ab|* a&b&b&”
3.后缀表达式创建NFA首先介绍一下NFA的存储结构，下图为一个NfaState
struct NfaState /*定义NFA状态*/ { int index; /*NFA状态的状态号*/ char input; /*NFA状态弧上的值，默认为“#”*/ int chTrans; /*NFA状态弧转移到的状态号，默认为-1*/ IntSet epTrans; /*当前状态通过ε转移到的状态号集合*/ }; struct NFA { NfaState *head; /*NFA的头指针*/ NfaState *tail; /*NFA的尾指针*/ };程序中定义了一个NfaState类型的数组NfaStates和一个int类型的全局变量nfaStateNum，初值为0，每次需要创建一个NFA时就通过NfaStates[nfaStateNum]和NfaStates[nfaStateNum + 1]从数组中取出两个状态，nfaStateNum加2，再更新NFA的头尾指针即可。
转换过程中要用到一个NFA栈，具体流程如下：
- 按顺序读取后缀表达式，每次读取一个字符
-
如果遇到操作数a，则新建一个NFA，转换弧上的值为a，将这个NFA压入栈中
-
如果遇到闭包运算符“*”，则新建一个NFA n，从NFA栈中弹出一个元素 n1，连接关系如下，将NFA n压入栈中
-
如果遇到或运算符“|”，则新建一个NFA n，并在NFA栈中弹出两个元素n1，n2，连接关系如下，将NFA n压入栈中
-
如果遇到连接运算符“&”，不用新建NFA，只需在NFA栈中弹出两个元素n1，n2，改变n1 n2的头尾指针，连接关系如下，最后将n压入栈中
-
DFA存储结构如下，下图为一个DfaState
struct DfaState /*定义DFA状态*/ { bool isEnd; /*是否为终态，是为true，不是为false*/ int index; /*DFA状态的状态号*/ IntSet closure; /*NFA的ε-move()闭包*/ int edgeNum; /*DFA状态上的射出弧数*/ Edge Edges[10]; /*DFA状态上的射出弧*/ }; struct DFA /*定义DFA结构*/ { int startState; /*DFA的初态*/ set<int> endStates; /*DFA的终态集*/ set<char> terminator; /*DFA的终结符集*/ int trans[MAX][26]; /*DFA的转移矩阵*/ };算法过程如下：
set s; //用于判断集合是否出现过。如果没有出现，则需新建一个DFA状态 queue q; dfa状态总数 = 0; //dfa状态总数 T0 = ε-closure(0); //计算ε-closure(0)，令T0 = ε-closure(0) s.insert(T0); //将子集T0加入子集族s中 q.push(T0); //将子集T0入队列 为T0新建一个dfa状态; dfa状态总数++; //dfa状态总数加一 while(!q.empty()) { T = q.front(); //出队列 q.pop(); for ch in 终结符集 //对每个终结符进行ε-closure(move(T， ch))运算 { temp_set = ε-closure(move(T, ch)); if(!temp_set.empty()) //如果子集不为空 { if(!s.count(temp_set)） //如果子集不在s中 { 为temp_set新建一个dfa状态； s.insert(temp_set); //将子集temp_set加入子集族s中 q.push(temp_set); //将子集temp_set入队列 dfa状态总数++; } else //该状态在子集族s中，假设标号为T_temp { 为当前状态T新建一条弧; //弧上的值为当前终结符 弧上的值 = ch; //弧转移到的状态为标T_temp 弧转移到的状态 = temp; } } } }以“ab|* a&b&b&”为例：
| T0 {0 2 4 6 7 8} | {0 1 2 4 5 6 7 8 9 10} T1 | {0 2 3 4 5 6 7 8} T2 |
| T1 {0 1 2 4 5 6 7 8 9 10} | {0 1 2 4 5 6 7 8 9 10} T1 | {0 2 3 4 5 6 7 8 11 12} T3 |
| T2 {0 2 3 4 5 6 7 8} | {0 1 2 4 5 6 7 8 9 10} T1 | {0 2 3 4 5 6 7 8} T2 |
| T3 {0 2 3 4 5 6 7 8 11 12} | {0 1 2 4 5 6 7 8 9 10} T1 | {0 2 3 4 5 6 7 8 13} T4 |
| T4 {0 2 3 4 5 6 7 8 13} | {0 1 2 4 5 6 7 8 9 10} T1 | {0 2 3 4 5 6 7 8} T2 |
至此，子集族中不存在新的子集，为每个子集创建dfa状态后，dfa则构造完成。
5.DFA的最小化 struct stateSet /*划分状态集*/ { int index; /*该状态集转换到的状态集标号*/ IntSet s; /*该状态集中的dfa状态号*/ }; stateSet temp[128];定义一个缓冲区，用来存储划分集合中的元素和该集合转移到的集合号。 如果某个DFA状态没有与某个终结符对应的弧，规定此类DFA状态转移到的集合号为-1。
判断当前划分集合是否需要进行划分的依据为缓冲区中的元素个数例如当前划分集合为
| PartSet[0] | {0 2 4 6 7} |
| PartSet[1] | {1 3 5} |
假设划分集合 PartSet[0]：{0 2 4 6 7}对于终结符“a”，有这样一个缓冲区：
| temp[0] | 1 | {0 6} |
| temp[1] | -1 | {2} |
| temp[2] | 0 | {4 7} |
因为缓冲区的元素个数大于1，即PartSet[0]中的元素能转移到不同集合中，所以应对PartSet[0]进行划分。
算法过程如下：
set PartSet[128]; //用于存储所有的划分集合 //将终态和非终态划分开 for state in DfaStates //遍历DFA状态数组 { if(state.isEnd == true) //如果该DFA状态是终态 { PartSet[0].insert(state); //加入到划分集合[0]中 } else //如果不是终态 { PartSet[1].insert(state); //加入到划分集合[1]中 } } //实际实现过程中为了遍历划分集合还应判断DFA中是否包含非终态。 //如果有则第一次划分后划分集合个数为2，如果没有则为1。 bool flag = true; //上次产生新的划分则为true，反之为false while(flag) //一直循环，直到上次没有产生新的划分 { for set in PartSet //对每个划分集合set { int cutCount = 0; //划分次数 for ch in 终结符集 //遍历每个终结符 { for state in set //遍历集合set中的每个DFA状态state { //判断该DFA状态是否存在与该终结符对应的弧 bool haveEdge = false; for edge in sate.Edge //遍历DFA状态sate的每条边edge { //如果存在某条边的输入为当前终结符 if(set.state.edge.input == ch) { //找到该弧转换到的状态所属的划分集合号 setNum = findSet(set.state.edge.Trans); 将该state加入到缓冲区中能转换到setNum的状态集合中; haveEdge = true; break; } } if(!haveEdge) { 将该state加入到缓冲区中能转换到-1的状态集合中; } } } if(缓冲区中元素个数 > 1) //缓冲区中元素个数大于1则需要划分 { cutCount++; //划分次数+1 //这里是从1开始，因为要将temp[0]中的元素保留在原划分集合中 for(i = 1; i < temp的元素个数; i++) { 在原划分集合set中删除temp[i]中的元素; 为temp[i]创建新的划分集合; } } } if(cutCount > 0) //划分次数大于0说明本次产生了新的划分 { flag = true; } } for set in PartSet { 为set创建一个DfaState; }还是之前的例子： 在进行第一次划分，即将终态与非终态分开后
| PartSet[0] | {4} |
| PartSet[1] | {0 1 2 3} |
PartSet[1]对终结符“a”进行划分
| temp[0] | 1 | {0 1 2 3} |
PartSet[1]对终结符“b”进行划分
| temp[0] | 1 | {0 1 2} |
| temp[1] | 0 | {3} |
缓冲区中的个数大于1，需要进行划分。划分后的集合为：
| PartSet[0] | {4} |
| PartSet[1] | {0 1 2} |
| PartSet[2] | {3} |
PartSet[2]对终结符“b”进行划分
| temp[0] | 1 | {0 2} |
| temp[1] | 2 | {1} |
缓冲区中的个数大于1，需要进行划分。划分后的集合为：
| PartSet[0] | {4} |
| PartSet[1] | {0 2} |
| PartSet[2] | {3} |
| PartSet[3] | {1} |
对每个划分集合进行判断，发现不再需要进行新的划分， 则为每个划分集合创建一个DFA状态，DFA最小化完成。
版权声明：本文标题：C++实现正则表达式转最小化DFA过程详解 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1686533641a78800.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
![[ linux ] 文件系统和目录结构详解](/uploads/image/0737.jpg)
发表评论