LR0项目集族和LR0分析表的构造课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《LR0项目集族和LR0分析表的构造课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- LR0 项目 分析 构造 课件
- 资源描述:
-
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补充例补充例:找出找出句型句型#abbcde#abbcde#的所有活前缀的所有活前缀
4、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#aAcde#de#移进移进8 8#aAc#aAcd de#e#归约归约 Bd9 9#aAcB
5、#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#的规范归约过程的规范归约过程S=S =aAcBe =aAcde =aAbcde =abbcde 规范规范推导推导序列序列识别句型
6、识别句型#abbcde#abbcde#所有活前缀的所有活前缀的DFADFASabaAbaAcdaAcBe确定化确定化最小化最小化0245136897SaAbcBed*bG:SaAcBeG:SaAcBe11AbAb22AAbAAb33BdBd44利用利用DFADFA进行进行移近移近-归约分析归约分析(见黑板见黑板)acebd#S A B0 2112 3434 6 556 7878 990245136897SaAbcBed*bG:SaAcBeG:SaAcBe11AbAb22AAbAAb33BdBd44r rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr rr
7、 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分析表分析表LRLR分析分析二、构造识别文法所有活前缀的二、构造识别文法所有活前缀的DFADFA 1.LR(0)1.LR(0)项目项目2.2
8、.构造识别文法所有活前缀的构造识别文法所有活前缀的DFADFA3.LR(0)3.LR(0)项目的分类项目的分类求出文法所有的活前缀求出文法所有的活前缀根据产生式得出可能出现在栈中的符号串根据产生式得出可能出现在栈中的符号串1.LR(0)1.LR(0)项目项目在文法在文法G G中每个产生式的右部适当位置添加一中每个产生式的右部适当位置添加一个圆点构成项目个圆点构成项目.对空产生式对空产生式A A,仅有项目仅有项目AA例例:产生式产生式 A A XYZ XYZ 对应的项目有对应的项目有 A AXYZXYZ A AX XYZYZA AXYXYZ Z A AXYZXYZ一个产生式可对应的项目个数是它的
9、右部符号长度加一个产生式可对应的项目个数是它的右部符号长度加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借助项目构造借助项目构造识别文法活前识别文法活前缀的缀的DFADFAG:G:S S aAd aAd A Abcbc2.2.构造识别文法所有活前缀的构造识别文法所有活前缀的DFADFA1).1).文法的每个项目都为文法的每个
10、项目都为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 4EaAEaA 13.13.EbBEbB5 5EaAEaA 14.14.BcBBcB6 6AcAAcA 15.15.BcBBcB7 7AcA AcA 16.16.BcBBcB8 8AcA AcA 17.Bd17.Bd
11、9 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+1XXn nXXA AAA状态状态i i状态状态j j出自同一产生式出自同一产生式项目项目1 1为为初态初态 P106 P106 NFANFA1 1SESE2 2SE SE 3 3EaAEaA4 4EaAEaA 5 5EaAEaA 6 6AcAAcA7
12、 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 每个状态都为每个状态都为活前缀识别态活前缀识别态 句柄识别态句柄识别态(可归前缀识别可归前缀识别态态):圆点在最后的项目圆点在最后的项目句子识别态句子识别态 aE*AcAddcBbB786341059121318161112141517p106p106识别一个文识别一个文法活前缀的法活前缀的DFADFA3).3).确定确
13、定化化 最小最小化化每个状态是一每个状态是一个项目集个项目集,称称作作LR(0)LR(0)项目集项目集整个状态集称整个状态集称为为LR(0)LR(0)项目集项目集规范族规范族3.LR(0)3.LR(0)项目的分类项目的分类移进项目移进项目:AAa a分析时把分析时把a a移进符号栈移进符号栈 待约项目待约项目:AAB B用产生式用产生式A A的右部归约时的右部归约时,首先要将首先要将B B的产生式右的产生式右部归约为部归约为B,B,对对A A的右部才能继续进行分析的右部才能继续进行分析 归约项目归约项目:AA 表明一个产生式的右部已分析完,句柄已形成可表明一个产生式的右部已分析完,句柄已形成可
14、以归约以归约 接受项目接受项目:SSSS 表明已分析成功表明已分析成功 三、三、LR(0)LR(0)项目集规范族的构造项目集规范族的构造构造识别文法活前缀构造识别文法活前缀DFADFA的三种方法的三种方法 *1.1.求出活前缀的正规表达式,然后由此正规求出活前缀的正规表达式,然后由此正规表达式构造表达式构造NFA,NFA,再确定化为再确定化为DFADFA。2.2.求出文法的所有项目,按一定规则构造识求出文法的所有项目,按一定规则构造识别活前缀的别活前缀的NFA,NFA,再确定化为再确定化为DFADFA。3.3.通过闭包函数和转换函数,直接求出通过闭包函数和转换函数,直接求出LR(0)LR(0)
15、项目集规范族,再由转换函数建立状态之间项目集规范族,再由转换函数建立状态之间的连接关系得到识别活前缀的的连接关系得到识别活前缀的DFADFA。1.1.拓广文法拓广文法2.2.项目集项目集I I的闭包函数的闭包函数 CLOSURE(I)CLOSURE(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的拓广文法。的拓广文法。使文法的开
展开阅读全文