THOMPSON 算法的实现.doc

实验二:THOMPSON 算法的实现

掌握THOMPSON 算法原理和方法。
、内容及步骤
,输出一个接受L(r)的NFA;
++语言,实现该算法;

;

计算机、Windows 操作系统、Visual C++ 程序集成环境。

Thompson构造法:从正规表达式构造NFA
输入:字母表Σ上的一个正规表达式r
输出:接受L(r)的NFA N
方法:将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, 可构造复合的NFA N(s|t):
②对于正规表达式 st, 可构造复合的NFA N(st):
③对于正规表达式 s*, 构造复合的NFA N(s*):

④对于括起来的正规表达式(s), 使用N (s) 本身作为它的NFA。
在构造过程中,每次构造的新状态都要赋予不同的名字。这样,任何NFA的两个状态都具有不同的名字。即使同一符号在r中出现多次,我们也要为该符号的每个实例创建一个独立的带有自己状态的NFA。






核心代码如下:
#ifndef THOMPSON_H
#define THIMPSON_H

#include <iostream>
#include <>
#include <stack>
#include <string>

using namespace std;

#define MAX 100

//节点,定义成结构体,便于以后扩展
struct state
{
string StateName;
};
//边空转换符永'#'表示
struct edge
{
state StartState;
state EndState;
char TransSymbol;
};

//单元
struct cell
{
edge EdgeSet[MAX];
int EdgeCount;
state StartState;
state EndState;
};

//全局变量声明
//int EDGE_NUM = 0;
int STATE_NUM = 0;
//int CELL_NUM = 0;
//函数声明
void input(string&);
int check_legal(string);
int check_character(string);
int check_parenthesis(string);
int is_letter(char);
string add_join_symbol(string);
//中缀转后缀
string postfix(string);
//优先级 in stack priority
int isp(char);
//优先级 ing priority
int scp(char);
//表达式转NFA
cell express_2_NFA(string);
//处理 a|b
cell do_Unite(cell,cell);
//处理 ab
cell do_Join(cell,cell);
//处理 a*
cell do_Star(cell);
//处理 a
cell do_Cell(char);
//将一个单元的边的集合复制到另一个单元
void cell_EdgeSet_Copy(cell&,cell);

//产生一个新的状态节点,便于管理
state new_StateNode();
//显示
void Display(cell);
#endif
#include ""
//主函数,
void main()
{
string Regular_Ex