LL分析方法自顶向下分析.ppt

《LL分析方法自顶向下分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、LL分析方法—自顶向下分析LL(1)是LL(k)的特例,其中的k则表示向前看k个符号。LL(1)方法和递归下降法属于同一级别的自顶向下分析法，但有一些区别.递归下降法对每个非终极符产生子程序，而LL(1)方法则产生LL分析表；递归下降法能判断每个产生式的结束，而LL(1)方法则不能；递归下降法分析法不用符号栈，而LL(1)方法则用符号栈。LL(1)分析方法的条件对于任一非终极符A，其任意两个产生式A→和A→，都要满足下面条件：Predict(A→)Predict(A→)=满足这一条件的文法称为LL(1)文法。LL(1)分析例文法G[A]:AaBc[1]

2、Bd[2]

3、bB[3]输入串：abbdc分析过程：(A,abbdc)1(cBa,abbdc)(cB,bbdc)3(cBb,bbdc)(cB,bdc)3(cBb,bdc)(cB,dc)2(cd,dc)(c,c)(,)LL(1)分析的动作替换：当X1VN时选相应候选式去替换X1。匹配：当X1VT时它与Y1进行匹配，其结果可能成功，也可能失败，如果成功则去掉X1和Y1，否则报错。接受：当格局为（空，空）时报分析成功。报错：出错后，停止分析。LL(1)分析表T：VNVT→P{Error}T(A,t)=A→若tPredict(A→)T(A,

4、t)=Error否则其中P表示所有产生式的集合LL(1)分析的驱动器StackInputa栈为空情形的处理XVT情形的处理XVN情形的处理XLL[1]分析表LL_Driver[1]初始化：Stack:=empty；Push(S)；[2]读下一个输入符：Read(a)；[3]若当前格局是(empty,#)，则成功结束；否则转下；[4]设当前格局为（.....X,a.....)，则若XVT&X=a则{Pop(1)；Read(a)；goto[3]}若XVT&Xa则Error；若XVN，则：ifT(X,a)=X→Y1Y2Ynthen{Pop(1)；P

5、ush(Yn,.....,Y1)；goto[3]}elseErrorLL分析实例文法G:ETE’[1]E’+TE’[2]

6、[3]TFT’[4]T’*FT’[5]

7、[6]Fid[7]

8、(E)[8]符号串i+i*i#的LL[1]分析过程：Predict([1])=first(TE’)={id,(}Predict([2])=first(+TE’)={+}Predict([3])=follow(E’)={),#}Predict([4])=first(FT’)={id,(}Predict([5])=first(*FT’)={*}Predict([6])=fol

9、low(T’)={+,),#}Predict([7])=first(id)={id}Predict([8])=first((E))={(}分析栈S输入流T矩阵元素#Ei+i*i#LL[E,i]=[1]#E’Ti+i*i#LL[T,i]=[4]#E’T’Fi+i*i#LL[F,i]=[7]#E’T’ii+i*i#Match#E’T’+i*i#LL[T’,+]=[6]#E’+i*i#LL[E’,+]=[2]#E’T++i*i#Match#E’Ti*i#LL[T,i]=[4]#E’T’Fi*i#LL[F,i]=[7]#E’T’ii*i#Match#E’T’*i#LL[T’

10、,*]=[5]#E’T’F**i#Match#E’T’Fi#LL[F,i]=[7]#E’T’ii#Match#E’T’#LL[T’,#]=[6]#E’#LL[E’,#]=[3]##okIf-then-else语句BL语言{[i]j

11、i>=j>=0}不是LL文法条件语句的产生式是无法变换成LL[1]型产生式的。