LL(1)分析方法 LL(1)是LL(k)的特例,其中的k则表示向前看k个符号. LL(1)方法和递归下降法属于同一级别的自顶向下分析法. 括号中的“1”,则表示在分析过程中,每进行一步推导,只要查看一个输入符号便能确定当前所应选用的产生式.
1 LL(1)分析方法的思想 对给定的终极符串ace,分析过程: 符号栈 输入流 驱动程序 ace # #Z 替换[1] #eBa 例 G[z] : [1] Z aBe [2] Z Bd [3] B bB [4] B cK [5] D d [6] K ε {b,c} {b} {d} {c} {d,e} {a} 对给定的终极符串ace,分析过程: 符号栈 输入流 驱动程序 ace # #Z 替换[1] #eBa ace # 匹配Match #eB ce # 替换[4] #eKc ce # 匹配Match #eK e # 替换[6] #e e # 匹配Match # # Success
b c d e Z B D K Error # LL(1)分析表 a 例 G[z] : [1] Z aBe [2] Z Bd [3] B bB [4] B cK [5] D d [6] K ε {b,c} {b} {d} {c} {d,e} {a} a b c d e Z B D K Z aBe Z Bd Error K ε B bB B cK D d # LL(1)分析表
对给定的终极符串acb,分析过程: 符号栈 输入流 驱动程序 acb # #Z 替换[1] #eBa acb # 匹配Match #eB 例 G[z] : [1] Z aBe [2] Z Bd [3] B bB [4] B cK [5] D d [6] K ε {b,c} {b} {d} {c} {d,e} {a} 对给定的终极符串acb,分析过程: 符号栈 输入流 驱动程序 acb # #Z 替换[1] #eBa acb # 匹配Match #eB cb # 替换[4] #eKc cb # 匹配Match #eK b # Error
在逻辑上,一个LL(1)分析器由输入流、LL(1)分析表、符号栈和驱动程序组成: 输入流:待分析的符号串 . 符号栈:存放分析过程中的文法符号串. LL(1)分析表:用来表示相应文法的全部信息 的一个矩阵(或二维数组). 驱动程序:语法分析程序.
4.5.2 LL(1)分析表的构造 LL(1)分析表的定义: T:VN VT → P { Error } T(A,t)=A→ 若tPredict( A→ ) T(A,t)=Error 否则 其中P表示所有产生式的集合.
E T E’[1] i + * ( ) # E 1 E’ 2 3 T 4 T’ 6 5 F 7 8 E’ + T E’[2] | ε[3] T F T’[4] T’ * F T’[5] | ε[6] F i[7] | ( E )[8] Predict( [1]) = { i , ( } Predict( [2] )= { + } Predict( [3] ) = { ) , # } Predict( [4] ) = { i , ( } Predict( [5] ) = { * } Predict( [6] = { + , ) , # } Predict( [7] ) = { i } Predict( [8] ) = { ( }
4.5.3 LL(1)驱动程序构造 LL(1)分析的动作:设当前格局为 (..... X1, Y1.....), 替换:当X1VN时选相应候选式去替换X1. 匹配:当X1VT时,它与Y1进行匹配,其结果可能成功,也可能失败,如果成功则去掉X1和Y1,否则报错. 接受:当格局为(#,#)时报分析成功. 报错:
LL(1)分析方法的驱动器 a X Input 栈顶为#情形的处理 X VT情形的处理 X VN情形的处理 Stack 栈顶为#情形的处理 X VT情形的处理 X VN情形的处理 X LL[1]分析表
LL_驱动程序 Stack = empty ; Push(#); Push(S); Read(a);//读第一个输入符 令X=栈顶符号; //X=S while(X!=# && a!=#) { //栈不空,输入没结束 if (X VT ){ if( X= a) { Pop(1); Read(a);} else {Error( );return(-1);} } else if ( T(X, a) = X→Y1 Y2........ Yn ) { Pop(1);Push(Yn ,.....,Y1);// Y1在栈顶 } else { Error( ); return(-1); } 令X=栈顶符号; if ( X=# && a=#) Success( ); else Error( );
例2:文法G: E’ + T E’[2] | ε[3] T F T’[4] T’ * F T’[5] | ε[6] F i[7] | ( E )[8] 符号串 i + i * i # 的LL[1]分析过程:
E T E’[1] { i , ( } 分析栈 输入流 矩阵元素 # E i + i * i # LL[ E ,i ] = [1] 分析栈 输入流 矩阵元素 # 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 E T E’[1] { i , ( } E’ + T E’[2] { + } | ε[3] { ) , # } T F T’[4] { i , ( } T’ * F T’[5] { * } | ε[6] { + , ) , # } F id[7] { i } | ( E )[8] { ( }
E T E’[1] { i , ( } 分析栈 输入流 矩阵元素 # E i + i *+ i # LL[ E ,i ] = [1] 分析栈 输入流 矩阵元素 E T E’[1] { i , ( } E’ + T E’[2] { + } | ε[3] { ) , # } T F T’[4] { i , ( } T’ * F T’[5] { * } | ε[6] { + , ) , # } F id[7] { i } | ( E )[8] { ( } # 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,+] =Error
自顶向下语法分析方法的总结 一、自顶向下语法分析条件 predict(Aβk)predict(Aβj)= 当kj
二、LL(1)方法和递归下降法的区别 递归下降法对每个非终极符产生子程序,而LL(1)方法算法不变只是LL分析表不同;
练习:构造下述文法的LL(1)分析表. G[D]: D TL T int | float L id R R , id R | ε 文法符号 First集 Follow集 D { int,float } { # } T { int,float} { id } L { # } R { , , } Predict( D TL ) = { int,float } Predict( T int ) = { int } Predict( T float) = { float} Predict( L id R) = {id} Predict( R , id R ) = { ,} Predict( R ε ) = {#}
G[D]: D TL T int | float L id R R , id R | ε int float id , # Predict( D TL ) = { int,float } Predict( T int ) = { int } Predict( T float) = { float} Predict( L id R) = {id} Predict( R , id R ) = { ,} Predict( R ε ) = {#} int float id , # D D TL T T int T float L L id R R R , id R R ε
练习 课后题1:设有如下文法G[S] SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|Cg9|10 求每个产生式的Predict集 该文法是否为LL(1)文法,为什么?
First集 G[S]: SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|Cg9|10 First(S)={,a} First(A)={,a,d} First(B)={,a,d,h,e} First(C)={,a,f,g} First(aABbcd)={a} First(ASd)={a,d} First(SAh)={a,d,h} First(eC)={e} First(Sf)={a,f} First(Cg)={a,f,g}
Follow集 G[S]: SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|Cg9|10 First(S)={,a} First(A)={,a,d} First(B)={,a,d,h,e} First(C)={,a,f,g} Follow(S)={#,a,d,h,f} Follow(A)={a,b,d,h,e} Follow(B)={b} Follow(C)={g,b}
Predict集 Predict(1)={a} Predict(2)={a,d,h,f,#} Predict(3)={a,d} G[S]: SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|Cg9|10 Predict集 Predict(1)={a} Predict(2)={a,d,h,f,#} Predict(3)={a,d} Predict(4)={a,d,e,h} Predict(5)={a,d,h} Predict(6)={e} Predict(7)={b} Predict(8)={a,f} Predict(9)={a,f,g} Predict(10)={g,b} First(aABbcd)={a} First(ASd)={a,d} First(SAh)={a,d,h} First(eC)={e} First(Sf)={a,f} First(Cg)={a,f,g} Follow(S)={a,d,h,f,#} Follow(A)={a,b,d,h,e} Follow(B)={b} Follow(C)={g,b} 由于不同产生式规则的Predict集有交集,所以该文法不是LL(1)文法。
课后题2 判断下列文法那些是LL(1)文法 S(SS’| S’)| S(S)S| SS(S)S| S(S|S’ Predict(S(SS’)={(} Predict(S)={),#} Predict(S’))={)} Predict(S’)={),#} 不是LL(1)文法 Predict(S(S)S)={(} Predict(S)={),#} 是LL(1)文法 Predict(SS(S)S)={(} Predict(S)={),(,#} 左递归,不是LL(1)文法 Predict(S(S)={(} Predict(SS’)={(,#} Predict(S’(S’))={(} 判断下列文法那些是LL(1)文法 S(SS’| S’)| S(S)S| SS(S)S| S(S|S’ S’(S’)|
课后题3 已知文法G[E] EE+T|T TT*F|F Fi|(E) 按递归下降法构造此文法的语法分析程序 步骤: 判断文法类型 文法变换 消除左递归 提取公共前缀 求Predict集 设计程序
文法变换 EE+T|T ETE’ E’+TE’| TT*F|F TFT’ T’*FT’| G[E] EE+T|T TT*F|F Fi|(E) EE+T|T ETE’ E’+TE’| TT*F|F TFT’ T’*FT’| 消除左递归 对直接左递归形如: AA| 消除左递归可得: AA AA|
课后题4 A S 1 B 构造LL(1)文法G以识别语言L,其中={0,1} L={x|x为不包括两个相邻的1的非空串} S0A[1]|1B[2] A0A[3]|1B[4]|[5] B0A[6]|[7] Predict集 P(1)={0}=P(3)=P(6) P(2)={1}=P(4) P(5)={#}=P(7) S A B 1
课后题5 已知文法G[A] AaABe|a BBb|d 求G的LL(1)等价文法G’ [A] 构造G’[A]的LL(1)分析表并给出输入串aade#的分析过程。 AaABe|a 消除公共前缀得 AaA’[1] A’ABe[2]|[3] BBb|d 消除左递归得 BdB’[4] B’bB’[5]|[6] 26
a b d e # A 1 A’ 2 3 B 4 B’ 5 6 AaA’[1] A’ABe[2]|[3] BdB’[4] B’bB’[5]|[6] (#A,aade#) 1 (#A’a,aade#) m (#A’,ade#) 2 (#eBA,ade#) 1 (#eBA’a,ade#) m (#eBA’,de#) 3 (#eB,de#) 4 (#eB’d,de#) m (#eB’,e#) 6 (#e,e#) m (#,#) ok P(1)={a} P(2)={a} P(3)={d,#} P(4)={d} P(5)={b} P(6)={e} a b d e # A 1 A’ 2 3 B 4 B’ 5 6 27