LL(1)分析方法 LL(1)是LL(k)的特例,其中的k则表示向前看k个符号. LL(1)方法和递归下降法属于同一级别的自顶向下分析法.

Presentation on theme: "LL(1)分析方法 LL(1)是LL(k)的特例,其中的k则表示向前看k个符号. LL(1)方法和递归下降法属于同一级别的自顶向下分析法."— Presentation transcript:

1 LL(1)分析方法 LL(1)是LL(k)的特例,其中的k则表示向前看k个符号. LL(1)方法和递归下降法属于同一级别的自顶向下分析法.
括号中的“1”，则表示在分析过程中，每进行一步推导，只要查看一个输入符号便能确定当前所应选用的产生式.

2 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

3 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)分析表

4 对给定的终极符串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

5 在逻辑上，一个LL(1)分析器由输入流、LL(1)分析表、符号栈和驱动程序组成：
输入流:待分析的符号串 . 符号栈:存放分析过程中的文法符号串. LL(1)分析表：用来表示相应文法的全部信息 的一个矩阵（或二维数组）. 驱动程序：语法分析程序.

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

7 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] ) = { ( }

8 4.5.3 LL(1)驱动程序构造 LL(1)分析的动作：设当前格局为 （..... X1, Y1.....)， 替换：当X1VN时选相应候选式去替换X1. 匹配：当X1VT时，它与Y1进行匹配，其结果可能成功，也可能失败，如果成功则去掉X1和Y1，否则报错. 接受：当格局为（#，#）时报分析成功. 报错：

9 LL(1)分析方法的驱动器 a X Input  栈顶为#情形的处理  X VT情形的处理  X  VN情形的处理 Stack
 栈顶为#情形的处理  X VT情形的处理  X  VN情形的处理 X LL[1]分析表

10 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 Y Yn ) { Pop(1)；Push(Yn ,.....,Y1)；// Y1在栈顶 } else { Error( ); return(-1); } 令X=栈顶符号； if ( X=# && a=#) Success( ); else Error( );

11 例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]分析过程：

12 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] { ( }

13 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

14 自顶向下语法分析方法的总结 一、自顶向下语法分析条件 predict(Aβk)predict(Aβj)= 当kj

15 二、LL(1)方法和递归下降法的区别 递归下降法对每个非终极符产生子程序，而LL(1)方法算法不变只是LL分析表不同；

16 练习：构造下述文法的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  ε ) = {#}

17 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  ε

18 练习 课后题1：设有如下文法G[S] SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|Cg9|10
求每个产生式的Predict集 该文法是否为LL(1)文法，为什么？

19 First集 G[S]： SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|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}

20 Follow集 G[S]： SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|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}

21 Predict集 Predict(1)={a} Predict(2)={a,d,h,f,#} Predict(3)={a,d}
G[S]： SaABbcd1|2 AASd3|4 BSAh5|eC6|7 CSf8|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)文法。

22 课后题2 判断下列文法那些是LL(1)文法 S(SS’| S’)| S(S)S| SS(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(SS(S)S)={(} Predict(S)={),(,#} 左递归，不是LL(1)文法 Predict(S(S)={(} Predict(SS’)={(,#} Predict(S’(S’))={(} 判断下列文法那些是LL(1)文法 S(SS’| S’)| S(S)S| SS(S)S| S(S|S’ S’(S’)|

23 课后题3 已知文法G[E] EE+T|T TT*F|F Fi|(E) 按递归下降法构造此文法的语法分析程序 步骤： 判断文法类型
文法变换 消除左递归 提取公共前缀 求Predict集 设计程序

24 文法变换 EE+T|T ETE’ E’+TE’| TT*F|F TFT’ T’*FT’|
G[E] EE+T|T TT*F|F Fi|(E) EE+T|T ETE’ E’+TE’| TT*F|F TFT’ T’*FT’| 消除左递归 对直接左递归形如： AA| 消除左递归可得： AA AA|

25 课后题4 A S 1 B 构造LL(1)文法G以识别语言L，其中={0,1} L={x|x为不包括两个相邻的1的非空串}
S0A[1]|1B[2] A0A[3]|1B[4]|[5] B0A[6]|[7] Predict集 P(1)={0}=P(3)=P(6) P(2)={1}=P(4) P(5)={#}=P(7) S A B 1

26 课后题5 已知文法G[A] AaABe|a BBb|d 求G的LL(1)等价文法G’ [A] 构造G’[A]的LL(1)分析表并给出输入串aade#的分析过程。 AaABe|a 消除公共前缀得 AaA’[1] A’ABe[2]|[3] BBb|d 消除左递归得 BdB’[4] B’bB’[5]|[6] 26

27 a b d e # A 1 A’ 2 3 B 4 B’ 5 6 AaA’[1] A’ABe[2]|[3] BdB’[4]
B’bB’[5]|[6] (#A,aade#) 1 (#A’a,aade#) m (#A’,ade#) 2 (#eBA,ade#) 1 (#eBA’a,ade#) m (#eBA’,de#) (#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