LR(0)项目集族和LR(0)分析表的构造课件.ppt

1、第五章第五章 语法分析语法分析5.1 5.1 自下而上分析基本问题自下而上分析基本问题5.2 5.2 算符优先分析算符优先分析 5.3 LR5.3 LR分析分析5.4 YACC5.4 YACC5.3 LR5.3 LR分析分析5.3.1 LR5.3.1 LR分析器分析器5.3.2 LR(0)5.3.2 LR(0)项目集族项目集族LR(0)LR(0)分析表的构分析表的构造造5.3.3 SLR5.3.3 SLR分析表的构造分析表的构造5.3.4 5.3.4 规范规范LRLR分析表的构造分析表的构造5.3.5 LALR5.3.5 LALR分析表的构造分析表的构造5.3.6 5.3.6 二义文法的应用二

2、义文法的应用5.3.2 LR(0)5.3.2 LR(0)项目集族项目集族LR(0)LR(0)分析表的构分析表的构造造一、前缀、活前缀一、前缀、活前缀 p104p104二、构造识别文法所有活前缀的二、构造识别文法所有活前缀的DFA DFA p104p104三、三、LR(0)LR(0)项目集规范族的构造项目集规范族的构造 p106p106四、有效项目四、有效项目 p108p108五、五、LR(0)LR(0)分析表的构造分析表的构造 p109p109一、前缀、活前缀一、前缀、活前缀 前缀前缀 : : 符号串的头符号串的头 活前缀活前缀 : : 规范句型的一个前缀规范句型的一个前缀, , 这种这种前缀

3、不包含句柄之后的任何符号前缀不包含句柄之后的任何符号. .* *可归前缀可归前缀: : 包含句柄的活前缀包含句柄的活前缀. .规范规范推导推导序列序列 S S=aAcBeaAcBe=aAc=aAcd de e=a=aAbAbcdecde=a=ab bbcde bcde ,a,a,abab,a,aA,a,aA,aAbaAb ,a,aA,aAc,a,aA,aAc,aAcdaAcd,a,aA,aAc,aAcB,a,aA,aAc,aAcB,aAcBaAcBe e活前缀活前缀可归前缀可归前缀ab , aAb, aAcd , ab , aAb, aAcd , aAcBeaAcBe补充例补充例: : 找出找

4、出句型句型 #abbcde# #abbcde# 的所有活前缀的所有活前缀G:SaAcBeG:SaAcBe11 AbAb22 AAbAAb33 BdBd44abb c d eAABS当栈顶出现可归前缀即可归约当栈顶出现可归前缀即可归约步步骤骤符号栈符号栈剩余剩余输入串输入串动作动作1 1# #abbcdeabbcde# # 移进移进2 2#a#abbcde#bbcde# 移进移进3 3#a#ab bbcde#bcde# 归约归约 Ab4 4#aA#aAbcde#bcde# 移进移进5 5#a#aAbAbcde#cde# 归约归约 AAb6 6#aA#aAcde#cde# 移进移进7 7#aAc#

5、aAcde#de# 移进移进8 8#aAc#aAcd de#e# 归约归约 Bd9 9#aAcB#aAcBe#e# 移进移进1010 # #aAcBeaAcBe# # 归约归约 SaAcBe1111 #S#S# # 接受接受abb c d eAABS1.1.栈里的文法符号与栈里的文法符号与剩余符号串一起构剩余符号串一起构成了规范句型成了规范句型2.2.栈里的文法符号构栈里的文法符号构成活前缀成活前缀 S = S =aAcBeaAcBe =aAc =aAcd de e =a =aAbAbcde cde =a =ab bbcde bcde 规范规范推导推导序列序列#abbcde#abbcde#的规

6、范归约过程的规范归约过程S =S =aAcBe =aAcde =aAbcde =abbcde 规范规范推导推导序列序列识别句型识别句型#abbcde#abbcde#所有活前缀的所有活前缀的DFADFASabaAbaAcdaAcBe确定化确定化最小化最小化0245136897SaAbcBed*bG:SaAcBeG:SaAcBe11AbAb22AAbAAb33BdBd44利用利用DFADFA进行进行移近移近- -归约分析归约分析( (见黑板见黑板) )acebd#S A B0 2112 3434 6 556 7878 990245136897SaAbcBed*bG:SaAcBeG:SaAcBe11

