编译原理LL1文法源代码实验三

《编译原理LL1文法源代码实验三》由会员分享，可在线阅读，更多相关《编译原理LL1文法源代码实验三（29页珍藏版）》请在装配图网上搜索。

1、一、实验目的及要求1掌握LL(1)分析法的基本原理； 2掌握LL(1)分析表的构造方法；3用LL（1）分析法分析高级语言表达式。4、了解LL（1）分析器的工作过程。文法：无二义性的算术表达式的文法（1）把词法分析作为语法分析的子程序实现（5分）（2）独立的语法分析程序（4分）（3）对表达式文法消除左递归、构造LL（1）分析表（4）LL（1）分析表可以直接输入（4分），也可以用程序实现（5分）（5）给一个表达式，给出分析过程（分析栈、输入串、所用规则）（4分）（6）生成一个棵语法树（5分）用二叉树的形式表示出来二、 实验内容及原理 1、 实验原理（1）、LL（1）文法的定义LL(1)分析法属于确

2、定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1)分析方法要求文法满足如下条件：对于任

3、一非终极符A的两个不同产生式Aa,Ab，都要满足下面条件：SELECT(Aa)SELECT(Ab)=（2）、预测分析表构造LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。若用M表示LL(1)分析表，则M可表示如下：M: VNVTPErrorM(A, t) = A，当tselect(A) ，否则M(A, t) = Error其中P表示所有产生式的集合。（3）、语法分析程序构造LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号，#为句子括

4、号即输入串的括号。分析表用一个二位数组M表示，数组元素MA，a中的下标A表示非终结符，a为终结符或句子括号#，二维数组中存放的是一条关于A 的产生式，表明当非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，则表明用A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。LL(1)分析过程主要包括以下四个动作：替换：当XVN时选相应产生式的右部b去替换X。此时X出栈，b逆序入栈。匹配：当XVT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。接受：当格局为（#，空#）时报告分析成功。报错：

5、出错后，停止分析。并给出相应的错误提示信息。2、实验内容根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。 对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E-TG（2）G-+TG（3）G-（4）T-FS（5）S-*FS（6）S-（7）F-(E)（8）F-i程序输入一以#结束的符号串(包括+*（）i#)，如：i+i*i#。三、 实验过程及步骤1. 总体思路分析及流程图给定一个正规文法G，在LL(1)预测分析中，必须先求出First集和Follow集， 构造预测分析表。求出预测分析表之后，再输入一个字

6、符串，依据LL1分析表单步输出字符串的分析过程。功能模块分解图（1）主程序流程图（2）核心算法流程图 1.计算非终结符的First集的算法及流程：First集合的构造算法：（1）若XVT，则First（X）=X。（2）若XVN，且有产生式Xa，则把a加入到First (X)中；若X也是一条产生式，则把也加到First (X)中。（3）若XY是一个产生式且YVN，则把First (Y)中的所有非-元素都加到First (X)中；若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，First (Yj)都含有（即Y1Yi-1* ），则把First (Yj)中的所有

7、非-元素都加到First (X)中；特别是，若所有的First (Yj)均含有，j=1,2,，k，则把加到First (X)中。连续使用上面的规则，直至每个集合First不再增大为止。2.计算非终结符的Follow集：Follow集合的具体构造算法如下：（1）对于文法的开始符号S，置#于Follow(S)中；（2）若AB是一个产生式，则把First()|加至Follow(B)中；（3）若AB是一个产生式，或AB是一个产生式而 （即First()），则把Follow(A)加至Follow(B)中。连续使用上面的规则，直至每个集合Follow不再增大为止。3.预测分析控制程序的算法流程 LL（1）

8、文法（源代码）#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; /*右部结点头指

9、针*/;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 collec

10、tNode* 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 I

11、nputP();/*产生式输入*/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();/*计算f

12、irst和follow*/void CreateAT();/*构造预测分析表*/void ShowAT();/*输出分析表*/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

13、集为：); 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

14、) 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

15、 = 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 &

16、 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; wh

17、ile(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 = getcha

18、r() 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 inE

19、rr = 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() whil

20、e(# != (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(请输入文法产生式的

21、个数：); 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 = p

22、t; 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;

23、 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)

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

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

26、(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

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

28、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) fol

29、lowV - 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

30、集*/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;

31、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.lCurso

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

33、t) 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.lCurs

34、or - 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

35、) 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 = analyseTableanalyseStacktopAnalyse - 100IndexCh(stcu

36、rrent); if(-1 != r) Push(r); step+; printf(%dt, step); ShowStack(); printf(tt%ctt%dn, stcurrent, r); else printf(此串不是此文法的句子！n); return; if(# = stcurrent) if(0 = topAnalyse & # = stcurrent) step+; printf(%dt, step); ShowStack(); printf(tt%ctt分析成功！n, stcurrent); printf(%s是给定文法的句子！n, st); else while(to

37、pAnalyse 0) if(100 analyseStacktopAnalyse) printf(此串不是此文法的句子！n); return; else r = analyseTableanalyseStacktopAnalyse - 100vtNum; if(-1 != r) Push(r); /*产生式右部代替左部，指示器不移动*/ step+; printf(%dt, step); ShowStack(); if(0 = topAnalyse & # = stcurrent) printf(tt%ctt分析成功！n, stcurrent); printf(%s是给定文法的句子！n, s

38、t); else printf(tt%ctt%dn, stcurrent, r); else printf(此串不是此文法的句子！n); return; /*初始化栈及符号串*/void InitStack() int i; /*分析栈的初始化*/ for(i = 0; i MaxStLength; i+) sti = 0; analyseStack0 = -1; /*#(-1)入栈*/ analyseStack1 = 100; /*初始符入栈*/ topAnalyse = 1;/*显示符号栈中内容*/void ShowStack() int i; for(i = 0; i = topAnalyse; i+) if(100 rCursor) return; topAnalyse += Pr.rLength; for(i = 0; i rCursor;/*逆序入栈*/ pt = pt-next;