LL1语法分析器实验报告.doc

《LL1语法分析器实验报告.doc》由会员分享，可在线阅读，更多相关《LL1语法分析器实验报告.doc（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上南京信息工程大学实验（实习）报告实验（实习）名称 LL（1）文法语法分析设计 实验（实习）日期 11月28日 得分 指导教师 林美华 系 计算机 专业 计算机科学与技术 年级 2011 班次 计科3班 姓名 王欣 学号 一 实验目的1熟悉判断LL（1）文法的方法及对某一输入串的分析过程。2学会构造表达式文法的预测分析表。二 实验内容编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。三 实验步骤从键盘读入输入串，并判断正误；若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL（1）文法；若符合LL（1）文法，由

2、程序自动构造LL（1）分析表；由算法判断输入符号串是否为该文法的句型【源代码】#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;/*左部符号

3、序号*/int rLength;/*右部长度*/*注当rLength = 1 时，rCursor = -1为空产生式*/struct pRNode *rHead;/*右部结点头指针*/;char VnMaxVnNum + 1;/*非终结符集*/int vnNum;char VtMaxVtNum + 1;/*终结符集*/int vtNum;struct pNode PMaxRuleNum;/*产生式*/int PNum;/*产生式实际个数*/char bufferMaxPLength + 1;char ch;/*符号或string ch;*/char stMaxStLength; /*要分析的符

4、号串*/struct collectNode/*集合元素结点结构*/int nVt;/*在终结符集中的下标*/struct collectNode *next;struct collectNode* firstMaxVnNum + 1;/*first集*/struct collectNode* followMaxVnNum + 1;/*follow集*/int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;/*预测分析表存放为产生式的编号，+1用于存放结束符，多+1用于存放#(-1)*/int analyseStackMaxStackDepth + 1;/*

5、分析栈*/int topAnalyse;/*分析栈顶*/*int reverseStackMaxStackDepth + 1;/*颠倒顺序栈*/*int topReverse;/*倒叙栈顶*/void Init();/*初始化*/int IndexCh(char ch);/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/void InputVt();/*输入终结符*/void InputVn();/*输入非终结符*/void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/void InputP();/*产生式输入

6、*/bool CheckP(char * st);/*判断产生式正确性*/void First(int U);/*计算first集,U-xx.*/void AddFirst(int U, int nCh);/*加入first集*/bool HaveEmpty(int nVn); /*判断first集中是否有空(-1)*/void Follow(int V);/*计算follow集*/void AddFollow(int V, int nCh, int kind);/*加入follow集，kind = 0表加入follow集，kind = 1加入first集*/void ShowCollect(

7、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);/*使用

8、产生式入栈操作*/#include LL1.hvoid main(void)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 !

9、= 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;

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

