《2022年文法的化简和改造编译原理借鉴》由会员分享，可在线阅读，更多相关《2022年文法的化简和改造编译原理借鉴（20页珍藏版）》请在金锄头文库上搜索。
1、深圳大学实验报告课程名称：编译原理实验名称：文法的化简和改造姓名：学号：班级：实验日期：第6 周、第 8 周实验课名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 20 页 - - - - - - - - - 一. 实验目的1) 编写文法的化简和改造程序；二. 实验环境1) 硬件环境：计算机；2) 软件环境： C/C+编译器；三. 实验内容1. 用 C/C+ 语言编写方法的化简和改造程序，实现以下功能之一（如实现两个功能，则满分为 110分；如实现三个功能，则满分为120分
2、） ：(1) 无用符号和无用产生式的删除，参考课本中算法2.1和算法2.2。(2) -产生式的消除，参考课本中算法2.3、 2.4和 2.5。(3) 单产生式的消除，参考课本中算法2.6。从文件或终端中读入文法，并将化简和改造后的文法输出到另一文件或终端中。文法的表示如下：S-aS S-W S-U U-a V-bV V-ac W-aW 用空字符表示 用大写的拉丁字母表示文法的非终结符号，用小写的拉丁字母表示文法的终结符号，每个产生式占一行，第一个产生式的左部为开始符号。在下面写出代码，并用课本2.4 节中相应的例子进行验证，提供相应的截图（对窗口截图时先同时按alt 和 prtscn 键，再按
3、ctrl+v粘贴）答：课本中的结果为：S-aS S-U U-a 而在实验中输出结果为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 20 页 - - - - - - - - - S-aS S-a 下面是书本中算法的主要代码：/algorithm21, algorithm22用于消除无用产生式/算法 2.1 void algorithm21() SymbolSet VN1; ProductionSet P1; struct Lnode *left = NULL; stru
4、ct Rnode *right = NULL; int flag = 0, added = 1; VN1.next = NULL; P1.next = NULL; P1.num = 0; /第一步left = Productions.next; while(left) flag = 1; right = left-right; while(right) if(strcmp(right-name, ) = 0) break; if(IsInSet(&T erminators, right-name) = 0) flag = 0; break; 名师资料总结 - - -精品资料欢迎下载 - - -
5、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 20 页 - - - - - - - - - right = right-next; if(flag = 1) /如果原来不存在则添加if(IsInSet(&VN1, left-name) = 0) AddSym(&VN1, left-name); left = left-next; /第二步added = 1; while(added) added = 0; left = Productions.next; while(left) flag = 1; right = lef
6、t-right; while(right) if(strcmp(right-name, ) = 0) break; if(IsInSet(&T erminators, right-name) = 0) & ( IsInSet(&VN1, right-name) = 0) flag = 0; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 20 页 - - - - - - - - - right = right-next; if(flag = 1) /如果原来
7、不存在则添加if(IsInSet(&VN1, left-name) = 0) AddSym(&VN1, left-name); added = 1; left = left-next; /第三步left = Productions.next; while(left) flag = 1; right = left-right; while(right) if(strcmp(right-name, ) = 0) break; if(IsInSet(&T erminators, right-name) = 0) &( IsInSet(&VN1, right-name) = 0) flag = 0;
8、break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 20 页 - - - - - - - - - right = right-next; if(flag = 1) AddPro(&P1, left); left = left-next; /转移到系统链表集合 /删除原有的ClearProductionSet(&Productions); DestroySymbolSet(&NonT erminators); /转移Productions.num = P1.num
9、; Productions.next = P1.next; NonTerminators.next = VN1.next; /算法 2.2 void algorithm22() SymbolSet VN1, VT1; ProductionSet P1; struct Lnode *left = NULL; struct Rnode *right = NULL; int flag = 0, added = 1; VN1.next = NULL; VT1.next = NULL; P1.next = NULL; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -
10、- - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 20 页 - - - - - - - - - P1.num = 0; /开始符号放入VN1 AddSym(&VN1, Start); /第一步added = 1; while(added) added = 0; left = Productions.next; while(left) if(IsInSet(&VN1, left-name) = 1) right = left-right; while(right) if(IsInSet(&NonT erminators, right-name) = 1) ad
11、ded = AddSym(&VN1, right-name); else if(IsInSet(&T erminators, right-name) = 1 | strcmp(right-name, ) = 0) added = AddSym(&VT1, right-name); right = right-next; left = left-next; /第二步left = Productions.next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 20 页 -
12、 - - - - - - - - while(left) flag = 1; if(IsInSet(&VN1, left-name) = 1) right = left-right; while(right) if(IsInSet(&VN1, right-name) = 0 & IsInSet(&VT1, right-name) = 0) flag = 0; break; right = right-next; if(flag = 1) AddPro(&P1, left); left = left-next; /转移到系统链表集合 /删除原有的ClearProductionSet(&Produ
13、ctions); DestroySymbolSet(&NonT erminators); DestroySymbolSet(&T erminators); /转移Productions.num = P1.num; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 20 页 - - - - - - - - - Productions.next = P1.next; NonTerminators.next = VN1.next; Terminators.next = VT1.n
14、ext; /algorithm23,algorithm24用于消除 -产生式/算法 2.3 void algorithm23() struct Lnode *left = NULL; struct Rnode *right = NULL; int flag = 0, added = 1; W1.next = NULL; W2.next = NULL; /第一步left = Productions.next; while(left) right = left-right; /如果是空产生式if(right-next = NULL) & strcmp(right-name, ) = 0) AddS
15、ym(&W1, left-name); left = left-next; /第二步added = 1; while(added) added = 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 20 页 - - - - - - - - - left = Productions.next; while(left) flag = 1; right = left-right; while(right) if(IsInSet(&W1, right-name) = 0) f
16、lag = 0; break; right = right-next; if(flag = 1) added = AddSym(&W1, left-name); left = left-next; /algorithm23 结束，等待算法2.4 /算法 2.4 void algorithm24() ProductionSet P1; struct Symbol *sym = NULL;struct Lnode *left = NULL, *ltmp = NULL, *tmpNew = NULL;struct Rnode *right = NULL, *rtmp = NULL; int flag
17、 = 0, added = 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 20 页 - - - - - - - - - P1.next = NULL; P1.num = 0; /第一步sym = NonTerminators.next; while(sym) if(IsInSet(&W1, sym-name) = 0) AddSym(&W2, sym-name); sym = sym-next; /第二步left = Productions.next; whil
18、e(left) tmpNew = (struct Lnode *)malloc(sizeof(struct Lnode); tmpNew-name = (char *)malloc(strlen(left-name) + 1); strcpy(tmpNew-name, left-name); tmpNew-next = NULL; tmpNew-right = NULL; forAlgo24(&P1, left, left-right, tmpNew); left = left-next; /转移ClearProductionSet(&Productions); Productions.nex
19、t = P1.next; Productions.num = P1.num; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 20 页 - - - - - - - - - /递归添加产生式void forAlgo24(ProductionSet *Set, struct Lnode *left, struct Rnode *tail, struct Lnode *p) struct Lnode *ltmp = NULL, *new1 = NULL, *new2 = NU
20、LL;struct Rnode *rtmp = NULL, *rt1 = NULL, *rt2 = NULL, *tailTmp = NULL; if(tail = NULL) rtmp = p-right; if(strcmp(rtmp-name, ) = 0 & rtmp-next = NULL) return; else AddPro(Set, p); else if(IsInSet(&W1, left-name) = 0) /复制 pnew1 = (struct Lnode *)malloc(sizeof(struct Lnode); new1-name = (char *)mallo
21、c(strlen(p-name) + 1); strcpy(new1-name, p-name); new1-next = NULL; new1-right = NULL; rt1 = p-right; while(rt1) rt2 = (struct Rnode *)malloc(sizeof(struct Rnode); rt2-name = (char *)malloc(strlen(rt1-name) + 1); strcpy(rt2-name, rt1-name); rt2-next = NULL; if(new1-right = NULL) 名师资料总结 - - -精品资料欢迎下载
22、 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 20 页 - - - - - - - - - new1-right = rt2; tailTmp = new1-right; else tailTmp-next = rt2; tailTmp = tailTmp-next; rt1 = rt1-next; rt2 = (struct Rnode *)malloc(sizeof(struct Rnode); rt2-name = (char *)malloc(strlen(tail-name) + 1); strc
23、py(rt2-name, tail-name); rt2-next = NULL; if(tailTmp = NULL) new1-right = rt2; else tailTmp-next = rt2; forAlgo24(Set, left, tail-next, new1); else /复制 p,1 new1 = (struct Lnode *)malloc(sizeof(struct Lnode); new1-name = (char *)malloc(strlen(p-name) + 1); strcpy(new1-name, p-name); new1-next = NULL;
24、 new1-right = NULL; rt1 = p-right; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 20 页 - - - - - - - - - while(rt1) rt2 = (struct Rnode *)malloc(sizeof(struct Rnode); rt2-name = (char *)malloc(strlen(rt1-name) + 1); strcpy(rt2-name, rt1-name); rt2-next = NULL;
25、 if(new1-right = NULL) new1-right = rt2; tailTmp = new1-right; else tailTmp-next = rt2; tailTmp = tailTmp-next; rt1 = rt1-next; rt2 = (struct Rnode *)malloc(sizeof(struct Rnode); rt2-name = (char *)malloc(strlen(tail-name) + 1); strcpy(rt2-name, tail-name); rt2-next = NULL; if(tailTmp = NULL) new1-r
26、ight = rt2; else tailTmp-next = rt2; forAlgo24(Set, left, tail-next, new1); new1 = NULL; rt1 = rt2 = tailTmp = NULL; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 20 页 - - - - - - - - - / /复制 p,2 new2 = (struct Lnode *)malloc(sizeof(struct Lnode); new2-name =
27、 (char *)malloc(strlen(p-name) + 1); strcpy(new2-name, p-name); new2-next = NULL; new2-right = NULL; rt1 = p-right; while(rt1) rt2 = (struct Rnode *)malloc(sizeof(struct Rnode); rt2-name = (char *)malloc(strlen(rt1-name) + 1); strcpy(rt2-name, rt1-name); rt2-next = NULL; if(new2-right = NULL) new1-r
28、ight = rt2; tailTmp = new1-right; else tailTmp-next = rt2; tailTmp = tailTmp-next; rt1 = rt1-next; forAlgo24(Set, left, tail-next, new2); ClearLNode(p); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 20 页 - - - - - - - - - /算法 2.5 void algorithm25() struct Lno
29、de *left = NULL; struct Rnode *right = NULL; int flag = 0, added = 1; char tempMAXLEN = 0; memset(temp, 0, MAXLEN); /首先判断开始符号是否出现在产生式右部left = Productions.next; flag = 0; while(left & flag = 0) right = left-right; while(right) if(strcmp(Start, right-name) = 0) flag = 1; break; right = right-next; lef
30、t = left-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 20 页 - - - - - - - - - /算法 2.6 void algorithm26() ProductionSet P1; SymbolSet W; struct Lnode *left = NULL, *ltmp = NULL;struct Rnode *right = NULL, *rtmp = NULL; struct Symbol *sym = NULL;int flag
31、= 0, added = 1; P1.next = NULL; P1.num = 0; W.next = NULL; left = Productions.next; while(left) added = 1; while(added) added = 0; added = AddSym(&W, left-name); ltmp = Productions.next; while(ltmp) if(IsInSet(&W, ltmp-name) = 1) rtmp = ltmp-right; if(IsInSet(&NonT erminators, rtmp-name) = 1) & (NUL
32、L = rtmp-next) added = AddSym(&W, rtmp-name); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 20 页 - - - - - - - - - ltmp = ltmp-next; /第二步sym = W.next; while(sym) ltmp = Productions.next; while(ltmp) if(strcmp(sym-name, ltmp-name) = 0) rtmp = ltmp-right; if(rt
33、mp-next != NULL | IsInSet(&NonT erminators, rtmp-name) = 0) AddPro1(&P1, &P1, left, ltmp); ltmp = ltmp-next; sym = sym-next; DestroySymbolSet(&W); left = left-next; /转移ClearProductionSet(&Productions); DestroySymbolSet(&W); Productions.next = P1.next; Productions.num = P1.num; 名师资料总结 - - -精品资料欢迎下载 -
34、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 20 页 - - - - - - - - - 经过测试这个代码基本上没有问题，下面只给出2.4 节中的一个文法经过化简和改造后的结果；要想得到其他文法的结果只要改变grammer .txt 中的输入文法即可。输出结果：原文法删除单产生式后的文法删除空产生式后的文法删除无用产生式后的文法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 20 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 20 页 - - - - - - - - -
