编译原理词法分析实验报告

PAGE3编译原理实验报告学号姓名实验名称词法分析程序的设计——NFA转换为DFA实验目的理解并掌握NFA转换为DFA的实现过程实验方案实验过程：输入NFA状态表以及转换状态（L,D），将每一个状态转换表以链表的形式的链接起来，以栈的形式存储；输入初始状态，求取该状态的ε闭包，以及在状态转换下的DFA集合，当求得DFA后，以该DFA为新的NFA集合，求新的ε闭包，直到到达最后状态或进入重复循环，则求另一个状态转换下的DFA集合；输出NFA在转换状态的DFA集合；实验记录求取ε闭包：Node*Closure(Node*closure,intstate,Node*List){//closure表示存储闭包的链表，state是闭包的最初元素，List是查找的链表 Node*Tip=(Node*)malloc(sizeof(Node)); Node*newNode=(Node*)malloc(sizeof(Node)); Tip=List; while(Tip!=NULL){ if(state==Tip->Start&&Tip->Sign=="*"){ newNode->Start=Tip->End; newNode->next=closure->next; closure->next=newNode; closure=Closure(closure,Tip->End,List); } Tip=Tip->next; } returnclosure;}NFA转换DFA的实现过程：Node*NFAtoDFA(Node*NFA,Node*List,stringchange){//NFA表示最初状态集合，List表示查找的链表，change表示转换条件 Node*flag=(Node*)malloc(sizeof(Node)); Node*DFA=(Node*)malloc(sizeof(Node)); Node*newNode1=(Node*)malloc(sizeof(Node)); Node*newNode2=(Node*)malloc(sizeof(Node)); newNode2=NFA; DFA->next=NULL; while(newNode2!=NULL){ flag=List; while(flag!=NULL){ if(newNode2->Start==List->Start&&List->Sign==change){ newNode1->Start=List->End; newNode1->next=DFA->next; DFA->next=newNode1; DFA=Closure(DFA,List->End,List); } flag=flag->next; } newNode2=newNode2->next; } returnDFA;}问题解决代码：voidsolve(Node*NFA,Node*List,stringtransition[],intnumber2){ Node*DFA=(Node*)malloc(sizeof(Node)); Node*newNode1=(Node*)malloc(sizeof(Node)); Node*newNode2=(Node*)malloc(sizeof(Node)); int*array1=newint[VOLUME]; int*array2=newint[VOLUME]; intlength1,length2; boolflag; for(inti=0;i<number2;i++){ DFA=NFAtoDFA(NFA,List,transition[i]); length1=length(NFA,array1); length2=length(DFA,array2); if(length1==length2){ while(length1>0){ if(array1[length1]==array2[length1]){length1--;flag=1;continue;} else{flag=0;break;} } } elseflag=0; newNode1=NFA; newNode2=DFA; cout<<"NFA:"; while(newNode1!=NULL){ cout<<newNode1->Start<<""; newNode1=newNode1->next; } cout<<"transfer:"<<transition[i]<<""; cout<<"DFA:"; while(newNode2!=NULL){ cout<<newNode2->Start<<""; newNode2=newNode2->next; } cout<<"\n"; if(flag==0)solve(DFA,List,transition,number2); }}输入输出结果：实验总结通过本次实验，了解和熟悉了NFA转换DFA的过程，在实验开始之前，需要对转换