文法的化簡和改造編譯原理

1、深 圳 大 學實 驗 報 告課程名稱：編譯原理實驗名稱：文法的化簡和改造姓 名：學 號：班 級：實驗日期：第6周、第8周實驗課一.實驗?zāi)康?) 編寫文法的化簡和改造程序；二.實驗環(huán)境1) 硬件環(huán)境：計算機；2) 軟件環(huán)境：C/C+編譯器；三.實驗內(nèi)容1. 用C/C+語言編寫方法的化簡和改造程序，實現(xiàn)以下功能之一（如實現(xiàn)兩個功能，則滿分為110分；如實現(xiàn)三個功能，則滿分為120分）：(1) 無用符號和無用產(chǎn)生式的刪除，參考課本中算法2.1和算法2.2。(2) -產(chǎn)生式的消除，參考課本中算法2.3、2.4和2.5。(3) 單產(chǎn)生式的消除，參考課本中算法2.6。從文件或終端中讀入文法，并將化簡和改造

2、后的文法輸出到另一文件或終端中。文法的表示如下：S-aSS-WS-UU-aV-bV V-acW-aW用空字符表示用大寫的拉丁字母表示文法的非終結(jié)符號，用小寫的拉丁字母表示文法的終結(jié)符號，每個產(chǎn)生式占一行，第一個產(chǎn)生式的左部為開始符號。在下面寫出代碼，并用課本2.4節(jié)中相應(yīng)的例子進行驗證，提供相應(yīng)的截圖（對窗口截圖時先同時按alt和prtscn鍵，再按ctrl+v粘貼）答：課本中的結(jié)果為：S-aS S-U U-a而在實驗中輸出結(jié)果為：S-aS S-a下面是書本中算法的主要代碼：/algorithm21, algorithm22用于消除無用產(chǎn)生式/算法2.1void algorithm21()Sy

3、mbolSet 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) =

4、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

5、, 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)

6、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;/轉(zhuǎn)移到系統(tǒng)鏈表集合/刪除原有的ClearProductionSet(&Productions);DestroySymbolSet(&NonTerminators);/轉(zhuǎn)移Productions.num = P1.num;Productions.next = P1.next;

7、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 = P

8、roductions.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 = l

9、eft-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;/轉(zhuǎn)移到系統(tǒng)鏈表集合/刪除原有的ClearProductionSet

10、(&Productions);DestroySymbolSet(&NonTerminators);DestroySymbolSet(&Terminators);/轉(zhuǎn)移Productions.num = P1.num;Productions.next = P1.next;NonTerminators.next = VN1.next;Terminators.next = VT1.next;/algorithm23,algorithm24用于消除-產(chǎn)生式/算法2.3void algorithm23()struct Lnode *left = NULL;struct Rnode *right = NU

11、LL;int flag = 0, added = 1;W1.next = NULL;W2.next = NULL;/第一步left = Productions.next;while(left)right = left-right;/如果是空產(chǎn)生式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 =

12、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結(jié)束，等待算法2.4/算法2.4void algorithm24()ProductionSet P1;struct Symbol *sym = NULL;struct Lnode *left = NULL, *ltmp = NULL, *tmpNew = NULL;struct

13、 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 = (c

14、har *)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;/轉(zhuǎn)移ClearProductionSet(&Productions);Productions.next = P1.next;Productions.num = P1.num;/遞歸添加產(chǎn)生式void forAlgo24(ProductionSet *Set, struc

15、t 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, lef

16、t-name) = 0)/復(fù)制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);str

17、cpy(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 = NU

18、LL;if(tailTmp = NULL)new1-right = rt2;elsetailTmp-next = rt2;forAlgo24(Set, left, tail-next, new1);else/復(fù)制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 = (s

19、truct 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 Rnod

20、e);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;/復(fù)制p,2new2 = (struct Lnode *)malloc(sizeof(struct Lnode);new2-name =

21、(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;t

22、ailTmp = 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);/首先判斷開始符號是否出現(xiàn)在產(chǎn)生式右部lef

23、t = 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.nex