资源描述：
《LL1文法分析的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、•.需求分析4.问题的提出:语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的-个问题。2.问题解决：其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而卞的分析法，一类
2、是自卞而上的分析法。自上而下的主旨是，对任何输入串，试图用-•切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者•说，为输入串寻找一个最左推倒，这种分析过程的木质是种试探过程，是反复使川不同产生式谋求匹配输入串的过程我主要是自上而下的过程。3.解决步骤：在用上而下的分析法屮，主要是研究LL⑴分析法。它的解决步骤是首先接收到用户输入的一个文法,对文法进行检测和处理，消除左递归，得到LL(1)文法,这个文法应该满足:无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRS
3、T和FOLLOW集合然后根据FIRST和FOLLOW集合构适LL(1)分析表，最后利用分析表，根据LL⑴语法分析构造一个分析器。LL(1)的语法分析程序包含了三个部分，总控程序，预测分析表两数，先进先出的语法分析栈。二概要设计1.设计原理：所谓LL(1)分析法，就是指从左到右扌描输入串(源程序)，同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL(1)分析的程序乂称为LL(1)分析程序或LL1(1)分析器。我们知道一个文法要能进行LL(1)分析，那么这个文法应该满足：无二义
4、性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL(1)分析表，最后利用分析表，根据LL⑴语法分析构造一个分析器。LL(1)的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，木程序也是采用了同样的方法进行语法分析，该程序是采用了C++语言來编写，其逻辑结构图如下：LL(1)预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何(X,a)，总控程序每次都执
5、行下述三种可能的动作之一：(1)若X=a=4#',则宣布分析成功，停止分析过程。(2)若X二a#,则把X从STACK栈顶弹出,让a指向下一个输入符号。(3)若X是一个非终结符，则査看预测分析农若M[A,a]中存放着关于X的一个产生式，那么，首先把X弹II1,STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈(若右部符号为£,则不推什么东西进STACK栈)。若M[A,a]屮存放看“出错标志”，则调用出错诊断程序ERROR。事实上，LL(1)的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，
6、因此在LL(1)分析器中，实际上是以LL(1)分析表代替相应方法来进行分析的。1.构造LL(1)分析表考查文法G［E］：E-E+T
7、TT->T*F
8、FF->(E)
9、i
10、x
11、y我们容易看出此文法没冇左公因子也没冇二义性，但却存在两个直接左递归，这里我们利用引入新非终结符的方法來消除它使方法满足要求，即：对形如：U-Ux
12、y的产生式(其中x,yV+,y不以U开头)，引入一个新的非终结符U'后，可以等价地改写成为：U—yU，UJxU'
13、£显然改吗后，U和U'都不是左递归的非终结符。因此文法GEE］按上述方法消去左递归后可等价
14、地写成：E->TPPt+TP
15、£T->FQQ->*FQ
16、£F->(E)
17、i
18、x
19、y在构造LL(1)预测分析农之前，首先要构造该文法的每个非终结符的FIRST和FOLLOW集合，按照下面描述的算法來构造这两个集合。®FIRST集合的构造算法：(1)若XUVT,贝ijFIRST(X)={X}C(2)若XeVN,且有产生式X->8……，则把a加入到FIRST(X)中；若Xt£也是一条产生式，则把£也加到FIRST(X)中。(3)若XtY……是一个产生式且YeVN,则把FIRST(Y)中的所有非&元素都加到FIRST(X)中;
20、若X->Y1Y2...Yk是一个产生式,Y1,Yi・1都是非终结符,而且，对于任何j,1则把FIRST(丫j)中的所有非£•元素都加到FIRST(X)电特别是若所冇的FIRST(Yj)均含有£,j=1,2,...,k,则把£加到FIRST(X)中。连续使用上面的规
