资源描述：
《实验3预测分析法.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、精品资料一、分析语法分析部分我们我们采用LL(1)方法实现，采用LL(1)方法实现语法发分析要求文法满足以下要求：一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当有右部能=*=>&时则与其左部非终结符的后跟符号集合也有关，此外在产生式中不存在左递归，无回溯。它的基本思想是从左到右扫描源程序，同时从识别符号开始生成句子的最左推导，并只向前查看一个输入符号，便能唯一确定应选择的规则。下面将确切地定义满足确定的自顶向下分析条件的文法即LL(1)文法及LL(1)文法的判别并介绍如何对非LL(1)文法进行等价变换问题，也就是消除一个文法中的左递归和左
2、公共因子。一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。LL(1)文法的定义(5种定义)：一个文法符号串的开始符号集合定义如下：定义1.设G=(VT,VN,S,P)是上下文无关文法，a是任意的文法符号串，FIRST(a)是从a推导出的串的开始符号的终结符集合。。。。FIRST(%)={a
3、a=*=>aB,a€VT,a,B€V
4、*}若a=*=>e,贝U规定FIRST(a).当一个文法中相同左部非终结符的右部存在能=*=>e的情况则必须知道该非终结符的后跟符号的集合中是否含有其它右部开始符号集合的元素。为此，我们定义一个文法非终结符的后跟符号的集合如下：定义2.设G=(VT,VN,S,P)是上下文无关文法，A€VN,S是开始符号FOLLOW(A)={a
5、S=*=>吩3,且a€VT,a€FIRST(3),y€VT*,^€V+}若S=*=>pA3,且3e则#€FOLLOW(A)。也可定义为：FOLLOW(A)={a
6、S=*=>…Aa…,a€VT}若有S=*=>…A，则规定#€FOLLOW(A)这里我们用'#
7、'作为输入串的结束符，或称为句子括号，如：#输入串#。定义3.给定上下文无关文法的产生式AF,A€VN,a€V*,若a==>e,则SELECT(A~a)=FIRST(%)如果a=*=>e则SELECT(A~a)=FIRST(a>UFOLLOW(A)°FIRST(a)表示FIRST(a)的非打元素。更进一步可以看出能够使用自顶向下分析技术必须使文法满足如下条件，我们称满足条件的文法为LL(1)文法，其定义为：定义4.一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A~a,A~3,满足SELECT(A~a)ASELECT(A~3)=空,其中a,
8、3不同时能e.定义5.LL(1)文法也可定义为:一个文法G是LL(1)的，当且仅当对于G的每一个非终结符A的任何两个不同产生式A^a
9、3,下面的条件成立：⑴FIRST(a)AFIRST(3)=空,也就是a和3推导不出以某个相同的终结符a为首的符可编辑修改精品资料号串；它们不应该都能推出空字一⑵假若3=>£那么，FIRST(a)nFOLLOW(A)=空也就是，若B=>£则％所能推出的串的首符号不应在FOLLOW(A)中。、算法1T:判断句型1■r是LL(1)文法?结束该程序可分为如下几步：(1)(2)(3)(4)根据下面读入文法判断正误若无误，判断是否为LL(1)文法报错若是，构
10、造分析表；LL(1)文法，对输入串w:(i+i)*(i+i)+i*i进行LL(1)分析，要求如下1、先手工建立LL(1)分析表；2、分析输入串，判断是否是语法上正确的句子，并输出整个分析过程。LL(1)文法G为：EETT't*FT'
11、£Ft(E)
12、id分析算法：输入：串w和文法G的分析表M。输出：如果W属于L(G),则输出W的最左推导，否则报告错误。方法：开始时，#S在分析栈中，其中S是文法的开始符号，在栈顶；令指针ip指向W#的第一个符号；repeat让X等于栈顶符号，a为ip所指向的符号ifX是终结符号或#thenIfX=athen把X从栈顶弹出并使ip指向下一个输入符号e
13、lseerror()else/*X是非终结符号*/ifM[x,a]=Xdy1y2…ykthenbegin从栈中弹出X;把yk,yk-1,…,y1压入栈，y1在栈顶；输出产生式Xdy1y2…yk；endelseerror()untilX=#/*栈空*/可编辑修改精品资料语法分析的流程算法三、设计目的:(1)理解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析表的构造及分析过程的实现。(2)掌握预测分析程序如何使用分析表和栈联合控制实现LL(1)分析。四、实现
