正规式构造DFA
课程设计报告
学院(系):计算机学院
班级:计算机(3)班
学生姓名:
学号:
正规式->NFA->DFA->最小DFA
一.摘要:该实验的内容是将正规式转化为最小DFA。先从键盘输入正规式,如:(a|b)^*c#,可以
证明正规式的文法是一个算符优先文法,利用算符优先文法的分析方法将正规式转化为NFA,
然后将其转化为DFA,最后利用化简原则将其转化为最小DFA。该实验运用了栈、图等数据结构,并创建了NFA 的邻接矩阵,DFA 状态转移矩阵,最小DFA 状态转移矩阵。输出结果以矩阵形式存储在文件中。
二.功能说明
该程序可根据一个给定的正规式,生成其对应的NFA,经过确定化得到DFA,再将其最小化,
从而生成最小DFA。
三.系统结构说明
一、识别正规式
1.正规式的文法:
正规式分析采用算符优先分析法,正规式的文法为:
初态集:{S}
非终结符集合:{A,S}
终结符集合:{*,\,^,e |e 表示所有非运算符字符,*,\,^非别表示连接,或,闭包运算}
S->A|(A)
A->A*A|A\A|A^|e
可以证明这是一个算符优先文法。
由正规式构造NFA:使用Thompson构造法
输入:字母表Σ上的正则表达式
输出:能够接受L(r)的NFA N
方法:首先将构成r的各个元素分解,对于每一个元素,按下述规则1和规则2生成NFA。注意:如果r中记号a出现了多次,那么对于a的每次出现都需要生成一个单独的NFA。
之后依照正规表达式r的文法规则,将生成的NFA按照下述规则3组合在一起。
规则1对于空记号ε,生成下面的NFA。
规则2对于Σ的字母表中的元素a,生成下面的NFA。
规则3令正规表达式s和t的NFA分别为N(s)和N(t)。
a) 对于s|t,按照以下的方式生成NFA N(s|t)。
b) 对于st,按照以下的方式生成NFA N(st)。
c) 对于s*,按照以下的方式生成NFA N(s*)。
d) 对于(s),使用s本身的NFA N(s)。
正规式识别流程
符号的运算实际上是对正规式的运算。
采用栈结构,设置两个栈,正规式栈Stack_c 和操作栈Stack_o Initiate(Stack_c)//存储当前识别的NFAInitiate(Stack_o)//存储操作符Push(Stack_o,’#’)
读入正规式S
c<-s[0]
While Top(Stack_o)!=’#’
If c 是运算符Then
If c 优先级高于Top(Stack_o)的优先级Then
Push(Stack_o,c)
Else
If Top(Stack_o) 是’(‘ Then
Pop(Stack_o)
把下一个正规式中的字符给c
Else
NFA=Opertate(根据Top(Stack_o)取出Stack_c 中相应个数DFA,Pop(Stack_o))
//此函数为NFA 的构造函数
Push(stack_c,NFA)
EndIf
EndIf
EndIf
If c 是操作数Then
NFA= Convert(c)
// 是用c 字符构造一个单字符无运算的NFA
Push(Stack_c,NFA)
把下一个正规式中的字符给 c
EndIf
EndWhile
二、根据正规式构造NFA—Convert(c)与Operate(a,’c’,b)函数详解
1.使用邻接矩阵Tab[i][j]存储NFA
行列表示状态,矩阵元素表示字符。
N 表示状态个数
初始化N=0
2.NFA 的表示
Struct NFA
{
Int start//起点状态标号
Int end//终点状态标号
};
3.Convert()函数将单字符转化为正规式存入邻接矩阵
函数Convert(c,*Tab)
{
Struct NFA temp
Tab[N][N+1]=c//增加个NFA
Temp.start=N//起点
Temp.end=N+1//终点
Tab->N=Tab->N+2//状态数加2
Return temp;
}
4.Operate(NFA,运算符)函数
{
Struct NFA temp
当进行NFA_a | NFA_b 运算时
Tab[N][NFA_a.start]=空字符
Tab[N][NFA_b.start]=空字符
Tab[NFA_a.end][N+1]= 空字符
Tab[NFA_b.end][N+1]= 空字符
Temp.start=N
Temp.end=N+1
N=N+2;
当进行NFA_a*NFA_b 运算时
当进行NFA_a^运算时
Tab[NFA_a.end][NFA.start]= 空字符
Temp.start=NFA_a.start
Temp.end=NFA_b.end
当进行NFA_a^运算时
Tab[N][NFA_a.start]=空字符
Tab[N][N+1]=空字符
Tab[NFA_a.end][NFA_a.start]= 空字符
Tab[NFA_a.end][N+1]= 空字符
Temp.start=N
Temp.end=N+1
N=N+2;
}
三、NFA 的确定化
1.DFA 的表示
Struct DFANode{
Int Node[100]//
} //定义状态节点
Struct DFA{
Struct DFANode d[100]//状态节点
Int DFAMatrix[100][100]//状态转移矩阵
Int length//节点数目
}
2.NFA 确定化算法
Struct DFA DFATab
DFATab.DFANode[0]=CLOSURE(NFA 中的初态节点)
// CLOSURE(I),此函数采用深度优先便利方法,找到NFA 中所有与I 等价的状态。N=0;
DFATab.length=1;
WHILE N For a=第一个终结符to 最后一个终结符 Temp=NextState(Si,a) DFATab[Si,a]=temp IF temp 是新状态Then DFATab.Node[N]=temp DFATab.length= DFATab.length +1 EndIf EndFor N=N+1 EndWhile 数据结构 // 定义DFA的构造类 class DFA { public: DFA(); ~DFA(); void GetRegExp(); void InsertCatNode(); void RegExpToPost(); void GetEdgeNumber(); void ThompsonConstruction(); void SubsetConstruction(); void FindMatchingPatternInFile(); private: char *exp; char *post; char *edge; int edgeNumber; int **DStates; int **Dtran; int *AcceptStates; int DStatesNumber; int DtranNumber; int NFAStatesNumber; int DFAStatesNumber; AdjacentTable *NFATable; TransitionTable *DFATable; int Precedence(char symbol); int CompArray(int *t1, int *t2); int MinimizeDFAStates(int **Dtran, int *AcceptStates, int DtranNumber, int edgeNumber); void RemoveFirstSymbol(char *buf, int &len); }; // 定义邻接表的边表类 class Edge { public: int number; int position; char weight; Edge *link; Edge(); Edge(int num, int pos, char ch); }; // 定义邻接表的顶点类 class Vertex { public: int number; Vertex *next; Edge *out; Vertex(); Vertex(int num); }; Exp 输入的正规式 Post 逆波兰式 Edge 终结符 edgeNumber 终结符个数 DStates 集合 Dtran DFA对应的状态迁移表 AcceptStates 接受状态 DStatesNumber 集合数量 DtranNumber DFA最小化状态数NFAStatesNumber NFA状态数DFAStatesNumber DFA状态数 四.测试用例及测试结果 读入的文件: