LR项目集族和LR分析表的构造.pptx
会计学1LR项目集族和项目集族和LR分析分析(fnx)表的构造表的构造第一页，共40页。5.3 LR5.3 LR分析分析分析分析(fnx)(fnx)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 规范规范(gufn)LR(gufn)LR分析表的构造分析表的构造5.3.5 LALR5.3.5 LALR分析表的构造分析表的构造5.3.6 5.3.6 二义文法的应用二义文法的应用第1页/共40页第二页，共40页。5.3.2 LR(0)5.3.2 LR(0)项目项目项目项目(xingm)(xingm)集族集族集族集族LR(0)LR(0)分析表分析表分析表分析表的构造的构造的构造的构造一、前缀、活前缀一、前缀、活前缀 p104 p104二、构造识别文法所有活前缀的二、构造识别文法所有活前缀的DFA p104DFA p104三、三、LR(0)LR(0)项目集规范项目集规范(gufn)(gufn)族的构造族的构造 p106 p106四、有效项目四、有效项目 p108 p108五、五、LR(0)LR(0)分析表的构造分析表的构造 p109 p109第2页/共40页第三页，共40页。一、前缀一、前缀一、前缀一、前缀(qinzhu)(qinzhu)、活前缀、活前缀、活前缀、活前缀(qinzhu)(qinzhu)n n前缀前缀:符号串的头符号串的头 n n活前缀活前缀:规范句型的一个前缀规范句型的一个前缀,这种这种前缀不包含前缀不包含(bohn)(bohn)句柄之后的任何句柄之后的任何符号符号.n n*可归前缀可归前缀:包含包含(bohn)(bohn)句柄的活前句柄的活前缀缀.第3页/共40页第四页，共40页。规范规范规范规范推导推导推导推导(tu(tud d o)o)序列序列序列序列 S S=aAcBeaAcBe=aAc=aAcd de e=a=aAbAbcdecde=a=ab bbcde bcde,a,ab,a,aA,aAb,a,aA,aAc,aAcd,a,aA,aAc,aAcB,aAcBe活前缀活前缀(qinzhu)可归前缀可归前缀(qinzhu)(qinzhu)ab,aAb,aAcd,aAcBeab,aAb,aAcd,aAcBe补充例补充例:找出找出句型句型#abbcde#abbcde#的所有活前缀的所有活前缀G:SaAcBe1 Ab2 AAb3 Bd4abb c d eAABS当栈顶出现可归前缀即可归约当栈顶出现可归前缀即可归约第4页/共40页第五页，共40页。步步骤骤符号栈符号栈剩余剩余输入串输入串动作动作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#aAcde#de#移进移进8 8#aAc#aAcd de#e#归约归约 Bd9 9#aAcB#aAcBe#e#移进移进1010#aAcBeaAcBe#归约归约 SaAcBe1111#S#S#接受接受abb c d eAABS1.栈里的文法符号栈里的文法符号(fho)与剩余符号与剩余符号(fho)串一起构成串一起构成了规范句型了规范句型2.栈里的文法符号栈里的文法符号(fho)构成活前缀构成活前缀 S=aAcBe =aAcde =aAbcde =abbcde 规范规范推导推导(tudo)序列序列#abbcde#的规范的规范(gufn)归约过归约过程程第5页/共40页第六页，共40页。S=S =aAcBe =aAcde =aAbcde =abbcde 规规范范推推导导序序列列识别识别(shbi)句型句型#abbcde#所有活前缀的所有活前缀的DFASabaAbaAcdaAcBe确定确定(qudng)化化最小化最小化0245136897SaAbcBed*bG:SaAcBe1Ab 2AAb3Bd 4利用利用DFA进行进行移近移近-归约分析归约分析(fnx)(见黑板见黑板)第6页/共40页第七页，共40页。acebd#S A B0 2112 3434 6 556 7878 990245136897SaAbcBed*bG:SaAcBe1Ab 2AAb3Bd 4rrrrrrrrrrrrrrrrrrrrrrrraccSSSSSSGOTOACTION222222333333444444111111LR分析分析(fnx)表表DFA的矩阵的矩阵(j zhn)表示表示一个一个(y)LR分析器实质上是一个分析器实质上是一个(y)DFA第7页/共40页第八页，共40页。小结小结(xioji)识别识别(shbi)文法所有活前缀的文法所有活前缀的DFALR分析分析(fnx)表表LR分析分析第8页/共40页第九页，共40页。二、构造识别二、构造识别二、构造识别二、构造识别(shbi)(shbi)文法所有活前缀的文法所有活前缀的文法所有活前缀的文法所有活前缀的DFA DFA 1.LR(0)1.LR(0)项目项目2.2.构造构造(guzo)(guzo)识别文法所有活前缀的识别文法所有活前缀的DFADFA3.LR(0)3.LR(0)项目的分类项目的分类求出文法所有求出文法所有(suyu)的活前缀的活前缀根据产生式得出可能出现在栈中的符号串根据产生式得出可能出现在栈中的符号串第9页/共40页第十页，共40页。1.LR(0)1.LR(0)1.LR(0)1.LR(0)项目项目项目项目(xingm)(xingm)(xingm)(xingm)n n在文法在文法(wnf(wnf)G)G中每个产生式的右部适当位置中每个产生式的右部适当位置添加一个圆点构成项目添加一个圆点构成项目.n n对空产生式对空产生式A,A,仅有项目仅有项目AA例例:产生产生(chnshng)式式 A XYZ 对应的项目有对应的项目有 A XYZ A XYZA XYZ A XYZ一个产生式可对应的项目个数是它的右部符号长度加一个产生式可对应的项目个数是它的右部符号长度加1 1每个项目的含义与圆点的位置有关每个项目的含义与圆点的位置有关 第10页/共40页第十一页，共40页。补充补充补充补充(b(b chngchng)例例例例对应对应(duyng)(duyng)的项目的项目:(1)S(1)S aAdaAd (2)S(2)S aAd aAd (3)S(3)S aAd aAd (4)S(4)S aAd aAd (5)A(5)A bc bc (6)A(6)A bc bc (7)A(7)A bc bc借助项目借助项目(xingm)构造构造识别文法活前识别文法活前缀的缀的DFAG:S aAd Abc第11页/共40页第十二页，共40页。2.2.2.2.构造识别文法所有构造识别文法所有构造识别文法所有构造识别文法所有(suyu)(suyu)(suyu)(suyu)活前缀的活前缀的活前缀的活前缀的DFADFADFADFA1).文法的每个项目文法的每个项目(xingm)都为都为NFA的的一个状态一个状态 2).确定状态之间的转换关系确定状态之间的转换关系 3).确定化最小化确定化最小化第12页/共40页第十三页，共40页。例例例例5.8 p105 5.8 p105 G:G:SESE EaEaA A|bB|bB AcA|dAcA|d BcB|d BcB|d 更更正正(gngzhng)1SE 2SE 11.EbB3EaA 12.EbB4EaA 13.EbB5EaA 14.BcB6AcA15.BcB7AcA 16.BcB8AcA 17.Bd9Ad 18.Bd 10.Ad文法文法(wnf)(wnf)的的项目项目:1).文法的每个项目都为文法的每个项目都为NFA的一个的一个(y)状态状态第13页/共40页第十四页，共40页。2).2).确定状态确定状态确定状态确定状态(zhungti)(zhungti)之间的转换关系之间的转换关系之间的转换关系之间的转换关系X Xi iXXXX1 1X X2 2X Xi-1i-1X Xi iX Xn nXXXX1 1X X2 2X Xi iX Xi+1i+1X Xn nXXA AAA状态状态(zhungti)i状态状态(zhungti)j出自同一产生式出自同一产生式第14页/共40页第十五页，共40页。项目项目(xingm)1(xingm)1为初态为初态 P106 NFA1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad 10.Ad 11.EbB12.EbB 13.EbB14.BcB15.BcB16.BcB 17.Bd 18.Bd 每个状态每个状态(zhungti)(zhungti)都为活都为活前缀识别态前缀识别态句柄识别态句柄识别态(可归前缀识别可归前缀识别态态):):圆点在最后的项目圆点在最后的项目句子句子(j zi)(j zi)识别态识别态 aE*AcAddcBbB786341059121318161112141517第15页/共40页第十六页，共40页。p106识别一个识别一个(y(y)文法活前文法活前缀的缀的DFADFA3).确定确定(qudng)化化 最小化最小化每个状态是一个每个状态是一个项目集项目集,称作称作LR(0)项目集项目集整个整个(zhngg)状态集称为状态集称为LR(0)项目集规项目集规范族范族第16页/共40页第十七页，共40页。3.LR(0)3.LR(0)3.LR(0)3.LR(0)项目项目项目项目(xingm)(xingm)(xingm)(xingm)的分类的分类的分类的分类n n移进项目移进项目:Aa:Aan n分析时把分析时把a a移进符号栈移进符号栈 n n待约项目待约项目:AB:ABn n用产生式用产生式A A的右部归约时的右部归约时,首先要将首先要将B B的产生式的产生式右部归约为右部归约为B,B,对对A A的右部才能的右部才能(cinng)(cinng)继续继续进行分析进行分析 n n归约项目归约项目:A:A n n表明一个产生式的右部已分析完，句柄已形表明一个产生式的右部已分析完，句柄已形成可以归约成可以归约 n n接受项目接受项目:SS:SS n n表明已分析成功表明已分析成功 第17页/共40页第十八页，共40页。三、三、三、三、LR(0)LR(0)项目项目项目项目(xingm)(xingm)集规范族的构造集规范族的构造集规范族的构造集规范族的构造构造识别文法活前缀构造识别文法活前缀DFADFA的三种方法的三种方法*求出活求出活(ch hu)(ch hu)前缀的正规表达式，然后由此正规前缀的正规表达式，然后由此正规表达式构造表达式构造NFA,NFA,再确定化为再确定化为DFADFA。求出文法的所有项目，按一定规则构造识别活前求出文法的所有项目，按一定规则构造识别活前缀的缀的NFA,NFA,再确定化为再确定化为DFADFA。通过闭包函数和转换函数，直接求出通过闭包函数和转换函数，直接求出LR(0)LR(0)项目集项目集规范族，再由转换函数建立状态之间的连接关规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的系得到识别活前缀的DFADFA。第18页/共40页第十九页，共40页。1.1.拓广文法拓广文法2.2.项目项目(xingm)(xingm)集集I I的闭包函数的闭包函数 CLOSURE(I)CLOSURE(I)3.3.状态转换函数状态转换函数 GO(I,X)GO(I,X)4.4.构造文法的构造文法的LR(0)LR(0)项目项目(xingm)(xingm)集规范族集规范族第19页/共40页第二十页，共40页。1.1.1.1.拓广文法拓广文法拓广文法拓广文法(wnf)(wnf)(wnf)(wnf)n n原文法原文法G G的开始符号为的开始符号为S,S,在在G G中加中加SS SS 后得新的文法后得新的文法GG，n n 则称则称 GG为原文法为原文法G G的拓广文法。的拓广文法。n n使文法的开始符号不出现使文法的开始符号不出现(chxin)(chxin)在任何产生式右在任何产生式右部，当栈顶出现部，当栈顶出现(chxin)S,(chxin)S,则分析完成则分析完成 。n n注注:即使原开始符号即使原开始符号S S不出现不出现(chxin)(chxin)在任何产生式在任何产生式右部右部,为了统一起见也要增加该产生式。为了统一起见也要增加该产生式。第20页/共40页第二十一页，共40页。2.2.2.2.项目项目项目项目(xingm)(xingm)(xingm)(xingm)集集集集I I I I的闭包函数的闭包函数的闭包函数的闭包函数 CLOSURE(I)CLOSURE(I)CLOSURE(I)CLOSURE(I)a)I a)I 的项目均在的项目均在 CLOSURE(I)CLOSURE(I)中。中。b)b)若若ABAB属于属于CLOSURE(I),CLOSURE(I),则每一形如则每一形如 B B的项目也属于的项目也属于CLOSURE(I)CLOSURE(I)c)c)重复重复(chngf)b)(chngf)b)直到直到CLOSURE(I)CLOSURE(I)不再扩大。不再扩大。NFA:状态状态(zhungti)集合集合I的的-闭包闭包-closure(I)ABB第21页/共40页第二十二页，共40页。aE*AcAddcBbB786341059121318161112141517补充补充补充补充(b(b chngchng)例例例例I I S S E E CLOSURE(I)=SCLOSURE(I)=S E,E,EE aAaA,E E bB bB 1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad 10.Ad 11.EbB12.EbB 13.EbB14.BcB15.BcB16.BcB 17.Bd 18.Bd 1311第22页/共40页第二十三页，共40页。3.3.3.3.状态转换状态转换状态转换状态转换(zhunhun)(zhunhun)(zhunhun)(zhunhun)函数函数函数函数 GO(I,X)GO(I,X)GO(I,X)GO(I,X)GO(I,X)=CLOSURE(J)GO(I,X)=CLOSURE(J),X,X(V(VNNV VT T),),J=J=AAX X|AA X X I I X XAXAX若状态若状态(zhungti)I(zhungti)I识别活前缀识别活前缀,则状态则状态(zhungti)J(zhungti)J识别活前缀识别活前缀X X 状态状态(zhungti)I(zhungti)I状态状态J JNFA:状态集合状态集合I的的a弧转换弧转换 第23页/共40页第二十四页，共40页。aE*AcAddcBbB786341059121318161112141517补充补充补充补充(b(b chngchng)例例例例I I S S E,EE,E a aA,EA,E bBbB GO(I,a)=CLOSURE(GO(I,a)=CLOSURE(EEa a A A )=EaEa A A ,A,A cA,AcA,A d d 1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad 10.Ad 11.EbB12.EbB 13.EbB14.BcB15.BcB16.BcB 17.Bd 18.Bd 1311469第24页/共40页第二十五页，共40页。4.4.4.4.构造构造构造构造(guzo)(guzo)(guzo)(guzo)文法的文法的文法的文法的LR(0)LR(0)LR(0)LR(0)项目集规范族项目集规范族项目集规范族项目集规范族 C=I0,I1,InC=I0,I1,InC=I0,I1,InC=I0,I1,In核核:圆点不在产生式右部最左边的项目称为核圆点不在产生式右部最左边的项目称为核 a)a)置项目置项目SSSS为初态集的核，然后对核求闭包，为初态集的核，然后对核求闭包，CLOSURE(SSCLOSURE(SS）得到初态的项目集。）得到初态的项目集。b)b)对初态集或其它对初态集或其它(qt)(qt)所构造的项目集应用转换所构造的项目集应用转换函数函数GO(IGO(I，X)=CLOSURE(J)X)=CLOSURE(J)求出新状态求出新状态J J的项目集。的项目集。c)c)重复重复b)b)直到不出现新的项目为止。直到不出现新的项目为止。第25页/共40页第二十六页，共40页。算法算法算法算法(sun f)(sun f)(sun f)(sun f)Procedure itemsets(G)Procedure itemsets(G)Begin Begin C:=CLOSURE(SC:=CLOSURE(S S)S)Repeat Repeat for C for C中的每一个中的每一个I I 和每一个和每一个X do X do if GO(I,X)if GO(I,X)非空且不属于非空且不属于(sh(sh y)C then y)C then 把把GO(I,X)GO(I,X)放入放入C C中中 until Cuntil C不再增大不再增大end end p107初态的项目初态的项目(xingm)(xingm)集集 应用状态转换应用状态转换函数得到新的函数得到新的项目集项目集 第26页/共40页第二十七页，共40页。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识别文法所有识别文法所有(suyu)(suyu)活前缀的活前缀的DFADFALR(0)LR(0)项目集规范族项目集规范族 I0,I1,I11I0,I1,I11第27页/共40页第二十八页，共40页。四、有效四、有效四、有效四、有效(y(y uxio)uxio)项目项目项目项目*如果存在规范推导如果存在规范推导 则项目则项目(xingm)A(xingm)A 112 2 对活前缀对活前缀 1 1 是有效的。是有效的。如果如果2 2 ，应该移进，应该移进如果如果2=2=，应该用产生式，应该用产生式A A 1 1归约归约*RR 1 2 A S第28页/共40页第二十九页，共40页。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 A A B BG:SEEaA|bBAcA|dBcB|d 项目项目(xingm)(xingm)集集I5I5对活前对活前缀缀bcbc有效有效考虑如下考虑如下(rxi)规范推导规范推导(1)S E bB bcB(2)S E bB bcB bccB(3)S E bB bcB bcd第29页/共40页第三十页，共40页。图图5.7 p1065.7 p106识别识别(shbi)(shbi)文法文法活前缀的活前缀的DFADFA从初态出发从初态出发(chf),(chf),经经读出活前缀读出活前缀后后,而到而到达的项目集称为活前缀达的项目集称为活前缀的有效项目集的有效项目集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 A A B B第30页/共40页第三十一页，共40页。LRLR分析理论的一条基本分析理论的一条基本分析理论的一条基本分析理论的一条基本(jbn)(jbn)定理定理定理定理 p108 p108n n在任何时候，分析栈中的活前缀在任何时候，分析栈中的活前缀(qinzhu)X1X2.Xm(qinzhu)X1X2.Xm的有效项目集正是栈顶状态的有效项目集正是栈顶状态SmSm所代表的那个集合。所代表的那个集合。第31页/共40页第三十二页，共40页。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 A A B B同一个项目同一个项目(xingm)(xingm)可能对好可能对好几个活前缀都有效几个活前缀都有效G:SEEaA|bBAcA|dBcB|d 第32页/共40页第三十三页，共40页。同一个活前缀，可能存在同一个活前缀，可能存在(cnzi)(cnzi)若干个项目对它都是有若干个项目对它都是有效的，而且告诉我们应做的事情各不相同，相互冲突。效的，而且告诉我们应做的事情各不相同，相互冲突。这种冲突通过向前多看几个输入符号这种冲突通过向前多看几个输入符号,或许能够获得解决。或许能够获得解决。第33页/共40页第三十四页，共40页。n n移进移进-归约冲突归约冲突 n n一个一个(y(y )项目集中移进和归约项目集中移进和归约项目同时存在：项目同时存在：AaAan nBBn n归约归约-归约冲突归约冲突n n一个一个(y(y )项目集中归约和归约项目集中归约和归约项目同时存在项目同时存在:AAn nBB五、五、五、五、LR(0)LR(0)分析分析分析分析(fnx)(fnx)表的构造表的构造表的构造表的构造第34页/共40页第三十五页，共40页。LR(0)LR(0)文法文法文法文法(wnf(wnf)n n假若一个文法假若一个文法GG的拓广文法的拓广文法GG 的活前缀的活前缀(qinzhu)(qinzhu)识别自动机中的每个状态识别自动机中的每个状态(项目集项目集)不存在下述情况不存在下述情况n n既含移进项目又含归约项目既含移进项目又含归约项目n n或者含有多个归约项目或者含有多个归约项目n n则称则称GG是一个是一个LR(0)LR(0)文法。文法。n nLR(0)LR(0)文法规范族的每个项目集不包含任何冲突文法规范族的每个项目集不包含任何冲突项目项目(移进移进-归约冲突、归约归约冲突、归约-归约冲突归约冲突)。第35页/共40页第三十六页，共40页。LR(0)LR(0)分析分析分析分析(fnx)(fnx)表的构造表的构造表的构造表的构造假设假设(ji(ji sh)sh)已构造出已构造出LR(0)LR(0)项目集规范族项目集规范族为为:C=I0,I1,In:C=I0,I1,In 令包含令包含SS SS 项目的集合项目的集合IkIk的下标的下标k k为分析器为分析器的初始状态。的初始状态。第36页/共40页第三十七页，共40页。a)a)若项目若项目AaAa属于属于Ik ,Ik ,且且 GO(Ik,a)=Ij GO(Ik,a)=Ij 则置则置 ACTIONk,a ACTIONk,a 为为Sj Sjb)b)若项目若项目A A 属于属于IkIk，则对任何终结符，则对任何终结符a a 和和#置置ACTIONk,a ACTIONk,a 和和ACTIONk,#ACTIONk,#为为“rj”,j“rj”,j为为在文法在文法GG中某产生式中某产生式 A A的序号。的序号。c)c)若项目若项目 SS SS 属于属于Ik,Ik,则置则置ACTIONk,#ACTIONk,#为为“acc”/“acc”/接受接受d)d)若若GO(Ik,A)GO(Ik,A)Ij Ij，则置，则置GOTOk,A GOTOk,A 为为jje)e)凡不能用上述方法填入的元素凡不能用上述方法填入的元素(yun s),(yun s),均填上均填上“报错标志报错标志”/“/“空白空白”第37页/共40页第三十八页，共40页。I0:SE E aA E bBI8:BcB B cB B dI3:EbB B cB B dI2:EaA A cA A dI1:S E I5:AcA A cA A dI10:Ac AI6:A d I4:EaA I7:EbBI9:B d I11:BcB b E a c c c c d d d d A A B B(0)SE(1)EaA(2)EbB (3)AcA(4)Ad(5)BcB(6)Bd构造构造(guzo)LR(0)(guzo)LR(0)分析表分析表过程见黑板过程见黑板第38页/共40页第三十九页，共40页。n n根据这种方法构造的根据这种方法构造的LR(0)LR(0)分析表不含多重分析表不含多重定义定义(dngy)(dngy)时，称这样的分析表为时，称这样的分析表为LR(0)LR(0)分析表分析表n n能用能用LR(0)LR(0)分析表的分析器称为分析表的分析器称为LR(0)LR(0)分析器分析器第39页/共40页第四十页，共40页。
