《LL1语法分析器实验报告.pdf》由会员分享，可在线阅读，更多相关《LL1语法分析器实验报告.pdf（22页珍藏版）》请在三一文库上搜索。
1、南京信息工程大学实验（实习）报告 实验（实习）名称LL（1）文法语法分析设计实验（实习）日期11 月 28日 得分指导教师林美华 系 计算机专业计算机科学与技术年级2011 班次 计科 3 班姓名王欣学号20112308915 一 实验目的 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 50 struct pRNode/* 产生式右部结构*/ int rCursor;/* 右部序号 */ struct pRNode *next; ; struct pNode/*
3、 产生式结点结构*/ int lCursor;/* 左部符号序号*/ 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
4、+ 1; char ch;/* 符号或 string 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; /* 预测分
5、析表存放为产生式的编号，+1用于存放结束符，多+1 用于存放 #(-1)*/ int analyseStackMaxStackDepth + 1;/* 分析栈 */ int topAnalyse;/* 分析栈顶 */ /*int reverseStackMaxStackDepth + 1;/* 颠倒顺序栈 */ /*int topReverse;/* 倒叙栈顶 */ void Init();/*初始化 */ int IndexCh(char ch); /* 返回 Vn在 Vn表中的位置 +100、 Vt 在 Vt 表中的位置，-1 表示未找到 */ void InputVt();/* 输入终结
6、符 */ void InputVn();/*输入非终结符*/ void ShowChArray(char* collect, int num);/*输出 Vn或 Vt 的内容 */ void InputP();/*产生式输入 */ 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
7、V);/*计算 follow集*/ void AddFollow(int V, int nCh, int kind);/*加入 follow集， kind = 0表加入 follow集， kind = 1加入 first集*/ void ShowCollect(struct collectNode *collect);/*输出 first或 follow集*/ void FirstFollow();/*计算 first和 follow*/ void CreateAT();/*构造预测分析表*/ void ShowAT();/*输出分析表 */ void Identify(char *st);/
8、*主控程序 , 为操作方便 */ /* 分析过程显示操作为本行变换所用，与教程的显示方式不同*/ void InitStack();/*初始化栈及符号串*/ void ShowStack();/*显示符号栈中内容*/ void Pop();/*栈顶出栈 */ void Push(int r);/*使用产生式入栈操作*/ #include “LL1.h“ void main(void) char todo,ch; Init(); InputVn(); InputVt(); InputP(); getchar(); FirstFollow(); printf(“所得 first集为： “); Sh
9、owCollect(first); printf(“所得 follow集为： “); ShowCollect(follow); CreateAT(); ShowAT(); todo = y; while(y = todo) printf(“n是否继续进行句型分析？(y / n):“); todo = getchar(); while(y != todo todo = getchar(); if(y = todo) int i; InitStack(); printf(“请输入符号串( 以#结束 ) : “); ch = getchar(); i = 0; while(# != ch pt-ne
10、xt = 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) r
11、eturn false; if(- != st1) return false; if( != st2) return false; for(n = 3; 0 != stn; n +) if(-1 = IndexCh(stn) return false; return true; /*=first for(i = 0; i pt-rCursor) /* 注: 此处因编程出错, 使空产生式时 rlength同样是 1, 故此处同样可处理空产生式*/ AddFirst(U, pt-rCursor); break; else if(NULL = firstpt-rCursor - 100) First
12、(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)/* 当数值小于100 时 nCh为 Vt*/ /* 当处理非终结符时,AddFirst不添加空项 (-1)*/ struct collectNode *pt, *qt; int ch;/* 用于处理Vn*/ pt
13、= 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
14、; 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; /* 计算 follow集, 例： U-xVy,U-xV.(注：初始符必含# “-1“)*/ void Follow(int V) int i; struct pRNode *pt; if(100 = V)/* 当为初始符时*/ AddFoll
15、ow(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 AddFollow(V, Pi.lCursor, 0); else/* 不为空时V-xVy,( 注意： y-) ，调用 AddFollow 加入 Vt 或 y 的 first集
16、*/ while(NULL != pt /*y 的前缀中有空时，加如first集*/ pt = pt-next; if(NULL = pt)/* 当后面的字符可以推出空时*/ if(NULL = followPi.lCursor - 100 AddFollow(V, Pi.lCursor, 0); else/* 发现不为空的字符时*/ AddFollow(V, pt-rCursor, 1); /* 当数值小于100 时 nCh为 Vt*/ /*# 用-1 表示 ,kind用于区分是并入符号的first集，还是follow集 kind = 0表加入 follow集， kind = 1加入 fir
17、st集*/ void AddFollow(int V, int nCh, int kind) 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 = followV - 100)
18、 followV - 100 = pt; else qt-next = pt;/*qt指向 follow集的最后一个元素*/ pt = pt-next; else/* 为非终结符时，要区分是加first还是 follow*/ 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,
19、 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“); /*
20、 计算 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() int i; struct pRNode *pt; struct collectNode *ct; for(i = 0; i rCursor) /* 处理非终结符，当为终结符时，定
21、含空为假跳出*/ 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 != ct) if(-1 != ct-nVt) analyseTablePi.lCursor - 100ct-nVt = i; else
22、/* 当含有 #号时 */ 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)/*-1为空产生式时*/ ct = followPi.lCursor - 100; while(NULL != ct) if(-
23、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; 1printf(“构造预测分析表如下：n“); printf(“t|t“); for(i = 0; i analyseStacktopAnalyse)/* 当为终结
24、符时*/ if(analyseStacktopAnalyse = IndexCh(stcurrent) /* 匹配出栈，指示器后移*/ Pop(); current+; step+; printf(“%dt“, step); ShowStack(); printf(“tt%ctt出栈、后移 n“, stcurrent); else printf(“%c-%c不匹配！ “, analyseStacktopAnalyse, stcurrent); printf(“此串不是此文法的句子！n“); return; else/* 当为非终结符时*/ r = analyseTableanalyseStac
25、ktopAnalyse - 100IndexCh(stcurrent); if(-1 != r) Push(r);/* 产生式右部代替左部，指示器不移动*/ step+; printf(“%dt“, step); ShowStack(); printf(“tt%ctt%dn“, stcurrent, r); else printf(“无可用产生式，此串不是此文法的句子！n“); return; if(# = stcurrent) 5if(0 = topAnalyse printf(“%dt“, step); ShowStack(); printf(“tt%ctt分析成功！ n“, stcurr
26、ent); printf(“%s是给定文法的句子！n“, st); else while(topAnalyse 0) if(100 analyseStacktopAnalyse)/* 当为终结符时*/ printf(“无可用产生式，此串不是此文法的句子！n“); return; else r = analyseTableanalyseStacktopAnalyse - 100vtNum; if(-1 != r) Push(r);/* 产生式右部代替左部，指示器不移动*/ step+; printf(“%dt“, step); ShowStack(); if(0 = topAnalyse pri
27、ntf(“%s是给定文法的句子！n“, st); else printf(“tt%ctt%dn“, stcurrent, r); else printf(“无可用产生式，此串不是此文法的句子！n“); return; /* 初始化栈及符号串*/ void InitStack() int i; /* 分析栈的初始化*/ for(i = 0; i rCursor)/* 为空产生式时*/ return; topAnalyse += Pr.rLength; for(i = 0; i rCursor;/*逆序入栈 */ pt = pt-next; /* 循环未完时pt 为空，则说明rLength记录等出错 */ 四. 实验结果 五. 实验总结 通过这次的实验，我深入了解了词法分析器和LL(1) 文法预测分析法设计和实现，增强了我 的自学能力和独立思考能力，也让我对程序设计有了更大的兴趣，自己通过查找资料、复习 课本、 编程调试，写实验报告等环节，进一步掌握了以前学到的知识，并且还对编译原理应 用有了更深入的认识与掌握。在完成这个程序后，真的很开心， 也了使我解到编译原理的魅 力所在，激发了我要解决更多更难问题的决心。