LR项目集族和LR分析表的构造.pptx
《LR项目集族和LR分析表的构造.pptx》由会员分享,可在线阅读,更多相关《LR项目集族和LR分析表的构造.pptx(40页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、会计学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、.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页。一、前缀一、前缀一、前缀一、前缀(q
3、inzhu)(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
4、,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#移
5、进移进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)构成
6、活前缀构成活前缀 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
7、页/共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、析第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)项目项目项目项目(xi
9、ngm)(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
10、)例例例例对应对应(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)活前缀的活前缀的活前缀的活前缀的DFADFADFADF
11、A1).文法的每个项目文法的每个项目(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)
12、.文法的每个项目都为文法的每个项目都为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 NFA1
13、SE2SE 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).确
14、定确定(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的产生式的产生式右部归约为右部
15、归约为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)前缀的正规
16、表达式,然后由此正规前缀的正规表达式,然后由此正规表达式构造表达式构造NFA,NFA,再确定化为再确定化为DFADFA。求出文法的所有项目,按一定规则构造识别活前求出文法的所有项目,按一定规则构造识别活前缀的缀的NFA,NFA,再确定化为再确定化为DFADFA。通过闭包函数和转换函数,直接求出通过闭包函数和转换函数,直接求出LR(0)LR(0)项目集项目集规范族,再由转换函数建立状态之间的连接关规范族,再由转换函数建立状态之间的连接关系得到识别活前缀的系得到识别活前缀的DFADFA。第18页/共40页第十九页,共40页。1.1.拓广文法拓广文法2.2.项目项目(xingm)(xingm)集集I
17、 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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- LR 项目 分析 构造
限制150内