7、AbAb22AAbAAb33BdBd44r rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr raccaccS SS SS SS SS SS SGOTOGOTOACTIONACTION2 22 22 22 22 22 23 33 33 33 33 33 34 44 44 44 44 44 41 11 11 11 11 11 1LRLR分析表分析表DFADFA的矩阵表示的矩阵表示一个一个LRLR分析器实质上是一个分析器实质上是一个DFADFA 小结识别文法所有活前缀的识别文法所有活前缀的DFADFALRLR分

8、析表分析表LRLR分析分析二、构造识别文法所有活前缀的二、构造识别文法所有活前缀的DFADFA 1. LR(0)1. LR(0)项目项目2. 2. 构造识别文法所有活前缀的构造识别文法所有活前缀的DFADFA3. LR(0)3. LR(0)项目的分类项目的分类求出文法所有的活前缀求出文法所有的活前缀根据产生式得出可能出现在栈中的符号串根据产生式得出可能出现在栈中的符号串1. LR(0)1. LR(0)项目项目在文法在文法G G中每个产生式的右部适当位置添加一中每个产生式的右部适当位置添加一个圆点构成项目个圆点构成项目. . 对空产生式对空产生式A A , , 仅有项目仅有项目AA例例: : 产

9、生式产生式 A A XYZ XYZ 对应的项目有对应的项目有 A AXYZXYZ A AX XYZYZA AXYXYZ Z A AXYZXYZ一个产生式可对应的项目个数是它的右部符号长度加一个产生式可对应的项目个数是它的右部符号长度加1 1每个项目的含义与圆点的位置有关每个项目的含义与圆点的位置有关 补充例补充例对应的项目对应的项目: : (1)S(1)SaAdaAd (2)S(2)S a aAdAd (3)S(3)S aAaAd d (4)S(4)S aAdaAd (5)A(5)Abc bc (6)A(6)A b bc c (7)A(7)A bcbc借助项目构造借助项目构造识别文法活前识别文

10、法活前缀的缀的DFADFAG:G: S S aAd aAd A Abcbc2. 2. 构造识别文法所有活前缀的构造识别文法所有活前缀的DFADFA1). 1). 文法的每个项目都为文法的每个项目都为NFANFA的一个状态的一个状态 2). 2). 确定状态之间的转换关系确定状态之间的转换关系 3). 3). 确定化最小化确定化最小化例例5.8 5.8 p105 p105 G:G: SESE EaEaA A|bB|bB AcA|dAcA|d BcB|d BcB|d 更更正正1 1SE SE 2 2SE SE 11. 11. EbBEbB3 3EaAEaA 12. 12. EbBEbB4 4EaA

11、EaA 13. 13. EbBEbB5 5EaAEaA 14. 14. BcBBcB6 6AcAAcA 15. 15. BcBBcB7 7AcA AcA 16. 16. BcBBcB8 8AcA AcA 17. Bd17. Bd9 9AdAd 18. 18. Bd Bd 10. Ad10. Ad文法的项目文法的项目: :1). 1). 文法的每个项目都为文法的每个项目都为NFANFA的一个状态的一个状态2). 2). 确定状态之间的转换关系确定状态之间的转换关系X Xi iXXXX1 1X X2 2XXi-1i-1X Xi iXXn nXXXX1 1X X2 2X Xi iX Xi+1i+1X

12、Xn nXXA AAA状态状态i i状态状态j j出自同一产生式出自同一产生式项目项目1 1为为初态初态 P106 P106 NFANFA1 1SESE2 2SE SE 3 3EaAEaA4 4EaAEaA 5 5EaAEaA 6 6AcAAcA7 7AcAAcA8 8AcA AcA 9 9AdAd 10. 10. Ad Ad 11. 11. EbBEbB12. 12. EbB EbB 13. 13. EbBEbB14. 14. BcBBcB15. 15. BcBBcB16. 16. BcB BcB 17. 17. Bd Bd 18. 18. Bd Bd 每个状态都为每个状态都为活前缀识别态活

13、前缀识别态 句柄识别态句柄识别态( (可归前缀识别可归前缀识别态态) ): : 圆点在最后的项目圆点在最后的项目句子识别态句子识别态 aE*AcAddcBbB786341059121318161112141517p106p106识别一个文识别一个文法活前缀的法活前缀的DFADFA3).3).确定确定化化 最小最小化化每个状态是一每个状态是一个项目集个项目集, , 称称作作LR(0)LR(0)项目集项目集整个状态集称整个状态集称为为LR(0)LR(0)项目集项目集规范族规范族3. LR(0)3. LR(0)项目的分类项目的分类移进项目移进项目: : AAa a分析时把分析时把a a移进符号栈移进

