试验二LL预测分析

1、编译原理实验指导14非师实验二LL(1)分析的设计与实现开课实验室：A201 , A207实验项目LL(1)分析的设计与实现实验类型设计实验学时4一、实验目的根据某一文法编制调试LL(1)分析程序，以便对任意输入的符号串进行分析。掌握LL(1)分析法的基本原理，LL(1)分析表的构造方法，LL(1)驱动程序的构造方法。二、设备与环境.硬件设备：PC机一台.软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境, 如C C+Java等编程语百环境。三、实验要求.输入文法G的非终结符、终结符和产生式；(1)输出非终结符的FIRST集；(2)输出非终结符的 FOLLOW

2、 集；(3)构造文法G的预测分析表；(4)对输入符号串进行分析。2、编程语言不限。四、实验原理.程序功能(流程图参考)：4)输入文法计算FIRST计算FOLLOW集合集合构造预测分析表调用预测器进行分析第1页共25页编译原理实验指导13非师.计算FIRST集合：First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合。直接收取：对形如 U a的产生式(其中 a是终结符)，把a收入到First(U)中 反复传送：对形入 U P的产生式(其中 P是非终

3、结符)，应把First(P)中的全部内容 传送到First(U)中。算法描述：见教材 P80)若 XC Vt,则 FIRST(X)=X;)若XCVn,且有产生式 X-a，aCVt,则aC FIRST(X);)若 XC Vn,X- 当则 既 FIRST(X)若 X,Y1,丫2,丫3,丫4 Yn 都 Vn,而产生式 X-Y1,Y2 Yn.当Y1,Y2,Y3,Y4 Yn者8能= & 那么 FIRST(X)=并集的 FIRST(Yi)-曷(0=i& (i=1,2,3 ),则 FIRST(X)=并集的 FIRST(Yi)- 并上&.计算FOLLOW 集合：Follow集合是针对非终结符而言的，Follo

4、w(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“#是识别符号的后随符。直接收取：注意产生式右部的每一个形如J-Ua”的组合，把a直接收入到Follow(U)中；直接收取：又形如“ UP”(P是非终结符)的组合，把First(P)直接收入到Follow(U) 中；直接收取：若为文法开始符号S,则把#收入FOLLOW(S);反复传送：对形如U P的产生式(其中P是非终结符)，应把Follow(U)中的全部内 容传送到Follow(P)中。算法描述：见教材 P82)若为文法开始符号 S,则FOLLOW(S)=#)若为文法 A-aBb是一个产生式，则把 FIRST ( b)的

5、非空元素加入 FOLLOW(B) 中。如果b-则把FOLLOW(A)也加入FOLLOW(B)中。.构造预测分析表：(1)对于文法的每条产生式 ATa ,若a=FIRST(a),则MA, a = A Tx ；(2)若名WFIRST(a), b三 FOLLOW(久)贝U MA, b = A 5；(3)分析表M的其他元素均为出错标志error。.预测分析程序流图：见课本P93-P94五、程序源码#include stdio.h#include stdlib.h编译原理实验指导13非师define MaxRuleNum 8define MaxVnNum 5define MaxVtNum 5define

6、 MaxStackDepth 20define MaxPLength 20define MaxStLength 50struct pRNode /*产生式右部结构 */ int rCursor;struct pRNode *next;struct pNodeint lCursor;int rLength; /* 右部长度 */struct pRNode *rHead; /* 右部结点头指针 */ ;char VnMaxVnNum + 1;/* 非终结符集 */int vnNum;char VtMaxVtNum + 1; /* 终结符集 */int vtNum;struct pNode PMax

7、RuleNum;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 analyseStack

8、MaxStackDepth + 1; /* 分析栈 */ int topAnalyse; /* 分析栈顶 */编译原理实验指导13非师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

9、);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(

10、);/* 输出分析表 */void Identify(char *st);void InitStack();void ShowStack();void Pop();void Push(int r);void main(void)(char todo,ch;Init();InputVn();InputVt();InputP();getchar();FirstFollow();printf(所得 first 集为:);ShowCollect(first);printf(所得 follow 集为：);ShowCollect(follow);CreateAT();ShowAT();todo = y;w

11、hile(y = todo) 编译原理实验指导13非师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 Ma

12、xStLength)sti = ch;Identify(st);elseprintf(输入出错！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+)编译原理实验指导13非师(Pi.lCursor = NULL;Pi.rHead = NULL;Pi.rLength = 0;)PNum = 0;for(i = 0; i = MaxP

13、Length; 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

14、& 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);)/*输入非终结符*/编译原理实验指导13非师void InputVn()(int inErr = 1;int n,k;char ch;while(inErr)(printf(n请输入所有的非终结符，注意： );printf(请将开始符放在第一位，并以#结束：n);ch =;n

15、 = 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;/*正确性确认，正确

16、则，执行下下面，否则重新输入 */Vnk = 0;ShowChArray(Vn);ch =;while(y != ch & n != ch)(if(n != ch)编译原理实验指导13非师(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

17、=;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)编译原理实验指导13非师(if( # != (ch = getchar()(while(# != (ch = getchar()；printf(n符号数目超过限制！ n);inErr = 1;continue;Vtk = 0;ShowChAr

18、ray(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);p

19、rintf(n);while(i num)编译原理实验指导13非师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-n

20、ext = NULL;pt-next = qt;pt = qt;n+;Pi.rLength = n - 3;i+;elsen);printf(输入符号含非法在成分，请重新输入！/*判断产生式正确性*/bool CheckP(char * st)int n;if(100 IndexCh(st0)第10页编译原理实验指导13非师return false;if(- != st1) return false;if( != st2)return false;for(n = 3; 0 != stn; n +)(if(-1 = IndexCh(stn) return false;return true;vo

21、id 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;第11页编译原理实验指导13非师

22、) 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;elseqt = pt;pt = pt-next;)if(NULL = pt)pt = (struct collectNode *)malloc(sizeof(struct collectNode); pt-nVt =

23、nCh;pt-next = NULL;if(NULL = firstU - 100)firstU - 100 = pt;) elseqt-next = pt; /*qt指向first集的最后一个元素 */) pt = pt-next;)else第12页编译原理实验指导13非师(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 fa

24、lse;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.lCursoC= V)第13页编译原理实验指导13非师(Follow(Pi.lCursor);)AddFollow(V, Pi.lCursor, 0);)else(while(NULL

25、 != 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 c

26、h;pt = NULL;qt = NULL;if(nCh nVt = nCh) break;else第14页编译原理实验指导13非师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(i

27、f(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;)第15页编译原理实验指导13非师)/* 输出 first 或 follow 集*/void ShowCollect(struct collectNode *collect)(int i;struct

28、collectNode *pt;i = 0;while(NULL != collecti)(pt = collect。;printf(n%c:t, Vni);while(NULL != pt)(if(-1 != pt-nVt)(printf( %c, Vtpt-nVt);)elseprintf( #);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

29、!= Vni)(if(NULL = followi)Follow(100 + i);i+;)/*构造预测分析表*/void CreateAT()第16页编译原理实验指导13非师(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

30、 = followPi.lCursor - 100;while(NULL != ct)(if(-1 != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i; elseanalyseTablePi.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 /*终结符或

31、者空*/(if(-1 = pt-rCursor)第17页编译原理实验指导13非师(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;prin

32、tf(构造预测分析表如下：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+; s

33、tep+; printf(%dt, step); ShowStack(); printf(tt%ctt 出栈、后移 n, stcurrent);) else (printf(%c-%c 不匹配！, analyseStacktopAnalyse, stcurrent);printf(此串不是此文法的句子！n);return;)else /*当为非终结符时*/(r = analyseTableanalyseStacktopAnalyse - 100IndexCh(stcurrent); if(-1 != r) (Push(r); step+; printf(%dt, step);第19页编译原理实

34、验指导13非师ShowStack();printf(tt%ctt%dn, stcurrent, r);) elseprintf(此串不是此文法的句子！n);return;)if(# = stcurrent)if(0 = topAnalyse & # = stcurrent)step+;printf(%dt, step);ShowStack();printf(tt%ctt 分析成功！n, stcurrent);printf(%s是给定文法的句子！n, st);)elsewhile(topAnalyse 0)if(100 analyseStacktopAnalyse)printf(此串不是此文法的句子！n);return;) elser = analyseTableanalyseStacktopAnalyse - 100vtNum; if(-1 != r)Push(r); /*产生式右部代替左部，指示器不移动*/step+;printf(%dt, step);ShowStack();if(0 = topAnalyse & # = stcurrent) printf(tt%ctt 分析成功！ n, stcurrent);printf(%s是给定文法的句子！n, st);)elseprintf(tt%ctt%dn, stcurrent, r);第20页编译原理实验指导13非师) el