LR项目集族和LR分析表构造

1、第五章第五章 语法分析语法分析5.1 自下而上分析基本问题自下而上分析基本问题5.2 算符优先分析算符优先分析 5.3 LR分析分析5.4 YACC5.3 LR分析分析5.3.1 LR分析器分析器5.3.2 LR(0)项目集族项目集族LR(0)分析表的构造分析表的构造5.3.3 SLR分析表的构造分析表的构造5.3.4 规范规范LR分析表的构造分析表的构造5.3.5 LALR分析表的构造分析表的构造5.3.6 二义文法的应用二义文法的应用5.3.2 LR(0)项目集族项目集族LR(0)分析表的构造分析表的构造一、前缀、活前缀一、前缀、活前缀 p104p104二、构造识别文法所有活前缀的二、构造

2、识别文法所有活前缀的DFA DFA p104p104三、三、LR(0)LR(0)项目集规范族的构造项目集规范族的构造 p106p106四、有效项目四、有效项目 p108p108五、五、LR(0)LR(0)分析表的构造分析表的构造 p109p109一、前缀、活前缀一、前缀、活前缀 前缀前缀 : 符号串的头符号串的头 活前缀活前缀 : 规范句型的一个前缀规范句型的一个前缀, 这种前这种前缀不包含句柄之后的任何符号缀不包含句柄之后的任何符号.*可归前缀可归前缀: 包含句柄的活前缀包含句柄的活前缀.规范规范推导推导序列序列 S =aAcBe=aAcde=aAbcde=abbcde ,a,ab,a,aA

3、,aAb ,a,aA,aAc,aAcd,a,aA,aAc,aAcB,aAcBe活前缀活前缀可归前缀可归前缀ab , aAb, aAcd , aAcBe补充例补充例: 找出找出句型句型 #abbcde# #abbcde# 的所有活前缀的所有活前缀G:SaAcBe1 Ab2 AAb3 Bd4abb c d eAABS当栈顶出现可归前缀即可归约当栈顶出现可归前缀即可归约步步骤骤符号栈符号栈剩余剩余输入串输入串动作动作1 1# #abbcde#abbcde# 移进移进2 2#a#abbcde#bbcde# 移进移进3 3#ab#abbcde#bcde# 归约归约 Ab4 4#aA#aAbcde#bcd

4、e# 移进移进5 5#aAb#aAbcde#cde# 归约归约 AAb6 6#aA#aAcde#cde# 移进移进7 7#aAc#aAcde#de# 移进移进8 8#aAcd#aAcde#e# 归约归约 Bd9 9#aAcB#aAcBe#e# 移进移进1010 #aAcBe#aAcBe# # 归约归约 SaAcBe1111 #S#S# # 接受接受abb c d eAABS 栈里的文法符号与栈里的文法符号与剩余符号串一起构剩余符号串一起构成了规范句型成了规范句型 栈里的文法符号构栈里的文法符号构成活前缀成活前缀 S =aAcBe =aAcde =aAbcde =abbcde 规范规范推导推导序

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

6、rrrrrrrrraccSSSSSSGOTOACTION222222333333444444111111LR分析表分析表DFA的矩阵表示的矩阵表示一个一个LR分析器实质上是一个分析器实质上是一个DFA 小结识别文法所有活前缀的识别文法所有活前缀的DFALR分析表分析表LR分析分析二、构造识别文法所有活前缀的二、构造识别文法所有活前缀的DFA 1. LR(0)1. LR(0)项目项目2. 2. 构造识别文法所有活前缀的构造识别文法所有活前缀的DFADFA3. LR(0)3. LR(0)项目的分类项目的分类求出文法所有的活前缀求出文法所有的活前缀根据产生式得出可能出现在栈中的符号串根据产生式得出可

7、能出现在栈中的符号串1. LR(0)1. LR(0)项目项目在文法在文法G中每个产生式的右部适当位置添加一中每个产生式的右部适当位置添加一个圆点构成项目个圆点构成项目. 对空产生式对空产生式A , 仅有项目仅有项目A例例: 产生式产生式 A XYZ 对应的项目有对应的项目有 AXYZ AXYZAXYZ AXYZ一个产生式可对应的项目个数是它的右部符号长度加一个产生式可对应的项目个数是它的右部符号长度加1 1每个项目的含义与圆点的位置有关每个项目的含义与圆点的位置有关 补充例补充例对应的项目对应的项目: (1)SaAd (2)S aAd (3)S aAd (4)S aAd (5)Abc (6)A

8、 bc (7)A bc借助项目构造借助项目构造识别文法活前识别文法活前缀的缀的DFAG: S aAd Abc2. 2. 构造识别文法所有活前缀的构造识别文法所有活前缀的DFADFA1). 文法的每个项目都为文法的每个项目都为NFA的一个状态的一个状态 2). 确定状态之间的转换关系确定状态之间的转换关系 3). 确定化最小化确定化最小化例例5.8 p105 G: SE EaA|bB AcA|d BcB|d 更更正正1SE 2SE 11. EbB3EaA 12. EbB4EaA 13. EbB5EaA 14. BcB6AcA15. BcB7AcA 16. BcB8AcA 17. Bd9Ad 18

9、. Bd 10. Ad文法的项目文法的项目: :1). 文法的每个项目都为文法的每个项目都为NFA的一个状态的一个状态2). 确定状态之间的转换关系确定状态之间的转换关系X Xi iXXXX1 1X X2 2X Xi-1i-1X Xi iX Xn nXXXX1 1X X2 2X Xi iX Xi+1i+1X Xn nXXAAAA状态状态i状态状态j出自同一产生式出自同一产生式项目项目1 1为初态为初态 P106 NFA1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad 10. Ad 11. EbB12. EbB 13. EbB14. BcB15. BcB16. BcB

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

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

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

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

