第 1 页 实验二：THOMPSON 算法的实现 一．实验目的 掌握THOMPSON 算法原理和方法。 二．实验要求、内容及步骤 1.输入字母表上的正规式r，输出一个接受L（r）的NFA； 2.采用C++语言，实现该算法； 3.编制测试程序 4.调试程序； 三．实验设备 计算机、Windows 操作系统、Visual C++ 程序集成环境。 四．实验原理 Thompson 构造法：从正规表达式构造NFA 输入：字母表Σ上的一个正规表达式r 输出：接受L(r)的NFA N 方法：将 r 分解成最基本的子表达式，使用下面的规则 1 和2 为 r 的每个基本符号（ ε 或Σ中的符号）构造NFA。用规则 3 逐步组合前面构造的NFA，直到获得整个正规表达式的NFA 为止。 规则 1. 对ε, 构造NFA 第 2 页 这里 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*): 第 3 页 ④对于括起来的正规表达式 (s), 使用 N (s) 本身作为它的 NFA。 在构造过程中，每次构造的新状态都要赋予不同的名字。这样，任何NFA的两个状态都具有不同的名字。即使同一符号在 r 中出现多次，我们也要为该符号的每个实例创建一个独立的带有自己状态的 NFA。 第 4 页 五.程序设计框架 第 5 页 六.程序流程图 七.实验代码 核心代码如下： #ifndef THOMPSON_H #define THIMPSON_H #inclu de #inclu de #inclu de #inclu de u sing namespace std; 第 6 页 #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(str...
