编译原理compiler5_语法分析_2.ppt

《编译原理compiler5_语法分析_2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、5.3自底向上分析(Bottom-upParsing)——LR分析器5.3.4LR分析器——自底向上分析(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)分析器5.3.4.2LR(0)分析器例：考虑文法G[S]SaAAcA

2、d识别

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

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

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也是有效的。：伽马：艾塔定义(有效项目集，项目集规范族)：文法G的某个活前缀的所有有效项目组成的集合，

6、称为活前缀的LR(0)有效项目集。文法G的所有有效项目集组成的集合，称为G的LR(0)项目集规范族。定义(项目闭包)：设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)项目。定义(转移函数)：若I是文法G的一个LR(0)项目集，X是G中的文法符号。定义go(I,X)=closure(

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

8、A.XI}称函数go(I,X)为转移函数。项目AX.称为项目A.X后继。二、识别句柄和活前缀的自动机若文法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=closure({S.S

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

10、bBAcA

11、dB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,c)Ac.AA.cAA.dI5:(I3,

13、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.Ac.AA.cAA.dI4Sa.AA.cAA.dI2Sb.BB.cBB.dI3Bc.BB.cBB.dI5S.SS.aAS.bBI0startSS.I1AcA.I8SaA.I6A