14、符号栈 待约项目待约项目: : AAB B用产生式用产生式A A的右部归约时的右部归约时, ,首先要将首先要将B B的产生式右的产生式右部归约为部归约为B, B, 对对A A的右部才能继续进行分析的右部才能继续进行分析 归约项目归约项目: : AA 表明一个产生式的右部已分析完，句柄已形成可表明一个产生式的右部已分析完，句柄已形成可以归约以归约 接受项目接受项目: : SSSS 表明已分析成功表明已分析成功 三、三、LR(0)LR(0)项目集规范族的构造项目集规范族的构造构造识别文法活前缀构造识别文法活前缀DFADFA的三种方法的三种方法 * *1.1.求出活前缀的正规表达式，然后由此正规求出

15、活前缀的正规表达式，然后由此正规表达式构造表达式构造NFA, NFA, 再确定化为再确定化为DFADFA。2.2.求出文法的所有项目，按一定规则构造识求出文法的所有项目，按一定规则构造识别活前缀的别活前缀的NFA, NFA, 再确定化为再确定化为DFADFA。3.3.通过闭包函数和转换函数，直接求出通过闭包函数和转换函数，直接求出LR(0)LR(0)项目集规范族，再由转换函数建立状态之间项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的的连接关系得到识别活前缀的DFADFA。1.1.拓广文法拓广文法2.2.项目集项目集I I的闭包函数的闭包函数 CLOSURE(I)CLOSURE

16、(I)3.3.状态转换函数状态转换函数 GO(I, X)GO(I, X)4.4.构造文法的构造文法的LR(0)LR(0)项目集规范族项目集规范族21可编辑1.1.拓广文法拓广文法原文法原文法G G的开始符号为的开始符号为S, S, 在在G G中加中加SSSS 后得新的文法后得新的文法GG， 则称则称 GG为原文法为原文法G G的拓广文法。的拓广文法。使文法的开始符号不出现在任何产生式右部，使文法的开始符号不出现在任何产生式右部，当栈顶出现当栈顶出现S,S,则分析完成则分析完成 。注注: :即使原开始符号即使原开始符号S S不出现在任何产生式右部不出现在任何产生式右部, ,为了统一起见也要增加该

17、产生式。为了统一起见也要增加该产生式。2.2.项目集项目集I I的闭包函数的闭包函数 CLOSURE(I)CLOSURE(I)a) a) I I 的项目均在的项目均在 CLOSURE(I) CLOSURE(I) 中。中。b)b) 若若AAB B属于属于CLOSURE(I), CLOSURE(I), 则每一形如则每一形如 B B的项目也属于的项目也属于CLOSURE(I)CLOSURE(I)c)c) 重复重复b)b)直到直到CLOSURE(I)CLOSURE(I)不再扩大。不再扩大。 NFA NFA : : 状态集合状态集合I I的的-闭包闭包 -closure(I)-closure(I)AAB

18、 BB BaE*AcAddcBbB786341059121318161112141517补充例补充例I I SE SE CLOSURE(I) = SE, CLOSURE(I) = SE, EaAEaA, , EbB EbB 1 1SESE2 2SE SE 3 3EaAEaA4 4EaAEaA 5 5EaAEaA 6 6AcAAcA7 7AcAAcA8 8AcA AcA 9 9AdAd 10. 10. Ad Ad 11. 11. EbBEbB12. 12. EbB EbB 13. 13. EbBEbB14. 14. BcBBcB15. 15. BcBBcB16. 16. BcB BcB 17.

19、17. Bd Bd 18. 18. Bd Bd 1 13 311113.3.状态转换函数状态转换函数 GO(I, X)GO(I, X)GO(I, X) = CLOSURE(J)GO(I, X) = CLOSURE(J), X(V, X(VN NVVT T) , ) , J = J = AAX X| | AAX XI I X XAAX XAAX X若状态若状态I I识别活前缀识别活前缀,则状态则状态J J识别活前缀识别活前缀XX 状态状态I I状态状态J JNFA NFA : : 状态集合状态集合I I的的a a弧转换弧转换 aE*AcAddcBbB78634105912131816111214

