LL分析法 LL分析法的分析器由一张预测分析表(LL(1)分析表),一个控制程序(表驱动程序)及一分析栈组成 输入

Presentation on theme: "LL分析法 LL分析法的分析器由一张预测分析表(LL(1)分析表),一个控制程序(表驱动程序)及一分析栈组成 输入"— Presentation transcript:

1 LL分析法 LL分析法的分析器由一张预测分析表(LL(1)分析表),一个控制程序(表驱动程序)及一分析栈组成 输入
X Y Z # 分 析 栈 a1 a2 … ai … an # 输入 输入是待分析的符号串（单词流），以# 结尾。 分析表是一二维数组，M:VN(VT{#}) (P{ERR}), M[A,a]的值按下述规则确定:对于每个产生式A1|2|…|m (1)若aFIRST(i), 则置M[A,a]=“Ai”; (2)FIRST(i), aFOLLOW(A), 置M[A.a]=“Ai”, (3)除上述两种情况外,其它元素均填“ERR”. 分析表元素的含义:指明当前应用何产生式进行推导,或指明输入串出现错误

2 LL分析法实例 考虑如下（例如文法1） E T E’ E’ATE’ |  T FT ’ T’ MFT’ | 
F (E) | i A + | - M * | /

3 －、构造FIRST集的算法 对于G中的每个文法符号X,为求FIRST(X),反复应用如下规则,直到集合不再增大:
(1) if (XVT) { FIRST(X)={X};} (2)if (XVN) { if(XaP  aVT) aFIRST(X); if (XP) {FIRST(X);} } (3) if (XY1Y2…YkP) {if (Y1VN) {FIRST(Y1)-{} FIRST(X);} for(1 j k-1)if (YjVNFIRST(Yj)){FIRST(Yj)-{}FIRST(X);} if (for(1 j k):  FIRST(Yj)) {FIRST(X);} V*,=X1X2…Xn,求FIRST()类似于求XY1Y2…Yk,略.

4 构造FOLLOW集的算法 FOLLOW: VNVT{#},反复使用如下规则,直到不再增大: 1. # FOLLOW(S);
2. if (ABP) {FIRST()-{}FOLLOW(B);} 3. if ( (ABP)  ( AB  FIRST() ) ) {FOLLOW(A)FOLLOW(B);} 算法的证明: 对于1.,由定义直接得到; 对于2.,由于A是有用符号,则必存在含A的句型: S * A  B  Ba (a FIRST()); 对于3., 类似地, S * A  B[],显然, FIRST()FOLLOW(A),并且, FIRST()FOLLOW(B).证毕//

5 构造FIRST集和FOLLOW集的例子 我们以 (文法1)为例,计算相应的FIRST集和FOLLOW集.
1.求所有VN符的FIRST集.利用规则(2),有 FIRST(M)={*,/}, FIRST(A)={+,-} FIRST(F)={(,i}; 再利用规则(3),有FIRST(T’)=FIRST(M){}={*,/, }, FIRST(T)=FIRST(F)={(,i}, FIRST(E’)=FIRST(A) {}={+,-,} FIRST(E)=FIRST(T)={(,i} 2.求FOLLOW集 (1)由规则(1),#FOLLOW(E),再由产生式F(E), ) FOLLOW(E), 从而,FOLLOW(E)={),#} (2)由规则(3)及产生式ETE’可知FOLLOW(E)FOLLOW(E’),即有 FOLLOW(E’)={),#}

6 求FIRST,FOLLOW集例子(续) (3)由规则(2)及产生式E’ATE’有 FIRST(E’)-{}FOLLOW(T);再由规则(3)及ETE’和E’*有 FOLLOW(E)FOLLOW(T) 即FOLLOW(T)={+,-}{),#}={+,-,),#} (4)由规则(3)有TFT’有FOLLOW(T)FOLLOW(T’),即FOLLOW(T’)={+,-,),#} (5)由规则(2)及T’MFT’,有 FIRST(T’)-{} FOLLOW(F),再由规则(3)及T’MFT’和T’*,有FOLLOW(T’) FOLLOW(F),从而, FOLLOW(F)={*, /}{+,-,),#}={+,-,*,/,),#} (6)由规则(2)及E’ATE’,T’ MFT’ ,有 FIRST(T)FOLLOW(A), FIRST(F) FOLLOW(M),故有 FOLLOW(A)={(,i}, FOLLOW(M)={(,i}.

7 FIRST集和FOLLOW集

8 二、LL分析表的构造 造表的算法 在AVN所在行,aVT所在列, M[A,a]的填写方法如下:
对已给的LL(1)文法,在得到各文法符号的FIRST集和FOLLOW集之后,就可容易地构造出LL(1)分析表 (也称预测分析表). 在实际的表存储结构中,矩阵中每个元素并非真正存储的是产生式,而是其右部的逆序(也可以是产生式序号),这样便于分析时使用,并节省了内存空间. 造表的算法 在AVN所在行,aVT所在列, M[A,a]的填写方法如下: (1) if ( AP and aFIRST() )M[A,a] =‘A’; (2) if ( * ( FIRST()) and aFOLLOW(A) ) M[A,a]=‘A’; (3) Otherwise, M[A,a]=‘ERR’.

9 LL(1)分析表

10 三、分析器的工作原理 分析器对输入串的分析在控制程序的控制下进行，步骤如下：
1.初始化.首先将#及开始符S压入栈,各指针置初值.此时,格局为 # S a1 a2 … … an # # X1 X2 …Xm-1 Xm ai ai+1 … … an #c 2.设在分析的某时刻,的分析格局为 此时,根据当前栈顶符号Xm的不同情况,分别作如下处理: (1) XmVT,且Xm=ai,则匹配,将Xm 顶出栈,输入指针++;否则(Xmai),出错; (2) XmVN 查表M[Xm,ai],若M[Xm,ai]=“ERR”,则出错;若M[Xm,ai]= “Xm Y1Y2…Yk” ,则将Xm 出栈, Y1Y2…Yk 按逆序压入栈,得到格局 # X1 X2 …Xm-1YkYk-1...Y1 ai ai+1 … … an # (3)若Xm=ai=#,则表明输入串已完全得到匹配,分析成功,结束.

11 对i+i*i进行预测分析的过程

12 四 某些非LL(1)文法的改造 对于LL(1)文法而言,我们总能构造出相应的预测分析表,且表中决不会含有多重定义的元素.
然而对于非LL(1)文法,它们不满足LL(1)文法的条件,尽管仍可为其建立预测分析表,但表中必然会出现多重定义的元素(why?) 例如,文法G[S]: SabB ASC|BAA| BAbA CB| FIRST(S)={a} FIRST(A)={a,b, } FIRST(B)={a,b} FIRST(C)={a,b,c} FOLLOW(S)= FOLLOW(A)=FOLLOW(B)= FOLLOW(C)= {a,b,c,#}, 由造表规则,有 M[A,a]={ASC,A}, 同理, M[B,b]={ABAA, A }. 可见非LL(1)文法所造之表中,必有冲突元素.事实上, 是否有冲突元素也是判别一文法是否是LL(1)文法的方法之一. 对于某些非LL(1)文法而言,通过消除左递归,反复提取左因子等方法,有时是可以将其改造成LL(1)文法的.

13 某些非LL(1)文法的改造(续) 提取左因子 当文法中含有形如 A1|2|…|m 的产生式时,可将其改写为: AA’ A’1|2|…|m 若诸候选式1,2,…,m 中的一部分仍含有左因子 ,则再进行提取工作,如此等等.这样,就可能得到一个LL(1)文法. 例如, EE+T | T T(E) | a(E) | a 经改造后可得文法 ETE’ E’+TE’|  TaT’ | (E) T’ (E) |  这是一个LL(1)文法. 应当指出,并非所有的文法都能改造为LL(1)文法. 例如,文法G[S]: SAU | BR AaAU | b BaBR | b Uc Rd 文法中S的两个候选式AU及BR的FIRST集相交,G是非LL(1)的.为提取左因子,先将S产生式中的A,B用其右部替换,得: SaAUU|bU|aBRR|bR, 经提取左因子,得 S aS’|bS” S’AUU|BRR S” U|R A… 显然它仍不是LL(1)文法

14 关于LL(1)的一些结论 能由LL(1)文法产生的语言称为LL(1)语言.它们已被证明具有许多重要特性, 主要有:
(5) CFL是否是LL(1)语言是不可判定的; (6) 非LL(1)语言是存在的. 若在分析过程中,每步向前扫描k个符号来确定选用的产生式,此分析方法称为是LL(k)分析.此法极少用,故从略.