1、的分析器由一张的分析器由一张(LL(1)(LL(1)分析表分析表),),一个一个(表驱动程表驱动程序序)及一及一组成组成控制程序分析表分析表XYZ#分析栈a1 a2 ai an#输入 输入是待分析的符号串（输入是待分析的符号串（），以），以结尾。结尾。分析表是一二维数组，分析表是一二维数组，M:VN(VT#)(P ERR),MA,a的值按下述规则确的值按下述规则确定定:对于每个产生式对于每个产生式A1|2|m(1)若若a FIRST(i),则置则置MA,a=“Ai”;(2)FIRST(i),a FOLLOW(A),置置MA.a=“Ai”,(3)除上述两种情况外除上述两种情况外,其它元素均填其它
2、元素均填“ERR”.分析表元素的含义分析表元素的含义:指明当前应用何产生式进行推导指明当前应用何产生式进行推导,或指明输入串出现错误或指明输入串出现错误考虑如下（例如文法考虑如下（例如文法1）|iA|对于对于G G中的每个文法符号中的每个文法符号X X,为求为求FIRST(X),FIRST(X),反复应用如下规则反复应用如下规则,直到集合不再增大直到集合不再增大:(1)(1)if (if ()FIRST(X)=X;)FIRST(X)=X;(2)if(2)if()if(X)if(Xa aP P a a V VT T)a)aFIRST(X);FIRST(X);if(X if(XP)P)FIRST(
3、X);FIRST(X);(3)if(3)if()if(Y)if(Y V VN N)FIRST(Y)FIRST(Y)-)-FIRST(X);FIRST(X);for(1for(1 j j k-1)if(Y k-1)if(Yj j V VN NFIRST(YFIRST(Y)FIRST(Y)FIRST(Yj j)-)-FIRST(X);FIRST(X);if(for(1 if(for(1 j j k):k):FIRST(Y FIRST(Yj j)FIRST(X);FIRST(X);V V*,=X=X1 1X X2 2X Xn n,求求FIRST(FIRST()类似于求类似于求X XY Y1 1Y Y
4、2 2Y Yk k,略略.,反复使用如下规则,直到不再增大:算法的证明:对于1.,由定义直接得到;对于2.,由于A是有用符号,则必存在含A的句型:S S*A A B B BaBa (a (a FIRST(FIRST(););对于3.,类似地,S S*A A BB ,显然,FIRST(FIRST()FOLLOW(A),FOLLOW(A),并且,FIRST(FIRST()FOLLOW(B).FOLLOW(B).证毕我们以我们以 (文法文法1 1)为例为例,计算相应的计算相应的集和集和集集.1.求所有符的集.利用规则规则(2),有 FIRST()=,FIRST()=FIRST()=;再利用规则规则(
5、3),有FIRST()=FIRST()=,FIRST()=FIRST()=,FIRST()=FIRST()=FIRST()=FIRST()=2.求集(1)由规则规则(1),#FOLLOW(),再由产生式 FOLLOW(),从而,FOLLOW()=(2)由规则规则(3)及产生式可知FOLLOW()FOLLOW(),即有 FOLLOW(E)=(3)(3)由由规则规则(2)(2)及产生式及产生式有有 再由再由规则规则(3)(3)及及和和有有 FOLLOW(FOLLOW()FOLLOW(FOLLOW()即即FOLLOW(FOLLOW()=)=(4)(4)由由规则规则(3)(3)有有有有FOLLOW(F
6、OLLOW()FOLLOW(FOLLOW(),即即FOLLOW(FOLLOW()=)=(5)(5)由由规则规则(2)(2)及及,有有 FIRST(FIRST()-)-FOLLOW(FOLLOW(),再由再由规则规则(3)(3)及及和和,有有FOLLOW(FOLLOW()FOLLOW(FOLLOW(),从而从而,FOLLOW(FOLLOW()=)=(6)(6)由由规则规则(2)(2)及及,有有 FIRST(FIRST()FOLLOW(FOLLOW(),FIRST(),FIRST()FOLLOW(FOLLOW(),),故有故有 FOLLOW(FOLLOW()=)=,FOLLOW(,FOLLOW()
7、=)=.产生式产生式FIRSTFIRSTFOLLOWFOLLOW1.1.E ETETE(,(,i i ),#),#2.2.E EATEATE +,-+,-),#),#3.3.T TFTFT(,(,i i +,-,),#+,-,),#4.4.T TMFTMFT *,/*,/+,-,),#+,-,),#5.5.F F(E)(E)i i(i i +,-,*,/,),+,-,*,/,),#6.6.A A+-+-(,(,i i 7.7.M M*/*/(,(,i i 对已给的LL(1)文法,在得到各文法符号的集和集之后,就可容易地构造出(也称).在实际的表存储结构中,矩阵中每个元素并非真正存储的是产生式产
8、生式,而是其右部的逆序右部的逆序(也可以是产生式序号序号),这样便于分析时使用,并节省了内存空间.在A VN所在行,a VT所在列,MA,a的填写方法如下:(1)if(AP and a FIRST()MA,a=A;(2)if(*(FIRST()and a FOLLOW(A)MA,a=A;(3)Otherwise,MA,a=ERR.i+-*/()#EETEETEEA ATEA ATETFTFTFTFTTMFTMFTFi(E)A+-M*/分析器对输入串的分析在控制程序的控制下进行，步骤如下：#Sa1 a2 an#2.设在分析的某时刻设在分析的某时刻,的分析格局为的分析格局为#X1 X2 Xm-1
9、Xmai ai+1 an#c此时此时,根据当前栈顶符号根据当前栈顶符号Xm的不同情况的不同情况,分别作如下处理分别作如下处理:(1)Xm VT,且且Xm=ai,则匹配则匹配,将将Xm 顶出栈顶出栈,输入指针输入指针+;否则否则(Xm ai),出错出错;(2)Xm VN 查表查表MXm,ai,若若MXm,ai=“ERR”,则出错则出错;若若MXm,ai=“Xm Y1Y2Yk”,则将则将Xm 出栈出栈,Y1Y2Yk 按逆序压入栈按逆序压入栈,得到格局得到格局1.初始化初始化.首先将首先将#及开始符及开始符S压入栈压入栈,各各指针置初值指针置初值.此时此时,格局为格局为#X1 X2 Xm-1YkYk
10、-1.Y1ai ai+1 an#(3)若若则表明输入串已完全得到匹配则表明输入串已完全得到匹配,结束结束.步步骤骤分分析析栈栈余余留留输输入入串串所所用用产产生生式式1.#Ei+i*i#E TE2.#E Ti+i*i#T F FT3.#E T Fi+i*i#F F i4.#ETii+i*i#5.#ET+i*i#T 6.#E+i*i#E A ATE7.#ET A+i*i#A +8.#ET+i*i#9.#ETi*i#T F FT10.#ETFi*i#F i i11.#ETii*i#12.#ET*i#T M MF FT13.#ETF M*i#M M*14.#ETF*i#15.#ETFi#F i i1
11、6.#ETii#17.#ET#T 18.#E#E 19.#E#成成功功对于对于LL(1)LL(1)文法而言文法而言,我们总能构造出相应的预测分析表我们总能构造出相应的预测分析表,且表中决不会且表中决不会含有多重定义的元素含有多重定义的元素.然而对于然而对于非非LL(1)LL(1)文法文法,它们不满足它们不满足LL(1)LL(1)文法文法的条件的条件,尽管仍可为其建尽管仍可为其建立预测分析表立预测分析表,但表中必然会出现但表中必然会出现多重定义多重定义的的元素元素(why?(why?)例如例如,文法文法GS:SabB ASC|BAA|BAbA CB|.可见可见非非LL(1)LL(1)文法文法所造
12、之表中所造之表中,必有冲突元素必有冲突元素.事实上事实上,是否有冲突元素是否有冲突元素也是判别一文法是否是也是判别一文法是否是LL(1)LL(1)文法文法的方法之一的方法之一.对于某些对于某些非非LL(1)LL(1)文法文法而言而言,通过通过,反复反复等方法等方法,有时是可以将其改造成有时是可以将其改造成的的.当文法中含有形如 A1|2|m 的产生式时,可将其改写为:AAA1|2|m 若诸候选式1,2,m 中的一部分仍含有左因子,则再进行提取工作,如此等等.这样,就可能可能得到一个LL(1)文法.例如,EE+T|TT(E)|a(E)|a经改造后可得文法ETE E+TE|TaT|(E)T(E)|
13、这是一个LL(1)文法.应当指出,并非并非所有的文法都能改造为LL(1)文法.例如,文法GS:SAU|BRAaAU|bBaBR|bUcRd 文法中S的两个候选式AU及BR的FIRST集相交,G是非LL(1)的.为提取左因子,先将S产生式中的A,B用其右部替换,得:SaAUU|bU|aBRR|bR,经提取左因子,得 显然它仍不是LL(1)文法 能由LL(1)文法产生的语言称为LL(1)语言.它们已被证明具有许多重要特性,主要有:(1)任何任何LL(1)文法都是文法都是;(2)是非是非LL(1)的的;(3)存在一种算法存在一种算法,它能它能LL(1);(4)存在一种算法存在一种算法,它能它能LL(1);(5)是否是是否是LL(1)语言是语言是的的;(6)非非LL(1)语言是语言是存在存在的的.若在分析过程中,每步向前扫描k个符号来确定选用的产生式,此分析方法称为是LL(k)分析.此法极少用,故从略.