20、1517补充例补充例I I SE , E SE , Ea aA , EbBA , EbB GO(I, a) = CLOSURE( GO(I, a) = CLOSURE( EEa aA A ) )= = EaAEaA , AcA, Ad, AcA, Ad 1 1SESE2 2SE SE 3 3EaAEaA4 4EaAEaA 5 5EaAEaA 6 6AcAAcA7 7AcAAcA8 8AcA AcA 9 9AdAd 10. 10. Ad Ad 11. 11. EbBEbB12. 12. EbB EbB 13. 13. EbBEbB14. 14. BcBBcB15. 15. BcBBcB16. 1

21、6. BcB BcB 17. 17. Bd Bd 18. 18. Bd Bd 1 13 311114 46 69 94.4.构造文法的构造文法的LR(0)LR(0)项目集规范族项目集规范族 C=IC=I0 0,I,I1 1,I,In n 核核: : 圆点不在产生式右部最左边的项目称为核圆点不在产生式右部最左边的项目称为核 a) a) 置项目置项目SSSS为初态集的核，然后对核求为初态集的核，然后对核求闭包，闭包，CLOSURE(SSCLOSURE(SS）得到初态的项）得到初态的项目集。目集。b) b) 对初态集或其它所构造的项目集应用转换对初态集或其它所构造的项目集应用转换函数函数GO(IGO

22、(I，X)=CLOSURE(J)X)=CLOSURE(J)求出新状态求出新状态J J的项的项目集。目集。c) c) 重复重复b)b)直到不出现新的项目为止。直到不出现新的项目为止。算法算法Procedure itemsets(G)Procedure itemsets(G) Begin Begin C:= CLOSURE(SC:= CLOSURE(SS ) S ) RepeatRepeat forfor C C中的每一个中的每一个I I 和每一个和每一个X X dodo ifif GO(I, X)GO(I, X)非空且不属于非空且不属于C C thenthen 把把GO(I, X)GO(I, X

23、)放入放入C C中中 untiluntil C C不再增大不再增大end end p107p107初态的项目集初态的项目集 应用状态转换应用状态转换函数得到新的函数得到新的项目集项目集 G:G: SESE EaA|bBEaA|bB AcA|dAcA|d BcB|d BcB|d I I0 0: : SSE E E E aA aA E E bBbBI I8 8: : B Bc cB B B B cB cB B B d dI I3 3: : E Eb bB B B B cB cB B B d dI I2 2: :E Ea aA A A A cA cA A A d dI I1 1: : S S E E

24、I I5 5: :A Ac cA A A A cA cA A A d dI I1010:A:Ac Ac AI I6 6: :A A d dI I4 4:E:EaAaAI I7 7:E:EbBbBI I9 9: :B B d dI I1111:B:BcBcB b b E E a a c c c c c c c c d d d d d d d d A A A A B B B B识别文法所有活前识别文法所有活前缀的缀的DFADFALR(0)LR(0)项目集规范族项目集规范族 II0 0,I,I1 1, I, I1111 四、有效项目四、有效项目 * *如果存在规范推导如果存在规范推导 则项目则项目A

25、 A 1 1 2 2 对活前缀对活前缀 1 1 是有效的。是有效的。o 如果如果 2 2 ，应该移进，应该移进o 如果如果 2 2 = = ，应该用产生式，应该用产生式A A 1 1归约归约*RR 1 2 A SI0: SE E aA E bBI5: BcB B cB B dI3: EbB B cB B dI2:EaA A cA A dI1: S E I4:AcA A cA A dI8:Ac AI10:A d I6:EaA I7:EbBI11:B d I9:BcB b E a c c c c d d d d A A B BG:G: SESEEaA|bBEaA|bBAcA|dAcA|dBcB|d

26、 BcB|d 项目集项目集I I5 5对活前缀对活前缀bcbc有效有效考虑如下规范推导考虑如下规范推导(1)(1) S S E E bB bB b bc cB B(2)(2) S S E E bB bB bcB bcB bcbccBcB(3) (3) S S E E bB bB bcB bcB bcbcd d图图5.7 p1065.7 p106识别文法识别文法活前缀的活前缀的DFADFA从初态出发从初态出发, ,经读出活经读出活前缀前缀后后, ,而到达的项而到达的项目集称为目集称为活前缀活前缀的的有效项目集有效项目集I0: SE E aA E bBI5: BcB B cB B dI3: EbB

27、 B cB B dI2:EaA A cA A dI1: S E I4:AcA A cA A dI8:Ac AI10:A d I6:EaA I7:EbBI11:B d I9:BcB b E a c c c c d d d d A A B BLR分析理论的一条基本定理 p108在任何时候，分析栈中的活前缀在任何时候，分析栈中的活前缀X X1 1X X2 2.X.Xm m的有效项目集正是栈顶状态的有效项目集正是栈顶状态S Sm m所代表的那个集合。所代表的那个集合。I0: SE E aA E bBI5: BcB B cB B dI3: EbB B cB B dI2:EaA A cA A dI1: S

