信安1202-汪澄-1121290213.docx

课程设计报告 ( 2013--2014年度第一学期)名 称： 编译技术课程设计 题 目： LL(1)文法和预测分析方法 院 系： 控制制与计算机工程学院 班 级： 信安1202班 学 号： 1121290213 学生姓名： 汪澄 指导教师： 徐欢 设计周数： 一周 成 绩： 日期：2015年 1 月13日1 课程设计的目的和要求1.1 课程设计的目的本次设计的时间为1周，目的是通过使用高级语言实现部分算法加强对编译技术和理论的理解。本次课程设计主要是介绍LL(1)文法的一般原理，根据给定的一文法编制调试LL(1)文法语法分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析的理解。更加深刻的理解LL(1)文法的基本思想和文法的判别。通过用高级语言编程实现对LL(1)文法从理论到实践的认知，最终能够对LL(1)文法有高度清晰化和全面透彻化的理解。 1.2 课程设计的要求LL(1)文法使用的是确定的自顶向下的分析技术。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。因此为了达到对文法的理解水平，此次课程设计必须实现以下功能：LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。文法使用产生式来定义；分别求出文法中每一个非终结符的FIRST 集、FOLLOW集和SELECT集；画出预测分析表；判定给定的文法是否是LL(1)文法；给定符号串判定是否是文法中的句子，分析过程用分析表格的方式打印出来。同时要求界面简洁，美观，大方，能够友好化的展示程序所实现的功能。所以，在有效的时间内必须保质保量地完成课程设计的所有要求。2 系统描述本次课程设计要求编写一个程序，用来计算给定文法的全部FIRST集及FOLLOW集，并判定所给文法是否LL(1)文法。首先要面临一个问题就是本次程序具体实现的是一个内部给定的正确文法，其次是依次计算FIRST集、FOLLOW集和SELLECT集，然后判断是否为LL(1)文法,最后再进行句子分析。终结符，非终结符，FIRST集，FOLLOW集，SELLECT集和LL(1)分析表对于课程设计LL(1)问题的解决是特别的重要，计算出FIRST集、FOLLOW集和SELLECT集后，后面LL(1)分析表的构造以及判断文法是否为LL(1)文法就会变得容易。在程序的实现中，需要对每一个功能作出具体的展示，整个系统将会对LL(1)文法的定义，判别，和句子的分析做全面的实现。所以对LL(1)的重要环节和概念做出细致的描述：FIRST集的确定FIRST集使用以下四个步骤判定：(1)、若X∈VT?,则FIRST(X)={X}(2)、若X∈VN,且有产生式X→a…，a∈VT 则把a加入到FIRST(X)中，即a∈FIRST(X)(3)、若X∈VN,且有产生式X→ε， 则把$也加到FIRST(X)中，即$∈FIRST(X)(4)、若X∈VN, Y1，Y2，…，Yi 都∈VN，且有产生式X→Y1Y2…Yn。 当Y1，..Yi-1=>ε(1≤i≤n)，则FIRST(Y1)-{ε}，…，FIRST(Yi-1)- {ε}，FIRST(Yi)都包含在FIRST(X)中，即： FIRST(Yi-1)-{ε} ∈FIRST(X)所有Y1,…Yn *=>ε，则把ε加到FIRST(X)中,即： FIRST(Yi) ∈FIRST(X)其中第1-3个方法都很好处理，关键是第四个方法判断时首先判断第一个字符为非终结符，设定一个布尔型扫描标志FLAG，赋初值TRUE，接下去依次扫描产生式右部每一个字符Yi，假如第i个字符可以推出空，那么就把这个字符的FIRST集去除$加入到产生式左部字符的FIRST集中，即FIRST(Yi)-{$}FIRST(X),假如Yi是终结符或者不可以推出$，那么就把这个字符的FIRST集直接加入到FIRST(X)中，即FIRST(Yi)FIRST(X)同时置FLAG为FALSE不再向下扫描，假如Yi恰好是最后一个字符，那么不管它能不能星推导出空都直接把它的FIRST集加入到FIRST(X)中。同时要设置一个队列和一组布尔型变量记录FIRST集是否完成，队列用来记录FIRST(X)用到了哪些其它非终结符的FIRST集。第一遍扫描完成后就扫描队列，把FIRST集完成的非终结符的FIRST集加入到那些没有完成的非终结符的FIRST集中去，没有完成的非终结符再送回到队列，这时候可能出现死循环，比如FIRST(S)用到了FIRST(A),而FIRST(A)用到了FIRST(B)，