文档库 最新最全的文档下载
当前位置:文档库 › 正规式构造dfa

正规式构造dfa

正规式构造dfa
正规式构造dfa

正规式构造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状态数

四.测试用例及测试结果

读入的文件:

相关文档