目前学校正在开编译原理这门课。为了加深对正则表达式转最小化DFA的理解,利用c++编写了这个程序。现在把我的程序及实现的方法分享出来,希望能对大家的学习有所帮助。
完整代码:https://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.中缀表达式转后缀表达式
运算符的优先级为 闭包‘*’ > 连接‘&’ > 或‘|’
转换过程中需要用到一个运算符栈,具体过程如下:
- 如果遇到操作数,直接将其输出。
- 如果遇到运算符:
- 遇到‘(’直接压入栈中;
- 遇到‘)’将运算符出栈并输出,直到遇到‘(’,将‘(’出栈但不输出;
- 遇到‘*’、‘&’、‘|’运算符:
- 如果栈为空,直接将运算符压入栈中;
- 如果栈不为空,弹出栈中优先级大于等于当前运算符的运算符并输出,再将当前运算符入栈。
- 当输入串读取完之后,如果栈不为空,则将栈中元素依次出栈并输出。
/*
*本程序中比较优先级的方法是为每一个运算符返回一个权值,通过权值的大小来比较优先级。
*但是实际操作中会遇到bug,这是因为程序无法返回左括号的优先级。
*为了保证弹出优先级大于等于当前运算符的运算符时,左括号不会出栈,将左括号的权值设为0
*/
int priority(char ch)
{
if(ch == '*')
{
return 3;
}
if(ch == '&')
{
return 2;
}
if(ch == '|')
{
return 1;
}
if(ch == '(')
{
return 0;
}
}
下面看这个例子“(a|b)* &a&b&b”
-
1.遇到“(”,直接入栈
- 栈:(
- 输出区: 2.遇到“a”,直接输出
- 栈:(
- 输出区:a 3.遇到“|”,栈中没有优先级大于等于它的运算符,直接压入栈中
- 栈:( |
- 输出区:a 4.遇到“b”,直接输出
- 栈:( |
- 输出区:a b 5.遇到“)”,“|”出栈并输出,左括号出栈
- 栈:
- 输出区:a b | 6.遇到“*”,栈为空,直接入栈
- 栈:*
- 输出区:a b | 7.遇到“&”,“*”出栈并输出,再将“&”入栈
- 栈:&
- 输出区:a b | * 8.遇到“a”,直接输出
- 栈:&
- 输出区:a b | * a 9.遇到“&”,“&”出栈并输出,再将“&”入栈
- 栈:&
- 输出区:a b | * a & 10.遇到“b”,直接输出
- 栈:&
- 输出区:a b | * a & b 11.遇到“&”,“&”出栈并输出,再将“&”入栈
- 栈:&
- 输出区:a b | * a & b & 12.遇到“b”,直接输出
- 栈:&
- 输出区:a b | * a & b & b 13.字符串读完,栈不为空,将栈中元素出栈并输出
- 栈:
- 输出区:a b | * a & b & b &
所以转换完的后缀表达式为“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压入栈中
-
-
后缀表达式“ab|* a&b&b&”具体转换过程如下
-
- 遇到“a”,新建一个NFA n,压入栈中
- 遇到“a”,新建一个NFA n,压入栈中
-
- 遇到“b”,新建一个NFA n,压入栈中
- 遇到“b”,新建一个NFA n,压入栈中
-
- 遇到“|”,新建一个NFA n,从栈中弹出两个NFA,改变连接关系,再将n压入栈中
- 遇到“|”,新建一个NFA n,从栈中弹出两个NFA,改变连接关系,再将n压入栈中
-
- 遇到“*”,新建一个NFA n,从栈中弹出一个NFA,改变连接关系,再将n压入栈中
- 遇到“*”,新建一个NFA n,从栈中弹出一个NFA,改变连接关系,再将n压入栈中
-
- 遇到“a”,新建一个NFA n,压入栈中
- 遇到“a”,新建一个NFA n,压入栈中
-
- 遇到“&”, 新建一个NFA n,从栈中弹出两个NFA,改变连接关系,再将n压入栈中
- 遇到“&”, 新建一个NFA n,从栈中弹出两个NFA,改变连接关系,再将n压入栈中
-
7.遇到“b”,新建一个NFA n,压入栈中
-
8.遇到“&”, 新建一个NFA n,从栈中弹出两个NFA,改变连接关系,再将n压入栈中
-
9.遇到“b”,新建一个NFA n,压入栈中
-
10.遇到“&”, 新建一个NFA n,从栈中弹出两个NFA,改变连接关系,再将n压入栈中
后缀表达式读取结束,最后NFA栈中的唯一元素即为创建好的NFA
4.NFA转化为DFA
struct Edge /*定义DFA的转换弧*/
{
char input; /*弧上的值*/
int Trans; /*弧所指向的状态号*/
};
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&”为例:
子集 | a | 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。
-
判断当前划分集合是否需要进行划分的依据为缓冲区中的元素个数
- 如果个数为1,表示当前划分集合中的所有元素都转移到同一个集合中,则不需要划分
- 反之,如果个数大于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} |
-
该缓冲区表示
- temp[0]:DFA状态0、6都能转移到划分集合 PartSet[1]中
- temp[1]:DFA状态2没有与“a”对应的转换弧
- temp[2]:DFA状态4、7都能转移到划分集合 PartSet[0]中
因为缓冲区的元素个数大于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过程详解
发布评论