11、+)for(j = 0; j = MaxVnNum + 1; j+)analyseTableij = -1;/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-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(

12、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 &

13、-1 = IndexCh(ch)Vnn+ = ch;vnNum+;ch = getchar();Vnn = #;/*以“#”标志结束用于判断长度是否合法*/k = n;/*k用于记录n以便改Vnn=0*/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

14、(输入正确确认?(y/n):);scanf(%c, &ch);if(n = ch)printf(录入错误重新输入！n);inErr = 1;elseinErr = 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 = Ind

15、exCh(ch)Vtn+ = ch;vtNum+;ch = getchar();Vtn = #;/*以“#”标志结束*/k = n;/*k用于记录n以便改Vtn=0*/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):);sca

16、nf(%c, &ch);if(n = ch)printf(录入错误重新输入！n);inErr = 1;elseinErr = 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

17、= 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+;/*调试时使用*/elseprintf(输入符号含非法在成分，请重新输

18、入！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;/*=first & follow=*/*计算first集,U-xx.*/void First(int U)int i,j;for(i = 0; i PNum; i+)if(Pi.lCursor = U)st

19、ruct pRNode* pt;pt = Pi.rHead;j = 0;while(j pt-rCursor)/*注:此处因编程出错,使空产生式时rlength同样是1,故此处同样可处理空产生式*/AddFirst(U, pt-rCursor);break;elseif(NULL = firstpt-rCursor - 100)First(pt-rCursor);AddFirst(U, pt-rCursor);if(!HaveEmpty(pt-rCursor)break;elsept = pt-next;j+;if(j = Pi.rLength)/*当产生式右部都能推出空时*/AddFirst

20、(U, -1);/*加入first集*/void AddFirst(int U, int nCh)/*当数值小于100时nCh为Vt*/*当处理非终结符时,AddFirst不添加空项(-1)*/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 = nCh;pt-

21、next = NULL;if(NULL = firstU - 100)firstU - 100 = pt;elseqt-next = pt;/*qt指向first集的最后一个元素*/pt = pt-next;elsept = firstnCh - 100;while(NULL != pt)ch = pt-nVt;if(-1 != ch)AddFirst(U, ch);pt = pt-next;/*判断first集中是否有空(-1)*/bool HaveEmpty(int nVn)if(nVn nVt)return true;pt = pt-next;return false;/*计算follo

22、w集,例：U-xVy,U-xV.(注：初始符必含#-1)*/void Follow(int V)int i;struct pRNode *pt;if(100 = V)/*当为初始符时*/AddFollow(V, -1, 0 );for(i = 0; i rCursor != V) /*注此不能处理：U-xVyVz的情况*/pt = pt-next;if(NULL != pt)pt = pt-next;/*V右侧的符号*/if(NULL = pt)/*当V后为空时V-xV，将左符的follow集并入V的follow集中*/if(NULL = followPi.lCursor - 100 & Pi

23、.lCursor != V)Follow(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);else/*不为空时V-xVy,(注意：y-)，调用AddFollow加入Vt或y的first集*/while(NULL != pt & HaveEmpty(pt-rCursor)AddFollow(V, pt-rCursor, 1);/*y的前缀中有空时，加如first集*/pt = pt-next;if(NULL = pt)/*当后面的字符可以推出空时*/if(NULL = followPi.lCursor - 100 & Pi.lCursor != V)Follow(

24、Pi.lCursor);AddFollow(V, Pi.lCursor, 0);else/*发现不为空的字符时*/AddFollow(V, pt-rCursor, 1);/*当数值小于100时nCh为Vt*/*#用-1表示,kind用于区分是并入符号的first集，还是follow集kind = 0表加入follow集，kind = 1加入first集*/void AddFollow(int V, int nCh, int kind)struct collectNode *pt, *qt;int ch;/*用于处理Vn*/pt = NULL;qt = NULL;if(nCh nVt = nCh

25、)break;elseqt = 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;elseqt-next = pt;/*qt指向follow集的最后一个元素*/pt = pt-next;else/*为非终结符时，要区分是加first还是follow*/if(0 = kind)pt = follownCh - 100;while

26、(NULL != pt)ch = pt-nVt;AddFollow(V, ch, 0);pt = pt-next;elsept = 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%

27、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 != Vni)if(NULL = followi)Follow(100 + i);i+;/*=构造预测分析表,例：U:xyz=*/void CreateAT()in

28、t 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)/*NULL = pt，说明xyz-,用到follow中的符号*/ct = followPi.lCursor - 100;while(NULL

29、 != ct)if(-1 != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i;else/*当含有#号时*/analyseTablePi.lCursor - 100vtNum = i;ct = ct-next;elseif(100 rCursor)/*不含空的非终结符*/ct = firstpt-rCursor - 100;while(NULL != ct)analyseTablePi.lCursor - 100ct-nVt = i;ct = ct-next;else/*终结符或者空*/if(-1 = pt-rCursor)/*-1为空产生式时*/c

30、t = 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;1 printf(构造预测分析表如下：n);printf(t|t);for(i = 0; i vtNu

31、m; i+)printf(%ct, Vti);printf(#tn);2 printf(- - -t|- - -t);for(i = 0; i = vtNum; i+)printf(- - -t);printf(n);3 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);Sh

32、owStack();printf(tt%ctt出栈、后移n, stcurrent);elseprintf(%c-%c不匹配！, analyseStacktopAnalyse, stcurrent);printf(此串不是此文法的句子！n);return;else/*当为非终结符时*/r = analyseTableanalyseStacktopAnalyse - 100IndexCh(stcurrent);if(-1 != r)Push(r);/*产生式右部代替左部，指示器不移动*/step+;printf(%dt, step);ShowStack();printf(tt%ctt%dn, st

33、current, r);elseprintf(无可用产生式，此串不是此文法的句子！n);return;if(# = stcurrent)5 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);