编译技术课程设计报告模板静.docx
编译技术课程设计班 级 网络1102 学 号 3110610035 姓 名 徐静 指导老师 年轶 2014年6 月目 录一、目的2二、题目2三、要求2四、实验环境2五、系统实现2六、程序运行结果3七、总结3一、目的通过编译原理课程设计进一步理解高级语言在计算机中的执行过程，加深对编译原理中重点算法和编译技术的理解，掌握词法分析、语法分析、语义分析、代码生成和报错处理等理论与实践的结合，提高自己的编程能力，培养好的程序设计风格。同时通过某种可视化编程语言的应用，具备初步的Windows环境下的编程思想。二、题目输入文法，自动生成分析表，并完成语法分析工作三、要求题目3 文法编译器的自动生成器输入文法，自动生成分析表，并完成语法分析工作。语法分析方法可以是：LL（1）分析法或LR分析法。为文法构造分析表，并对输入串进行语法分析，判别是否符合语法规则，如果不符合，则输出错误信息。输入：文法，文法符号串输出：分析表、分析栈、分析结果四、实验环境开发环境Visual Studio6.0语言C+五、系统实现1.分析方法说明所谓LL(1)分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL(1)分析的程序又称为LL(1)分析程序或LL(1)分析器。我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL(1)分析表，最后利用分析表，根据LL（1）语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控制程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C+语言来编写。2.分析表的构造算法在构造LL(1)预测分析表之前，首先要构造该文法的每个非终结符的FIRST和FOLLOW集合，按照下面描述的算法来构造这两个集合。 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)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j=1,2,，k，则把加到FIRST(X)中。 连续使用上面的规则，直至每个集合FIRST不再增大为止。 FOLLOW集合的构造算法： （1）对于文法的开始符号S，置#于FOLLOW(S)中； （2）若AB是一个产生式，则把FIRST()| 加至FOLLOW(B)中； （3）若AB是一个产生式，或AB是一个产生式而Þ（即FIRST()），则把FOLLOW(A)加至FOLLOW(B)中。 连续使用上面的规则，直至每个集合FOLLOW不再增大为止3.数据结构变量定义： struct pRNode /*产生式右部结构*/ struct pNode struct collectNode struct collectNode* firstMaxVnNum + 1; /*first集*/ struct collectNode* followMaxVnNum + 1; /*follow集*/ char VnMaxVnNum + 1; /*非终结符集*/ int vnNum; char VtMaxVtNum + 1; /*终结符集*/ int vtNum; struct pNode PMaxRuleNum; int PNum; char bufferMaxPLength + 1; char stMaxStLength; /*要分析的符号串*/ int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1; int analyseStackMaxStackDepth + 1; /*分析栈*/ int topAnalyse; /*分析栈顶*/ 类关系图： LL(1)分析过程主要包括以下四个动作：替换：当XÎVN时选相应产生式的右部b去替换X。此时X出栈，b逆序入栈。匹配：当XÎVT时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。接受：当格局为（#，空#）时报告分析成功。报错：出错后，停止分析。并给出相应的错误提示信息。驱动程序框图如下：4.函数说明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);其中部分函数的具体实现：void First(int U) /构造first集合 int i,j; for(i = 0; i < PNum; i+) if(Pi.lCursor = U) struct pRNode* pt; pt = Pi.rHead; j = 0; while(j < Pi.rLength) if(100 > 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); void Follow(int V) /构造follow集合 int i; struct pRNode *pt ; if(100 = V) /*当为初始符时*/ AddFollow(V, -1, 0 ); for(i = 0; i < PNum; i+) pt = Pi.rHead; while(NULL != pt && pt->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 CreateAT() /构造LL（1）分析表 int i; struct pRNode *pt; struct collectNode *ct; for(i = 0; i < PNum; i+) pt = Pi.rHead; while(NULL != pt && HaveEmpty(pt->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 <= pt->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; 六、程序运行结果七、总结编译是把高级语言翻译成与之等价的低级语言的过程,它包括词法分析,语法分析,语义分析和中间代码生成,优化阶段和目标代码生成。此次课设本来是有三个题目，然后第一个题目中有词法分析和语法分析等过程，与之前做实验有些许关联，所以选择了第三个题目，也算是对自己能力的挑战。很多代码借鉴了同学的实验，然后自己在在原来的基础上稍加了修改，原本对C+的掌握也不怎么好，大致的读懂了程序，然后进行了多次运行。而同时自己对于LL(1)文法有了进一步的了解，对于文法的判定，二义性的消除等，在老师和同学的帮助下有了深刻的理解，以及对于FIRST集和FOLLOW集的判定等也有了长足的进步。对于自己以后其他的学习有很大的帮助，也使得自己对自己的专业知识技能有了多的掌握。这次课设培养了自己的耐性，是自己能够静下心来去研究程序，对自己以后走上工作岗位，能够虚心学习有深刻的影响。也是自我提高的过程，比如对于编译的过程有了深刻的理解，对于文法的判定以及使用也能够熟练的进行。自己能够不再拘泥于书本上的知识，对于实际的操作动手能力有了明显的提高，对以后的生活受益匪浅。最后很感谢老师对自己的帮助，希望老师能够万事如意！第13页
