文法的化简和改造编译原理.doc

深 圳 大 学实 验 报 告课程名称：编译原理实验名称：文法的化简和改造姓 名：学 号：班 级：实验日期：第6周、第8周实验课一.实验目的1) 编写文法的化简和改造程序；二.实验环境1) 硬件环境：计算机；2) 软件环境：C/C+编译器；三.实验内容1. 用C/C+语言编写方法的化简和改造程序，实现以下功能之一（如实现两个功能，则满分为110分；如实现三个功能，则满分为120分）：(1) 无用符号和无用产生式的删除，参考课本中算法2.1和算法2.2。(2) -产生式的消除，参考课本中算法2.3、2.4和2.5。(3) 单产生式的消除，参考课本中算法2.6。从文件或终端中读入文法，并将化简和改造后的文法输出到另一文件或终端中。文法的表示如下：S-aSS-WS-UU-aV-bV V-acW-aW用空字符表示用大写的拉丁字母表示文法的非终结符号，用小写的拉丁字母表示文法的终结符号，每个产生式占一行，第一个产生式的左部为开始符号。在下面写出代码，并用课本2.4节中相应的例子进行验证，提供相应的截图（对窗口截图时先同时按alt和prtscn键，再按ctrl+v粘贴）答：课本中的结果为：S-aS S-U U-a而在实验中输出结果为：S-aS S-a下面是书本中算法的主要代码：/algorithm21, algorithm22用于消除无用产生式/算法2.1void algorithm21()SymbolSet VN1;ProductionSet P1;struct Lnode *left = NULL;struct 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(&Terminators, right-name) = 0)flag = 0;break;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 = left-right;while(right)if(strcmp(right-name, ) = 0)break;if(IsInSet(&Terminators, right-name) = 0) & ( IsInSet(&VN1, right-name) = 0)flag = 0;break;right = right-next;if(flag = 1)/如果原来不存在则添加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(&Terminators, right-name) = 0) &( IsInSet(&VN1, right-name) = 0)flag = 0;break;right = right-next;if(flag = 1)AddPro(&P1, left);left = left-next;/转移到系统链表集合/删除原有的ClearProductionSet(&Productions);DestroySymbolSet(&NonTerminators);/转移Productions.num = P1.num;Productions.next = P1.next;NonTerminators.next = VN1.next;/算法2.2void 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;P1.num = 0;/开始符号放入VN1AddSym(&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(&NonTerminators, right-name) = 1)added = AddSym(&VN1, right-name);else if(IsInSet(&Terminators, right-name) = 1 | strcmp(right-name, ) = 0)added = AddSym(&VT1, right-name);right = right-next;left = left-next;/第二步left = Productions.next;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(&Productions);DestroySymbolSet(&NonTerminators);DestroySymbolSet(&Terminators);/转移Productions.num = P1.num;Productions.next = P1.next;NonTerminators.next = VN1.next;Terminators.next = VT1.next;/algorithm23,algorithm24用于消除-产生式/算法2.3void 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)AddSym(&W1, left-name);left = left-next;/第二步added = 1;while(added)added = 0;left = Productions.next;while(left)flag = 1;right = left-right;while(right)if(IsInSet(&W1, right-name) = 0)flag = 0;break;right = right-next;if(flag = 1)added = AddSym(&W1, left-name);left = left-next;/algorithm23结束，等待算法2.4/算法2.4void algorithm24()ProductionSet P1;struct Symbol *sym = NULL;struct Lnode *left = NULL, *ltmp = NULL, *tmpNew = NULL;struct Rnode *right = NULL, *rtmp = NULL;int flag = 0, added = 1;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;while(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.next = P1.next;Productions.num = P1.num;/递归添加产生式void forAlgo24(ProductionSet *Set, struct Lnode *left, struct Rnode *tail, struct Lnode *p)struct Lnode *ltmp = NULL, *new1 = NULL, *new2 = NULL;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;elseAddPro(Set, p);else if(IsInSet(&W1, left-name) = 0)/复制pnew1 = (struct Lnode *)malloc(sizeof(struct Lnode);new1-name = (char *)malloc(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)new1-right = rt2;tailTmp = new1-right;elsetailTmp-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-right = rt2;elsetailTmp-next = rt2;forAlgo24(Set, left, tail-next, new1);else/复制p,1new1 = (struct Lnode *)malloc(sizeof(struct Lnode);new1-name = (char *)malloc(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)new1-right = rt2;tailTmp = new1-right;elsetailTmp-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-right = rt2;elsetailTmp-next = rt2;forAlgo24(Set, left, tail-next, new1);new1 = NULL;rt1 = rt2 = tailTmp = NULL;/复制p,2new2 = (struct Lnode *)malloc(sizeof(struct Lnode);new2-name = (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-right = rt2;tailTmp = new1-right;elsetailTmp-next = rt2;tailTmp = tailTmp-next;rt1 = rt1-next;forAlgo24(Set, left, tail-next, new2);ClearLNode(p);/算法2.5void algorithm25()struct Lnode *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;left = left-next;/算法2.6void algorithm26()ProductionSet P1;SymbolSet W;struct Lnode *left = NULL, *ltmp = NULL;struct Rnode *right = NULL, *rtmp = NULL;struct Symbol *sym = NULL;int flag = 0, added = 1;P1.next = NULL;P1.num = 0;W.next = NULL;left = Productions.next