实验2-预测分析算法的设计与实现(1).doc

实验二 预测分析算法的设计与实现（8学时）一、实验目的通过预测分析算法的设计与实现，加深对自上而下语法分析方法的理解，尤其是对自上而下分析条件的理解。二、实验要求 输入文法及待分析的输入串，输出其预测分析过程及结果。 三、实验步骤1. 参考数据结构 (1)/*定义产生式的语法集结构*/typedef struct char formula200;/产生式grammarElement;grammarElement gramOldSet200;/原始文法的产生式集 (2)/*变量定义*/ char terSymbol200;/终结符号 char non_ter200;/非终结符号 char allSymbol400;/所有符号 char firstSET100100;/各产生式右部的FIRST集 char followSET100100;/各产生式左部的FOLLOW集 int M200200;/分析表2. 判断文法的左递归性，将左递归文法转换成非左递归文法。（该步骤可以省略，直接输入非左递归文法）。3.根据文法求FIRST集和FOLLOW集。（1）/*求 First 集的算法*/ beginif X为终结符(X) 在所有产生式中查找X所在的产生式 if 产生式右部第一个字符为终结符或空(即Xa（a）或Xe) then 把a或e加进FIRST(X) if 产生式右部第一个字符为非终结符 then if产生式右部的第一个符号等于当前字符 then 跳到下一条产生式进行查找 if 当前非终结符还没有求其FIRST集 then 查找它的FIRST集并标识此符号已求其FIRST集 求得结果并入到X的FIRST集 if 当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符 then 获取右部符号下一个字符在所有字符集中的位置 if 此字符的FIRST集还未查找 then 找其FIRST集，并标其查找状态为1 把求得的FIRST集并入到X的FIRST集 if 当前右部符号串可推出空且是右部符号串的最后一个字符(即产生式为X,若对一切1 i k,均有e FIRST(),则将e符号加进FIRST(X) then 把空字加入到当前字符X的FIRST集 else 不能推出空字则结束循环 标识当前字符X已查找其FIRST集。end（2）/*求 FOLLOW 集的算法*/begin if X为开始符号 then # FOLLOW(X) 对全部的产生式找一个右部含有当前字符X的产生式 if X在产生式右部的最后(形如产生式AaX) then 查找非终结符A是否已经求过其FOLLOW集.避免循环递归 if 非终结符A已经求过其FOLLOW集 then 把FOLLOW(A)中的元素加入FOLLOW(X) 继续查下一条产生式是否含有X else 求A的FOLLOW集，并标记为A已求其FOLLOW集 else if X不在产生式右部的最后(AaBb) then if 右部X后面的符号串b能推出空字e then 查找b是否已求过其FOLLOW集.避免循环递归 if 已求过b的FOLLOW集 then把FOLLOW(A)中的元素加入FOLLOW(B) 结束本次循环 else if b不能推出空字 then 求 FIRST(b) 把FIRST(b)中所有非空元素加入到FOLLOW(B)中标识当前要求的非终结符X的FOLLOW集已求过 end4.构造预测分析表。/*构造分析表*/在A所在行,a所在列, MA,a的填写方法如下:if (AdP and aFIRST(d) ) do MA,a=Adif (d*e(eFIRST(d) and aFOLLOW(A) do MA,a=Ad;else do MA,a=ERR.5.构造总控程序。程序流程图如图1所示：N$和文法开始符号进S栈第一个输入符号读进aS栈顶符号上托出去放X中X?X=a?X=$?将下一个输入符号读进aX=a?查MX,a=xy1y2yn?将y1y2yn逆序放入S栈中,若右部符号串为e,则e不进S栈出错正确出错出错YNYNYNYYN图16.对给定的输入串，给出分析过程及结果。四、实验报告要求1.写出编程思路、源代码（或流程图）；2.写出上机调试时发现的问题，以及解决的过程；3.写出你所使用的测试数据及结果；4.谈谈你的体会。5.上机8小时，完成实验报告2小时。程序代码:#include stdio.h#include stdlib.h#define MaxRuleNum 8#define MaxVnNum 5#define MaxVtNum 5#define MaxStackDepth 20#define MaxPLength 20#define MaxStLength 50struct pRNode /*产生式右部结构*/ int rCursor; struct pRNode *next;struct pNode int lCursor; int rLength; /*右部长度*/ struct pRNode *rHead; /*右部结点头指针*/;char VnMaxVnNum + 1; /*非终结符集*/int vnNum;char VtMaxVtNum + 1; /*终结符集*/int vtNum;struct pNode PMaxRuleNum; int PNum; char bufferMaxPLength + 1;char ch; char stMaxStLength; /*要分析的符号串*/struct collectNode int nVt; struct collectNode *next;struct collectNode* firstMaxVnNum + 1; /*first集*/struct collectNode* followMaxVnNum + 1; /*follow集*/int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;int analyseStackMaxStackDepth + 1; /*分析栈*/int topAnalyse; /*分析栈顶*/void Init();/*初始化*/int IndexCh(char ch);void InputVt(); /*输入终结符*/void InputVn();/*输入非终结符*/void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/void InputP();/*产生式输入*/bool CheckP(char * st);/*判断产生式正确性*/void First(int U);void AddFirst(int U, int nCh); /*加入first集*/bool HaveEmpty(int nVn); void Follow(int V);/*计算follow集*/void AddFollow(int V, int nCh, int kind);void ShowCollect(struct collectNode *collect);/*输出first或follow集*/void FirstFollow();/*计算first和follow*/void CreateAT();/*构造预测分析表*/void ShowAT();/*输出分析表*/void Identify(char *st);void InitStack();void ShowStack();void Pop();void Push(int r);int main() char todo,ch; Init(); InputVn(); InputVt(); InputP(); getchar(); FirstFollow(); printf(所得first集为：); ShowCollect(first); printf(所得follow集为：); ShowCollect(follow); CreateAT(); ShowAT(); todo = y; while(y = todo) printf(n是否继续进行句型分析？(y / n):); todo = getchar(); while(y != todo & n != todo) printf(n(y / n)? ); todo = getchar(); if(y = todo) int i; InitStack(); printf(请输入符号串(以#结束) : ); ch = getchar(); i = 0; while(# != ch & i MaxStLength) if( != ch & n != ch) sti+ = ch; ch = getchar(); if(# = ch & i MaxStLength) sti = ch; Identify(st); else printf(输入出错！n); getchar();void Init() int i,j; vnNum = 0; vtNum = 0; PNum = 0; for(i = 0; i = MaxVnNum; i+) Vni = 0; for(i = 0; i = MaxVtNum; i+) Vti = 0; for(i = 0; i MaxRuleNum; i+) Pi.lCursor = NULL; Pi.rHead = NULL; Pi.rLength = 0; PNum = 0; for(i = 0; i = MaxPLength; i+) bufferi = 0; for(i = 0; i MaxVnNum; i+) firsti = NULL; followi = NULL; for(i = 0; i = MaxVnNum; i+) for(j = 0; j = MaxVnNum + 1; j+) analyseTableij = -1; int IndexCh(char ch) int n; n = 0; /*is Vn?*/ while(ch != Vnn & 0 != Vnn) n+; if(0 != Vnn) return 100 + n; n = 0; /*is Vt?*/ while(ch != Vtn & 0 != Vtn) n+; if(0 != Vtn) return n; return -1;/*输出Vn或Vt的内容*/void ShowChArray(char* collect) int k = 0; while(0 != collectk) printf( %c , collectk+); printf(n);/*输入非终结符*/void InputVn() int inErr = 1; int n,k; char ch; while(inErr) printf(n请输入所有的非终结符，注意：); printf(请将开始符放在第一位，并以#号结束:n); ch = ; n = 0; /*初始化数组*/ while(n MaxVnNum) Vnn+ = 0; n = 0; while(# != ch) & (n MaxVnNum) if( != ch & n != ch & -1 = IndexCh(ch) Vnn+ = ch; vnNum+; ch = getchar(); Vnn = #; /*以#标志结束用于判断长度是否合法*/ k = n; if(# != ch) if( # != (ch = getchar() while(# != (ch = getchar() ; printf(n符号数目超过限制！n); inErr = 1; continue; /*正确性确认，正确则，执行下下面，否则重新输入*/ Vnk = 0; ShowChArray(Vn); ch = ; while(y != ch & n != ch) if(n != ch) printf(输入正确确认?(y/n):); scanf(%c, &ch); if(n = ch) printf(录入错误重新输入！n); inErr = 1; else inErr = 0; /*输入终结符*/void InputVt() int inErr = 1; int n,k; char ch; while(inErr) printf(n请输入所有的终结符，注意：); printf(以#号结束:n); ch = ; n = 0; /*初始化数组*/ while(n MaxVtNum) Vtn+ = 0; n = 0; while(# != ch) & (n MaxVtNum) if( != ch & n != ch & -1 = IndexCh(ch) Vtn+ = ch; vtNum+; ch = getchar(); Vtn = #; k = n; if(# != ch) if( # != (ch = getchar() while(# != (ch = getchar() ; printf(n符号数目超过限制！n); inErr = 1; continue; Vtk = 0; ShowChArray(Vt); ch = ; while(y != ch & n != ch) if(n != ch) printf(输入正确确认?(y/n):); scanf(%c, &ch); if(n = ch) printf(录入错误重新输入！n); inErr = 1; else inErr = 0; /*产生式输入*/void InputP() char ch; int i = 0, n,num; printf(请输入文法产生式的个数：); scanf(%d, &num); PNum = num; getchar(); /*消除回车符*/ printf(n请输入文法的%d个产生式,并以回车分隔每个产生式：, num); printf(n); while(i num) printf(第%d个：, i); /*初始化*/ for(n =0; n MaxPLength; n+) buffern = 0; /*输入产生式串*/ ch = ; n = 0; while(n != (ch = getchar() & n rCursor = IndexCh(buffer3); pt-next = NULL; Pi.rHead = pt; n = 4; while(0 != buffern) qt = (pRNode*)malloc(sizeof(pRNode); qt-rCursor = IndexCh(buffern); qt-next = NULL; pt-next = qt; pt = qt; n+; Pi.rLength = n - 3; i+; else printf(输入符号含非法在成分，请重新输入！n); /*判断产生式正确性*/bool CheckP(char * st) int n; if(100 IndexCh(st0) return false; if(- != st1) return false; if( != st2) return false; for(n = 3; 0 != stn; n +) if(-1 = IndexCh(stn) return false; return true;void First(int U) int i,j; for(i = 0; i PNum; i+) if(Pi.lCursor = U) struct pRNode* pt; pt = Pi.rHead; j = 0; while(j pt-rCursor) AddFirst(U, pt-rCursor); break; else if(NULL = firstpt-rCursor - 100) First(pt-rCursor); AddFirst(U, pt-rCursor); if(!HaveEmpty(pt-rCursor) break; else pt = pt-next; j+; if(j = Pi.rLength) /*当产生式右部都能推出空时*/ AddFirst(U, -1); /*加入first集*/void AddFirst(int U, int nCh) struct collectNode *pt, *qt; int ch; /*用于处理Vn*/ pt = NULL; qt = NULL; if(nCh nVt = nCh) break; else qt = pt; pt = pt-next; if(NULL = pt) pt = (struct collectNode *)malloc(sizeof(struct collectNode); pt-nVt = nCh; pt-next = NULL; if(NULL = firstU - 100) firstU - 100 = pt; else qt-next = pt; /*qt指向first集的最后一个元素*/ pt = pt-next; else pt = firstnCh - 100; while(NULL != pt) ch = pt-nVt; if(-1 != ch) AddFirst(U, ch); pt = pt-next; bool HaveEmpty(int nVn) if(nVn nVt) return true; pt = pt-next; return false;void Follow(int V) int i; struct pRNode *pt ; if(100 = V) /*当为初始符时*/ AddFollow(V, -1, 0 ); for(i = 0; i rCursor != V) pt = pt-next; if(NULL != pt) pt = pt-next; if(NULL = pt) if(NULL = followPi.lCursor - 100 & Pi.lCursor != V) Follow(Pi.lCursor); AddFollow(V, Pi.lCursor, 0); else while(NULL != pt & HaveEmpty(pt-rCursor) AddFollow(V, pt-rCursor, 1); pt = pt-next; if(NULL = pt) if(NULL = followPi.lCursor - 100 & Pi.lCursor != V) Follow(Pi.lCursor); AddFollow(V, Pi.lCursor, 0); else AddFollow(V, pt-rCursor, 1); void AddFollow(int V, int nCh, int kind) struct collectNode *pt, *qt; int ch; pt = NULL; qt = NULL; if(nCh nVt = nCh) break; else qt = pt; pt = pt-next; if(NULL = pt) pt = (struct collectNode *)malloc(sizeof(struct collectNode); pt-nVt = nCh; pt-next = NULL; if(NULL = followV - 100) followV - 100 = pt; else qt-next = pt; /*qt指向follow集的最后一个元素*/ pt = pt-next; else if(0 = kind) pt = follownCh - 100; while(NULL != pt) ch = pt-nVt; AddFollow(V, ch, 0); pt = pt-next; else pt = firstnCh - 100; while(NULL != pt) ch = pt-nVt; if(-1 != ch) AddFollow(V, ch, 1); pt = pt-next; /*输出first或follow集*/void ShowCollect(struct collectNode *collect) int i; struct collectNode *pt; i = 0; while(NULL != collecti) pt = collecti; printf(n%c:t, Vni); while(NULL != pt) if(-1 != pt-nVt) printf( %c, Vtpt-nVt); else printf( #); pt = pt-next; i+; printf(n);/*计算first和follow*/void FirstFollow() int i; i = 0; while(0 != Vni) if(NULL = firsti) First(100 + i); i+; i = 0; while(0 != Vni) if(NULL = followi) Follow(100 + i); i+; /*构造预测分析表*/void CreateAT() int i; struct pRNode *pt; struct collectNode *ct; for(i = 0; i rCursor) ct = firstpt-rCursor - 100; while(NULL != ct) if(-1 != ct-nVt) analyseTablePi.lCursor - 100ct-nVt = i; ct = ct-next; pt = pt-next; if(NULL = pt) ct = followPi.lCursor - 100; while(NULL != ct) if(-1 != ct-nVt) analyseTablePi.lCursor - 100ct-nVt = i; else analyseTablePi.lCursor - 100vtNum = i; ct = ct-next; else if(100 rCursor) /*不含空的非终结符*/ ct = firstpt-rCursor - 100; while(NULL != ct) analyseTablePi.lCursor - 100ct-nVt = i; ct = ct-next; else /*终结符或者空*/ if(-1 = pt-rCursor) ct = followPi.lCursor - 100; while(NULL != ct) if(-1 != ct-nVt) analyseTablePi.lCursor - 100ct-nVt = i; else /*当含有#号时*/ analyseTablePi.lCursor - 100vtNum = i; ct = ct-next; else /*为终结符*/ analyseTablePi.lCursor - 100pt-rCursor = i; /*输出分析表*/void ShowAT() int i,j; printf(构造预测分析表如下：n); printf(t|t); for(i = 0; i vtNum; i+) printf(%ct, Vti); printf(#tn); printf(- - -t|- - -t); for(i = 0; i = vtNum; i+) printf(- - -t); printf(n); for(i = 0; i vnNum; i+) printf(%ct|t, Vni); for(j = 0; j analyseStacktopAnalyse) if(analyseStacktopAnalyse = IndexCh(stcurrent) Pop(); current+; step+; printf(%dt, step); ShowStack(); printf(tt%ctt出栈、后移n, stcurrent); else printf(%c-%c不匹配！, analyseStacktopAnalyse, stc