学 号 | 不要为我难过姓 名 | ||
实验名称扎克天赋 | 词法分析程序的设计——NFA转换为DFA | ||
实验目的 | 理解并掌握NFA转换为DFA的实现过程 | ||
实验方案 | 实验过程： 1） 输入NFA状态表以及转换状态（L,D），将每一个状态转换表以链表的形式的链接起来，以栈的形式存储； 2） 输入初始状态，求取该状态的ε闭包，以及在状态转换下的DFA集合，当求得DFA后，以该DFA为新的NFA集合，求新的ε闭包，直到到达最后状态或进入重复循环，则求另一个状态转换下的DFA集合； 3） 输出NFA在转换状态的DFA集合； | ||
实验记录 | 求取ε闭包： Node* Closure(Node* closure, int state, 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; } return closure; } NFA转换DFA的实现过程： Node* NFAtoDFA(Node* NFA, Node* List, string change) {//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; } return DFA; } 问题解决代码： void solve(Node* NFA, Node* List, string transition[], int number2) { Node* DFA = (Node*)malloc(sizeof(Node)); Node* newNode1 = (Node*)malloc(sizeof(Node)); Node* newNode2 = (Node*)malloc(sizeof(Node)); int* array1 = new int[VOLUME]; int* array2 = new int[VOLUME]; int length1, length2; bool flag; for (int i = 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; } el { flag = 0;break; } } } el flag = 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的过程，在实验开始之前，需要对转换过程有清楚的了解，找到合适的方法处理转换终止和转换重复的情况，同时要清晰准确的输入条件可以简化一定的程序处理过程，在本次实验中，对同一状态的重复是所面临的处理困难，通过解决问题，并实际动手操作加强了自己的动手能力，也加深了对NFA到DFA装换的掌握。 | ||
本文发布于:2023-07-14 16:18:57，感谢您对本站的认可！
本文链接：https://www.wtabcd.cn/fanwen/fan/82/1096412.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
