吉林大学：《编译原理》课程教学资源（PPT课件讲稿）LL分析方法—自顶向下分析

LL分析方法自顶向下分析 ●LL(1)是L(k)的特例,其中的k则表示向前看k 个符号。 ●LL(1)方法和递归下降法属于同一级别的自顶 向下分析法,但有一些区别 递归下降法对每个非终极符产生子程序,而L()方 法则产生L分析表; 递归下降法能判断每个产生式的结束,而L(1)方法 则不能; 递归下降法分析法不用符号栈,而L(1)方法则用符 号栈

LL分析方法—自顶向下分析 ⚫ LL(1)是LL(k)的特例,其中的k则表示向前看k 个符号。 ⚫ LL(1)方法和递归下降法属于同一级别的自顶 向下分析法，但有一些区别. ▪ 递归下降法对每个非终极符产生子程序，而LL(1)方 法则产生LL分析表； ▪ 递归下降法能判断每个产生式的结束，而LL(1)方法 则不能； ▪ 递归下降法分析法不用符号栈，而LL(1)方法则用符 号栈

LL(1)分析方法的条件 对于任一非终极符A,其任意两个产生式 A→α和A→β,都要满足下面条件: Predict(A→a)∩ Predict(A→β)= 满足这一条件的文法称为LL(1)文法

LL(1)分析方法的条件 对于任一非终极符A，其任意两个产生式 A→和A→，都要满足下面条件： Predict(A→)  Predict(A→)=  满足这一条件的文法称为LL(1)文法

LL(1)分析例 文法G[A]:A→aBc[1 B→>d[2]|bB[3] 输入串: abbdc ●分析过程: ●(A, abbdc)→1(cBa,abbd)→(cB,bbdc) →3(cBb,bbd)→(cB,bdc)→3(cBb,bdc) →(cB,d)→2(cd,dc)→(c,o)→(,)

LL(1)分析例 ⚫ 文法G[A]: A → a B c[1] ⚫ B → d [2]| b B[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)分析的动作 替换:当米1∈V时选相应候选式β去替换X1 匹配:当X1∈时它与Y进行匹配,其结果可 能成功,也可能失败,如果成功则去掉X和 Y1,否则报错。 ●接受:当格局为(空,空)时报分析成功。 ●报错:出错后,停止分析

LL(1)分析的动作 ⚫ 替换：当X1VN时选相应候选式去替换X1。 ⚫ 匹配：当X1VT时它与Y1进行匹配，其结果可 能成功，也可能失败，如果成功则去掉X1和 Y1，否则报错。 ⚫ 接受：当格局为（空，空）时报分析成功。 ⚫ 报错：出错后，停止分析

LL(1)分析表 T:V×V→P∪[ Error NX T(A,t)=A→a若t∈ Predict(A→a) T(A, t=Error 否则 其中P表示所有产生式的集合

LL(1)分析表 ⚫ T：VN  VT → P  { Error } T(A,t)=A→ 若tPredict( A→ ) T(A,t)=Error 否则 其中P表示所有产生式的集合

LL(1)分析的驱动器 Input 栈为空情形的处理 X∈V情形的处理 X∈V情形的处理 Stack LL[分析 表

LL(1)分析的驱动器 Stack Input a • 栈为空情形的处理 • X VT情形的处理 • X  VN情形的处理 X LL[1]分析 表

LL Driver [们初始化: Stack:= empty;Push(S) [2]读下一个输入符:Read(a); [3]若当前格局是( empty,#),则成功结束; 否则转下; [4]设当前格局为(.X,a...),则 ●若X∈Vr&X=a yuu [Pop(1); Read(a); goto [3]] 若XⅥ&X≠a则 Error; 若X∈V,则 ifT(x,a)=X→Y1Y2Y then (Pop(1); Push n,.,Y1); goto [3]] ese Error

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，则： if T(X,a)=X→Y1 Y2 Yn then {Pop(1)；Push(Yn ,..... ,Y1 )；goto[3]} else Error

LL分析实例 文法G: E→TE E”→+TE2|的 T→FT4 T→*FT|A同 F→id|(E) 符号串i+i*i#的LL[1分析过程:

LL分析实例 ⚫文法G: E → T E’[1] E’ → + T E’[2] |  [3] T → F T’[4] T’ → * F T’[5] |  [6] F → id[7] | ( E )[8] 符号串 i + i * i # 的LL[1]分析过程：

Predict([1]=first(Te) {id,(} Predict(2)=first(+TE)=(+) Predict(3)=follow(E) =0,#i Predict(4))=first(FT) =(id, Predict( 5 )=first(FT)=*) Predict(6)=follow T)=(+),#) Predict([ 7)=first(id) ={id} Predict( 8)=first((E =o

Predict( [1] ) = first(TE’) = { id , ( } Predict( [2] ) = first(+TE’) = { + } Predict( [3] ) = follow(E’) = { ) , # } Predict( [4] ) = first(FT’) = { id , ( } Predict( [5] ) = first(*FT’) = { * } Predict( [6] ) = follow(T’) = { + , ) , # } Predict( [7] ) = first(id) = { id } Predict( [8] ) = first((E)) = { ( }

分析栈S 输入流T 矩阵元素 #E i+i*i# LLIE,i=1 #E’T i十ii# LLIT,i=4 #E’TF taxi# LLIF,i=71 #ETi i +i*i# Match #E’T tisi# LL[T’,+=同6 # E ti*i# LIE,+]=[2 #E’T+ 十ii# Match #E’T i# LL IT, i=14 #ETF i# LLIF, 1=7 #E’Ti Match #ET *i# LLIT’,]=|5 #ET”F* Match #ET”F LLF, i=7 # ETi # Match #ET LLIT, #=6 # e # LLE,#=3 #

分析栈S 输入流T 矩阵元素 # E i + i * i # LL[ E ,i ] = [1] # E’ T i + i * i # LL [ T ,i ] = [4] # E’ T’ F i + i * i # LL [ F ,i ] = [7] # E’ T’ i i + i * i # Match # E’ T’ + i * i # LL [ T’,+] = [6] # E’ +i * i # LL [ E’,+ ] = [2] # E’ T+ +i * i # Match # E’ T i * i # LL [ T,i ] =[4] # E’ T’ F i* i # LL [ F,i ] = [7] # E’ T’ i i * i # Match # E’ T’ * i # LL [ T’,* ] = [5] # E’T’F* * i # Match # E’T’F i # LL[F,i] = [7] # E’T’i i # Match # E’T’ # LL[T’,#] = [6] # E’ # LL[E’, #] = [3] # # ok