14、数的闭包函数 CLOSURE(I)CLOSURE(I)a) I 的项目均在的项目均在 CLOSURE(I) 中。中。b) 若若AB属于属于CLOSURE(I), 则每一形如则每一形如 B的项目也属于的项目也属于CLOSURE(I)c) 重复重复b)直到直到CLOSURE(I)不再扩大。不再扩大。 NFA : 状态集合状态集合I的的-闭包闭包 -closure(I)ABBaE*AcAddcBbB786341059121318161112141517补充例补充例I SE CLOSURE(I) = SE, EaA, EbB 1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad

15、10. Ad 11. EbB12. EbB 13. EbB14. BcB15. BcB16. BcB 17. Bd 18. Bd 13113.3.状态转换函数状态转换函数 GO(I, X)GO(I, X)GO(I, X) = CLOSURE(J), X(VNVT) , J = AX| AXI X XAXAX若状态若状态I I识别活前缀识别活前缀,则状态则状态J J识别活前缀识别活前缀XX 状态状态I I状态状态J JNFA : 状态集合状态集合I的的a弧转换弧转换 aE*AcAddcBbB786341059121318161112141517补充例补充例I SE , EaA , EbB GO(

16、I, a) = CLOSURE( EaA )= EaA , AcA, Ad 1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad 10. Ad 11. EbB12. EbB 13. EbB14. BcB15. BcB16. BcB 17. Bd 18. Bd 13114694.4.构造文法的构造文法的LR(0)LR(0)项目集规范族项目集规范族 C=IC=I0 0,I,I1 1,I,In n 核核: 圆点不在产生式右部最左边的项目称为核圆点不在产生式右部最左边的项目称为核 a) 置项目置项目SS为初态集的核，然后对核求闭为初态集的核，然后对核求闭包，包，CLOSURE(S

17、S）得到初态的项目）得到初态的项目集。集。b) 对初态集或其它所构造的项目集应用转换函对初态集或其它所构造的项目集应用转换函数数GO(I，X)=CLOSURE(J)求出新状态求出新状态J的的项目集。项目集。c) 重复重复b)直到不出现新的项目为止。直到不出现新的项目为止。算法算法Procedure itemsets(G) Begin C:= CLOSURE(SS ) Repeat for C中的每一个中的每一个I 和每一个和每一个X do if GO(I, X)非空且不属于非空且不属于C then 把把GO(I, X)放入放入C中中 until C不再增大不再增大end p107初态的项目集初

18、态的项目集 应用状态转换应用状态转换函数得到新的函数得到新的项目集项目集 G: SE EaA|bB AcA|d BcB|d I0: SE E aA E bBI8: BcB B cB B dI3: EbB B cB B dI2:EaA A cA A dI1: S EI5:AcA A cA A dI10:Ac AI6:A dI4:EaAI7:EbBI9:B dI11:BcB b E a c c c c d d d d A A B B识别文法所有活前识别文法所有活前缀的缀的DFADFALR(0)LR(0)项目集规范族项目集规范族 II0 0,I,I1 1, , I, I1111 四、有效项目四、有效

19、项目 *如果存在规范推导如果存在规范推导 则项目则项目A 1 2 对活前缀对活前缀 1 是是有效的有效的。o如果如果 2 ，应该移进，应该移进o如果如果 2 = = ，应该用产生式，应该用产生式A 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: SEEaA|bBAcA|dBcB|d 项目集项目

20、集I I5 5对活前缀对活前缀bc有效有效考虑如下规范推导考虑如下规范推导(1) S E bB bcB(2) S E bB bcB bccB(3) S E bB bcB bcd图图5.7 p1065.7 p106识别文法识别文法活前缀的活前缀的DFADFA从初态出发从初态出发, ,经读出活经读出活前缀前缀后后, ,而到达的项而到达的项目集称为活前缀目集称为活前缀的的有效项目集有效项目集I0: 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:Ea

21、A I7:EbBI11:B d I9:BcB b E a c c c c d d d d A A B BLR分析理论的一条基本定理 p108在任何时候，分析栈中的活前缀在任何时候，分析栈中的活前缀X1X2.Xm的有效项目集正是栈顶状态的有效项目集正是栈顶状态Sm所代表的那个集合。所代表的那个集合。I0: 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

22、A A B B 同一个项目可能对好同一个项目可能对好几个活前缀都有效几个活前缀都有效G: SEEaA|bBAcA|dBcB|d 同一个活前缀，可能存在若干个项目对它都是有效的同一个活前缀，可能存在若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。，而且告诉我们应做的事情各不相同，相互冲突。 这种冲突通过向前多看几个输入符号这种冲突通过向前多看几个输入符号, , 或许能够获得或许能够获得解决。解决。移进移进-归约冲突归约冲突 一个项目集中移进和归约项目同时存在：一个项目集中移进和归约项目同时存在：AaB归约归约-归约冲突归约冲突一个项目集中归约和归约项目同时存在一个项目集中归约和归约项目同时存在:AB五、五、LR(0)分析表的构造分析表的构造LR(0)文法文法假若一个文法假若一个文法G的拓广文法的拓广文法G 的活前缀识别自的活前缀识别自动机中的每个状态动机中的每个状态(项目集项目集)不存在下述情况不存在下述情况既含移进项目又含归约项目既含移进项目又含归约项目或者含有多个归约项目或者含有多个