编译原理Thompson实验报告

《编译原理Thompson实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验二THOMPSON算法的实现实验日期:2011年10月31日评分批阅教师签字一、实验目的掌握THOMPSON算法原理和方法二、实验内容1  输入字母表上的正规式r，输出一个接受L（r）的NFA2  采用C++语言，实现该算法3编制测试程序4  调试程序三、实验环境计算机、Windows操作系统、VisualC++程序集成环境。四、实验原理（或程序框图）及步骤THOMPSON算法是语法制导的，也就是说它沿着正则表达式的语法分析树自底向上的递归的地进行处理。对于每个子表达式，该算法构造一个只有一个接受状态的NFA。输入：

2、字母表上的一个正则表达式。输出：一个接受L(r)的NFAN。方法：首先对r进行语法分析，分解出组成它的子表达式。构造一个NFA的规则分为基本规则和归纳规则两组。基本规则处理不包含运算符的子表达式，而归纳规则根据一个给定表达式的直接子表达式的NFA构造出这个表达式的NFA。五、程序源代码核心代码如下：classnfa{public:nfa();第6页nfa(constnfa&);staticvoiddelete_arc_node(PArc_node&);staticvoiddelete_all_vnode(PV_node&

3、);staticbooland_append(my_expression,my_expression&);staticvoidadd_count(PV_node&,int);staticvoiddelete_vnode(PV_node&);staticboolinfix_to_postfix(my_expression,my_expression&);boolexpression_to_nfa(my_expression);boolreg_to_nfa(my_expression);voidprint_nfa();pri

4、vate:PV_nodenfa_data;voidoperator=(constnfa&);};boolnfa::expression_to_nfa(my_expressioninreg){PV_nodetest_V_node,test_V_node1;PV_nodetest_PV_node,test_PV_node1;PArc_nodetest_PArc_node;intcount;chartemp_char;V_stacktest_stack;while(!inreg.empty()){inreg.retrieve(

5、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;第6页add_count(test_V_node1,count);test_PV_n

6、ode->firstarc=test_V_node1->firstarc;test_PV_node->nextv=test_V_node1->nextv;deletetest_V_node1;test_stack.pop();test_stack.push(test_V_node);}elseif(temp_char=='

7、'){test_stack.top(test_V_node1);test_stack.pop();test_stack.top(test_V_node);test_PV_node=test_V_nod

8、e;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

9、_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=newArcNode;test_V_node->firstarc