编译原理LR分析法ppt课件.ppt

编译原理LR分析法ppt课件.ppt

ID:50735698

大小:1.70 MB

页数:54页

时间:2020-03-16

编译原理LR分析法ppt课件.ppt_第1页
编译原理LR分析法ppt课件.ppt_第2页
编译原理LR分析法ppt课件.ppt_第3页
编译原理LR分析法ppt课件.ppt_第4页
编译原理LR分析法ppt课件.ppt_第5页
资源描述:

《编译原理LR分析法ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、7自底向上分析(Bottom-upParsing)——LR分析器17.1LR分析器——自底向上分析(Bottom-upParsing)“L”:left-to-rightscanning自左向右扫描“R”:rightmostderivationinreverse最右推导的逆5.3.4.1LR分析方法概述5.3.4.2LR(0)分析器5.3.4.3SLR(1)分析器5.3.4.4LR(1)分析器5.3.4.5LALR(1)分析器27.1.1LR(0)分析器例:考虑文法G[S] SaAAcA

2、d识别ac

3、cd是否该文法的句子。Ac.AA.cAA.ds2Sa.AA.cAA.ds1S.aAs0startAcA.s4SaA.s5Ad.s3AddAcac3Ac.AA.cAA.ds2Sa.AA.cAA.ds1S.aAs0startAcA.s4SaA.s5Ad.s3AddAcacs0accd#shifts0as1ccd#shifts0as1cs2cd#shifts0as1cs2cs2d#shifts0as1cs2cs2ds3#reduceAds0as1cs2cs2As4#

4、reduceAcAs0as1cs2As4#reduceAcAs0as1As5#reduceSaAs0S#accept动作acton栈G[S]:1:SaA2:AcA3:Adaccd∈L(G[S])?4根据上述例子,可以总结如下:一、概念产生式右部符号被识别的多少,在产生式右部加上‘.’指示位置。项目:在文法产生式右部某个位置标有‘.’的产生式,称为文法的一个LR(0)项目。为了叙述方便,形如A.的项目称为归约项目;形如A.B的项目称为待约项目(基本项目);形如A.a的项目称为

5、移进项目。5定义(有效项目):项目A1.2对活前缀=1是有效的,如果存在规范推导S*Aw12w。若项目A1.B2对活前缀=1是有效的,且B是产生式,则项目B.对活前缀=1也是有效的。据假设,存在一个规范推导S*Aw1B2w设2w*xw,则对任何B有规范推导rmS*Aw1B2w1Bxw1xw所以B.对活前缀1也是有效的。:伽马:艾塔6定义(有效项目集,项目集规范族):文法G的某个活前缀的所有有效

6、项目组成的集合,称为活前缀的LR(0)有效项目集。文法G的所有有效项目集组成的集合,称为G的LR(0)项目集规范族。7定义(项目闭包):设I是文法G的一个LR(0)项目集合,I的项目闭包closure(I)定义如下:1、Iclosure(I)。2、若项目A.Bclosure(I),且B是G的产生式,则项目B.closure(I)。3、closure(I)仅包含上述两条规则确定的LR(0)项目。8定义(转移函数):若I是文法G的一个LR(0)项目集,X是G中的文法符号。定义go(I

7、,X)=closure(J)其中J={AX.

8、A.XI}称函数go(I,X)为转移函数。项目AX.称为项目A.X后继。9二、识别句柄和活前缀的自动机若文法G=(VT,VN,S,P),则识别G的句柄的自动机为DFAM=(=VTVN,Q=G的LR(0)项目集规范族,q0=closure({S.S}),F=所有含归约项目的有效项目集组成的集合,=go(I,X))。若将所有状态均视为终态,则识别活前缀的自动机DFAM=(=VTVN,Q=G的LR(0)项目集规范族,q0

9、=closure({S.S}),F=Q,=go(I,X))。10定理:对于拓广文法G的每一个活前缀,它的有效项目集恰好是从识别G活前缀的自动机的初态出发,经过路径所到达的那个状态所代表的项目集合。11例:设拓广文法G[S]的产生式为:SSSaA

10、bB AcA

11、d BcB

12、dLR(0)项目集规范族I0:S.SS.aAS.bBI1:(I0,S)SS.I2:(I0,a)Sa.AA.cAA.dI3:(I0,b)Sb.BB.cBB.dI4:(I2,c)(I4,

13、c)Ac.AA.cAA.dI5:(I3,c)(I5,c)Bc.BB.cBB.dI6:(I2,A)SaA.I7:(I3,B)SbB.I8:(I4,A)AcA.I9:(I5,B)BcB.I10:(I4,d)Ad.I11:(I3,d)Bd.12Ac.AA.cAA.dI4Sa.AA.cAA.dI2Sb.BB.cBB.dI3Bc.BB.cBB.dI5S.SS.aAS.bBI0startSS.I1AcA.

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。