THOMPSON算法地实现.docx
《THOMPSON算法地实现.docx》由会员分享，可在线阅读，更多相关《THOMPSON算法地实现.docx（25页珍藏版）》请在冰点文库上搜索。
THOMPSON算法地实现
实验二：
THOMPSON算法的实现
一．实验目的
掌握THOMPSON算法原理和方法。
二．实验要求、内容及步骤
1.输入字母表上的正规式r，输出一个接受L（r）的NFA；
2.采用C++语言，实现该算法；
3.编制测试程序
4.调试程序；
三．实验设备
计算机、Windows操作系统、VisualC++程序集成环境。
四．实验原理
Thompson构造法：
从正规表达式构造NFA
输入：
字母表Σ上的一个正规表达式r
输出：
接受L（r）的NFAN
方法：
将r分解成最基本的子表达式，使用下面的规则1和2为r的每个基本符号（ε或Σ中的符号）构造NFA。
用规则3逐步组合前面构造的NFA，直到获得整个正规表达式的NFA为止。
规则1.对ε,构造NFA
这里i是新的开始状态，f是新的接受状态。
很明显这个NFA识别{ε}。
规则2.对于Σ中的每个符号a，构造NFA
同样，i是新的开始状态，f是新的接受状态。
这个NFA识别{a}。
规则3.如果N（s）和N（t）是正规表达式s和t的NFA，则：
①对于正规表达式s|t,可构造复合的NFAN（s|t）:
②对于正规表达式st,可构造复合的NFAN（st）：
③对于正规表达式s*,构造复合的NFAN（s*）:
④对于括起来的正规表达式（s）,使用N（s）本身作为它的NFA。
在构造过程中，每次构造的新状态都要赋予不同的名字。
这样，任何NFA的两个状态都具有不同的名字。
即使同一符号在r中出现多次，我们也要为该符号的每个实例创建一个独立的带有自己状态的NFA。
五.程序设计框架
六.程序流程图
七.实验代码
核心代码如下：
#ifndefTHOMPSON_H
#defineTHIMPSON_H
#include
#include
#include
#include
usingnamespacestd;
#defineMAX100
//节点，定义成结构体，便于以后扩展
structstate
{
stringStateName;
};
//边空转换符永'#'表示
structedge
{
stateStartState;
stateEndState;
charTransSymbol;
};
//单元
structcell
{
edgeEdgeSet[MAX];
intEdgeCount;
stateStartState;
stateEndState;
};
//全局变量声明
//intEDGE_NUM=0;
intSTATE_NUM=0;
//intCELL_NUM=0;
//函数声明
voidinput（string&）;
intcheck_legal（string）;
intcheck_character（string）;
intcheck_parenthesis（string）;
intis_letter（char）;
stringadd_join_symbol（string）;
//中缀转后缀
stringpostfix（string）;
//优先级instackpriority
intisp（char）;
//优先级incomingpriority
intscp（char）;
//表达式转NFA
cellexpress_2_NFA（string）;
//处理a|b
celldo_Unite（cell,cell）;
//处理ab
celldo_Join（cell,cell）;
//处理a*
celldo_Star（cell）;
//处理a
celldo_Cell（char）;
//将一个单元的边的集合复制到另一个单元
voidcell_EdgeSet_Copy（cell&,cell）;
//产生一个新的状态节点，便于管理
statenew_StateNode（）;
//显示
voidDisplay（cell）;
#endif
#include"Thompson.h"
//主函数，
voidmain（）
{
stringRegular_Expression="（a|b）*abb";
cellNFA_Cell;
Regular_Expression="（a|b）*abb";
//接受输入
input（Regular_Expression）;//调试需要先屏蔽
//添加“+”，便于转后缀表达式
Regular_Expression=add_join_symbol（Regular_Expression）;
//中缀转后缀
Regular_Expression=postfix（Regular_Expression）;
//表达式转NFA
NFA_Cell=express_2_NFA（Regular_Expression）;
//显示
Display（NFA_Cell）;
}
/**表达式转NFA处理函数,返回最终的NFA结合
*/
cellexpress_2_NFA（stringexpression）
{
intlength=expression.size（）;
charelement;
cellCell,Left,Right;
stack| STACK; |
for（inti=0;i{
element=expression.at（i）;
switch（element）
{
case'|':
Right=STACK.top（）;
STACK.pop（）;
Left=STACK.top（）;
STACK.pop（）;
Cell=do_Unite（Left,Right）;
STACK.push（Cell）;
break;
case'*':
Left=STACK.top（）;
STACK.pop（）;
Cell=do_Star（Left）;
STACK.push（Cell）;
break;
case'+':
Right=STACK.top（）;
STACK.pop（）;
Left=STACK.top（）;
STACK.pop（）;
Cell=do_Join（Left,Right）;
STACK.push（Cell）;
break;
default:
Cell=do_Cell（element）;
STACK.push（Cell）;
}
}
cout<<"处理完毕!
"<Cell=STACK.top（）;
STACK.pop（）;
returnCell;
}
//处理a|b
celldo_Unite（cellLeft,cellRight）
{
cellNewCell;
NewCell.EdgeCount=0;
edgeEdge1,Edge2,Edge3,Edge4;
//获得新的新状态节点
stateStartState=new_StateNode（）;
stateEndState=new_StateNode（）;
//构建边
Edge1.StartState=StartState;
Edge1.EndState=Left.EdgeSet[0].StartState;
Edge1.TransSymbol='#';
Edge2.StartState=StartState;
Edge2.EndState=Right.EdgeSet[0].StartState;
Edge2.TransSymbol='#';
Edge3.StartState=Left.EdgeSet[Left.EdgeCount-1].EndState;
Edge3.EndState=EndState;
Edge3.TransSymbol='#';
Edge4.StartState=Right.EdgeSet[Right.EdgeCount-1].EndState;
Edge4.EndState=EndState;
Edge4.TransSymbol='#';
//构建单元
//先将Left和Right的EdgeSet复制到NewCell
cell_EdgeSet_Copy（NewCell,Left）;
cell_EdgeSet_Copy（NewCell,Right）;
//将新构建的四条边加入EdgeSet
NewCell.EdgeSet[NewCell.EdgeCount++]=Edge1;
NewCell.EdgeSet[NewCell.EdgeCount++]=Edge2;
NewCell.EdgeSet[NewCell.EdgeCount++]=Edge3;
NewCell.EdgeSet[NewCell.EdgeCount++]=Edge4;
//构建NewCell的启示状态和结束状态
NewCell.StartState=StartState;
NewCell.EndState=EndState;
returnNewCell;
}
//处理ab
celldo_Join（cellLeft,cellRight）
{
//将Left的结束状态和Right的开始状态合并，将Right的边复制给Left，将Left返回
//将Right中所有以StartState开头的边全部修改，
for（inti=0;i{
if（Right.EdgeSet[i].StartState.StateNpare（Right.StartState.StateName）==0）
{
Right.EdgeSet[i].StartState=Left.EndState;
STATE_NUM--;
}
elseif（Right.EdgeSet[i].EndState.StateNpare（Right.StartState.StateName）==0）
{
Right.EdgeSet[i].EndState=Left.EndState;
STATE_NUM--;
}
}
Right.StartState=Left.EndState;
cell_EdgeSet_Copy（Left,Right）;
//将Left的结束状态更新为Right的结束状态
Left.EndState=Right.EndState;
returnLeft;
}
//处理a*
celldo_Star（cellCell）
{
cellNewCell;
NewCell.EdgeCount=0;
edgeEdge1,Edge2,Edge3,Edge4;
//获得新的新状态节点
stateStartState=new_StateNode（）;
stateEndState=new_StateNode（）;
//构建边
Edge1.StartState=StartState;
Edge1.EndState=EndState;
Edge1.TransSymbol='#';
Edge2.StartState=Cell.EndState;
Edge2.EndState=Cell.StartState;
Edge2.TransSymbol='#';
Edge3.StartState=StartState;
Edge3.EndState=Cell.StartState;
Edge3.TransSymbol='#';
Edge4.StartState=Cell.EndState;
Edge4.EndState=EndState;
Edge4.TransSymbol='#';
//构建单元
//先将Cell的EdgeSet复制到NewCell
cell_EdgeSet_Copy（NewCell,Cell）;
//将新构建的四条边加入EdgeSet
NewCell.EdgeSet[NewCell.EdgeCount++]=Edge1;
NewCell.EdgeSet[NewCell.EdgeCount++]=Edge2;
NewCell.EdgeSet[NewCell.EdgeCount++]=Edge3;
NewCell.EdgeSet[NewCell.EdgeCount++]=Edge4;
//构建NewCell的启示状态和结束状态
NewCell.StartState=StartState;
NewCell.EndState=EndState;
returnNewCell;
}
//处理a
celldo_Cell（charelement）
{
cellNewCell;
NewCell.EdgeCount=0;
edgeNewEdge;
//获得新的新状态节点
stateStartState=new_StateNode（）;
stateEndState=new_StateNode（）;
//构建边
NewEdge.StartState=StartState;
NewEdge.EndState=EndState;
NewEdge.TransSymbol=element;
//构建单元
NewCell.EdgeSet[NewCell.EdgeCount++]=NewEdge;
NewCell.StartState=NewCell.EdgeSet[0].StartState;
NewCell.EndState=NewCell.EdgeSet[0].EndState;//EdgeCount此时为1
returnNewCell;
}
voidcell_EdgeSet_Copy（cell&Destination,cellSource）
{
intD_count=Destination.EdgeCount;
intS_count=Source.EdgeCount;
for（inti=0;i{
Destination.EdgeSet[D_count+i]=Source.EdgeSet[i];
}
Destination.EdgeCount=D_count+S_count;
}
/*
获得新的状态节点，统一产生，便于管理，不能产生重复的状态
并添加到state_set[]数组中
*/
statenew_StateNode（）
{
statenewState;
newState.StateName=STATE_NUM+65;//转换成大写字母
STATE_NUM++;
returnnewState;
}
//接收输入正规表达式，RegularExpression作为回传函数
voidinput（string&RegularExpression）
{
cout<<"请输入正则表达式：
（操作符：
（）*|;字符集：
a~zA~Z）"<do
{
cin>>RegularExpression;
}while（!
check_legal（RegularExpression））;
//cout<}
/**检测输入的正则表达式是否合法
*/
intcheck_legal（stringcheck_string）
{
if（check_character（check_string）&&check_parenthesis（check_string））
{
returntrue;
}
returnfalse;
}
/**
检查输入的字符是否合适（）*|a~zA~Z
合法返回true,非法返回false
*/
intcheck_character（stringcheck_string）
{
intlength=check_string.size（）;
for（inti=0;i{
charcheck=check_string.at（i）;
if（is_letter（check））//小写和大写之间有5个字符，故不能连续判断
{
//cout<<"字母合法";
}
elseif（check=='（'||check=='）'||check=='*'||check=='|'）
{
//cout<<"操作符合法";
}
else
{
cout<<"含有不合法的字符!
"<cout<<"请重新输入:
"<returnfalse;
}
}
returntrue;
}
/**先检查括号是否匹配
*合法返回true,非法返回false
*/
intcheck_parenthesis（stringcheck_string）
{
intlength=check_string.size（）;
char*check=newchar[length];
strcpy（check,check_string.c_str（））;
//chara=check_string.at
（1）;
stackSTACK;
for（inti=0;i{
if（check[i]=='（'）
STACK.push（i）;
elseif（check[i]=='）'）
{
if（STACK.empty（））
{
cerr<<"有多余的右括号"<cout<<"请重新输入:
"<returnfalse;
}
else
STACK.pop（）;
}
}
if（!
STACK.empty（））
{
//暂时不记录匹配位置location
cerr<<"有多余的左括号"<cout<<"请重新输入:
"<returnfalse;
}
//cout<returntrue;
}
/**检测是否是字母
是返回true,否则false
*/
intis_letter（charcheck）
{
if（check>='a'&&check<='z'||check>='A'&&check<='Z'）
returntrue;
returnfalse;
}
/**添加交操作符“+”，便于中缀转后缀表达式
例如abb->a+b+b
*/
stringadd_join_symbol（stringadd_string）
{
/*测试终止符\0
stringcheck_string="abcdefg\0aaa";
cout<intlength=check_string.size（）;
char*check=newchar[2*length];
strcpy（check,check_string.c_str（））;
cout<char*s="ssss\0aa";
cout<stringa（s）;
cout<*/
intlength=add_string.size（）;
intreturn_string_length=0;
char*return_string=newchar[2*length];//做多是两倍
charfirst,second;
for（inti=0;i{
first=add_string.at（i）;
second=add_string.at（i+1）;
return_string[return_string_length++]=first;
//若第二个是字母、第一个不是'（'、'|'都要添加
if（first!
='（'&&first!
='|'&&is_letter（second））
{
return_string[return_string_length++]='+';
}
//若第二个是'（',第一个不是'|'、'（',也要加
elseif（second=='（'&&first!
='|'&&first!
='（'）
{
return_string[return_string_length++]='+';
}
}
//将最后一个字符写入
return_string[return_string_length++]=second;
return_string[return_string_length]='\0';
stringSTRING（return_string）;
cout<<"加'+'后的表达式：
"<returnSTRING;
}
/*
优先级表：
#（*|+）
isp017538
icp086421
*/
//instackpriority栈内优先级
intisp（charc）
{
switch（c）
{
case'#':
return0;
case'（':
return1;
case'*':
return7;
case'|':
return5;
case'+':
return3;
case'）':
return8;
}
//若走到这一步，说明出错了
cerr<<"ERROR!
"<
升级会员 