编译原理Thompson实验报告.doc

实 验 二 THOMPSON 算法的实现实验日期: 2011 年 10 月 31日 评分 批阅教师签字 一、实验目的掌握THOMPSON 算法原理和方法二、实验内容1输入字母表上的正规式r，输出一个接受L（r）的NFA2采用C+语言，实现该算法3 编制测试程序4调试程序三、实验环境计算机、Windows 操作系统、Visual C+ 程序集成环境。四、实验原理（或程序框图）及步骤THOMPSON 算法是语法制导的，也就是说它沿着正则表达式的语法分析树自底向上的递归的地进行处理。对于每个子表达式，该算法构造一个只有一个接受状态的NFA。输入：字母表上的一个正则表达式。输出：一个接受L(r)的NFA N。方法：首先对r进行语法分析，分解出组成它的子表达式。构造一个NFA的规则分为基本规则和归纳规则两组。基本规则处理不包含运算符的子表达式，而归纳规则根据一个给定表达式的直接子表达式的NFA构造出这个表达式的NFA。五、程序源代码核心代码如下：class nfapublic:nfa();nfa(const nfa &);static void delete_arc_node(PArc_node &);static void delete_all_vnode(PV_node &);static bool and_append(my_expression, my_expression &);static void add_count(PV_node &, int);static void delete_vnode(PV_node &);static bool infix_to_postfix(my_expression, my_expression &);bool expression_to_nfa(my_expression);bool reg_to_nfa(my_expression);void print_nfa();private:PV_node nfa_data;void operator=(const nfa &);bool nfa: expression_to_nfa(my_expression inreg)PV_node test_V_node,test_V_node1;PV_node test_PV_node,test_PV_node1;PArc_node test_PArc_node;int count;char temp_char;V_stack test_stack;while (!inreg.empty()inreg.retrieve(temp_char);if (temp_char = .)test_stack.top(test_V_node1);test_stack.pop();test_stack.top(test_V_node);test_PV_node = test_V_node;while (test_PV_node-nextv != NULL)test_PV_node = test_PV_node-nextv;count = test_PV_node-data;add_count(test_V_node1,count);test_PV_node-firstarc = test_V_node1-firstarc;test_PV_node-nextv = test_V_node1-nextv;delete test_V_node1;test_stack.pop();test_stack.push(test_V_node);else if (temp_char = |)test_stack.top(test_V_node1);test_stack.pop();test_stack.top(test_V_node);test_PV_node = test_V_node;while (test_PV_node-nextv != NULL)test_PV_node = test_PV_node-nextv;count = test_PV_node-data + 2;add_count(test_V_node,1);add_count(test_V_node1,count);test_PV_node-nextv = test_V_node1;test_PV_node1 = test_V_node1;while (test_PV_node1-nextv != NULL)test_PV_node1 = test_PV_node1-nextv;count = test_PV_node1-data + 1;test_PV_node1-nextv = test_V_node;test_V_node = test_PV_node1;test_V_node-firstarc = new ArcNode;test_V_node-firstarc-adjvex = #;test_V_node-firstarc-info = 1;test_V_node-firstarc-nextarc = new ArcNode;test_PArc_node = test_V_node-firstarc-nextarc;test_PArc_node-adjvex = #;test_PArc_node-info = test_V_node1-data;test_PArc_node-nextarc = NULL;test_stack.pop();test_stack.push(test_V_node);else if (temp_char = *)test_stack.top(test_V_node);test_PV_node = test_V_node;while (test_PV_node-nextv != NULL)test_PV_node = test_PV_node-nextv;test_PV_node-firstarc = new ArcNode;test_PV_node-firstarc-adjvex = #;test_PV_node-firstarc-info = 0;test_PV_node-firstarc-nextarc = NULL;test_PArc_node = test_PV_node-firstarc;count = test_PV_node-data + 1;test_PV_node-nextv = new VNode;test_PV_node-nextv-data = count;test_PV_node-nextv-firstarc = NULL;test_PV_node-nextv-nextv = NULL;test_PArc_node-nextarc = new ArcNode;test_PArc_node-nextarc-adjvex = #;test_PArc_node-nextarc-info = count;test_PArc_node-nextarc-nextarc = NULL;add_count(test_V_node,1);test_PV_node = new VNode;test_PV_node-nextv = test_V_node;test_V_node = test_PV_node;test_PV_node-data = 0;test_PV_node-firstarc = new ArcNode;test_PV_node-firstarc-adjvex = #;test_PV_node-firstarc-info = 1;test_PArc_node = test_PV_node-firstarc;test_PArc_node-nextarc = new ArcNode;test_PArc_node-nextarc-adjvex = #;test_PArc_node-nextarc-info = count + 1;test_PArc_node-nextarc-nextarc = NULL;test_stack.pop();test_stack.push(test_V_node);else test_V_node = new VNode;test_V_node-data=0;test_V_node-firstarc = new ArcNode;test_V_node-firstarc-adjvex = temp_char;test_V_node-firstarc-info = 1;test_V_node-firstarc-nextarc = NULL;test_V_node-nextv = new VNode;test_V_node-nextv-data = 1;test_V_node-nextv-firstarc = NULL;test_V_node-nextv-nextv = NULL;test_stack.push(test_V_node);inreg.serve();return true;六、实验数据、结果分析本次实验以课本3.6节课后练习3.6