28、 E I4:AcA A cA A dI8:Ac AI10:A d I6:EaA I7:EbBI11:B d I9:BcB b E a c c c c d d d d A A B B 同一个项目可能对好同一个项目可能对好几个活前缀都有效几个活前缀都有效G:G: SESEEaA|bBEaA|bBAcA|dAcA|dBcB|d BcB|d 同一个活前缀，可能存在若干个项目对它都是有效的同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。，而且告诉我们应做的事情各不相同，相互冲突。 这种冲突通过向前多看几个输入符号这种冲突通过向前多看几个输入符号, , 或许能够获

29、得或许能够获得解决。解决。移进移进- -归约冲突归约冲突 一个项目集中移进和归约项目同时存在：一个项目集中移进和归约项目同时存在：AaAaBB归约归约- -归约冲突归约冲突一个项目集中归约和归约项目同时存在一个项目集中归约和归约项目同时存在: :AABB五、五、LR(0)LR(0)分析表的构造分析表的构造LR(0)LR(0)文法文法假若一个文法假若一个文法G G的拓广文法的拓广文法G G 的活前缀识别自的活前缀识别自动机中的每个状态动机中的每个状态( (项目集项目集) )不存在下述情况不存在下述情况既含移进项目又含归约项目既含移进项目又含归约项目或者含有多个归约项目或者含有多个归约项目则称则称

30、G G是一个是一个LR(0)LR(0)文法文法。LR(0)LR(0)文法规范族的每个项目集不包含任何冲文法规范族的每个项目集不包含任何冲突项目突项目( (移进移进- -归约冲突、归约归约冲突、归约- -归约冲突归约冲突) ) 。LR(0)LR(0)分析表的构造分析表的构造假设已构造出假设已构造出LR(0)LR(0)项目集规范族为项目集规范族为: : C=IC=I0 0,I,I1 1, , I, , In n 令包含令包含SSSS 项目的集合项目的集合I Ik k的下标的下标k k为分为分析器的初始状态。析器的初始状态。a)a) 若项目若项目AAa a属于属于I Ik ,k ,且且 GO(IGO

31、(Ik k, a) = I, a) = Ij j 则置则置 ACTIONk, a ACTIONk, a 为为S Sj jb)b) 若项目若项目AA 属于属于I Ik k，则对任何终结符，则对任何终结符a a 和和# 置置ACTIONk, a ACTIONk, a 和和ACTIONk, # ACTIONk, # 为为“r rj j”, ”, j j为在文法为在文法GG中某产生式中某产生式 AA的序号。的序号。c) c) 若项目若项目 SSSS 属于属于I Ik k , , 则置则置ACTIONk, #ACTIONk, #为为“accacc”/ ”/ 接受接受d)d) 若若GO(IGO(Ik k,

32、 A), A)I Ij j，则置，则置GOTOk,AGOTOk,A 为为 j j e)e) 凡不能用上述方法填入的元素凡不能用上述方法填入的元素, ,均填上均填上“报错标志报错标志” ” / “/ “空白空白”I I0 0: : SSE E E E aA aA E E bBbBI I8 8: : B Bc cB B B B cB cB B B d dI I3 3: : E Eb bB B B B cB cB B B d dI I2 2: :E Ea aA A A A cA cA A A d dI I1 1: : S S E E I I5 5: :A Ac cA A A A cA cA A A

33、d dI I1010:A:Ac Ac AI I6 6: :A A d d I I4 4:E:EaA aA I I7 7:E:EbBbBI I9 9: :B B d d I I1111:B:BcB cB b b E E a a c c c c c c c c d d d d d d d d A A A A B B B B(0) SE (0) SE (1) EaA(1) EaA (2) EbB (2) EbB (3) AcA(3) AcA(4) Ad (4) Ad (5) BcB(5) BcB(6) Bd(6) Bd构造构造LR(0)LR(0)分析表分析表过程见黑板过程见黑板根据这种方法构造的根据这种方法构造的LR(0)LR(0)分析表不含多重分析表不含多重定义时，称这样的分析表为定义时，称这样的分析表为LR(0)LR(0)分析表分析表能用能用LR(0)LR(0)分析表的分析器称为分析表的分析器称为LR(0)LR(0)分析器分析器42可编辑