5.3自底向上分析(Bottom-upParsing)5.3.4LR分析器——自底向上分析(Bottom-upParsing)5.3.4.2LR(0)分析器Ac.AA.cAA.ds2根据上述例子，可以总结如下：一、概念产生式右部符号被识别的多少,在产生式右部加上‘.’指示位置。项目：在文法产生式右部某个位置标有‘.’的产生式，称为文法的一个LR(0)项目。为了叙述方便，形如A.的项目称为归约项目；形如A.B的项目称为待约项目(基本项目)；形如A.a的项目称为移进项目。定义(有效项目)：项目A1.2对活前缀=1是有效的，如果存在规范推导S*Aw12w。若项目A1.B2对活前缀=1是有效的，且B是产生式，则项目B.对活前缀=1也是有效的。定义(有效项目集，项目集规范族)：文法G的某个活前缀的所有有效项目组成的集合，称为活前缀的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(J)其中J={AX.|A.XI}称函数go(I,X)为转移函数。项目AX.称为项目A.X后继。二、识别句柄和活前缀的自动机定理：对于拓广文法G的每一个活前缀，它的有效项目集恰好是从识别G活前缀的自动机的初态出发，经过路径所到达的那个状态所代表的项目集合。例：设拓广文法G[S]的产生式为：SSSaA|bBAcA|dBcB|dAc.AA.cAA.dI4三、LR分析器的结构和工作过程算法1:LR分析算法算法1:LR分析算法5.3.4.3SLR(1)分析SLR分析算法SLR(SLR(1))算法：如果文法G按上述算法构造出的分析表不存在冲突动作，则称G为SLR文法。类似地，不难定义LR(0)文法。例：设文法G[E]的产生式为I0:E.EE.E+TE.TT.T*FT.FF.(E)F.idI1(I0E):EE.EE.+TI2(I0T)(I4T):ET.TT.*FI0表4.11文法(4.22)的SLR分析表表：关于id*id+id的LR分析过程5.3.4.4LR(1)分析I1LR(1)分析表的构造LR(1)项目:由LR(0)项目和一个lookahead符号组成[A.,a]定义(LR(1)有效项目)：LR(1)项目[A.,a](aVT{#})对活前缀是有效的，如果存在规范推导S*Aww且aFirst(w#)。定理：若LR(1)项目[A.B,a]对活前缀是有效的，且B是一个产生式，则对任何bFirst(a)，项目[B.,b]也是活前缀的有效项目。例.构造文法G’[S’]的LR(1)分析表。LR(1)项目集规范族action例：构造文法SCCCcC|d的LR(1)和LALR分析表。S.S,#S.CC,#C.cC,c/dC.d,c/dI0S.SS.CCC.cCC.dI0文法的LR(1)分析表5.3.4.5LALR分析表的构造为了叙述方便，引入“同心项”和项目集的“核”的概念：定义(同心项)：如果两个LR(1)项目集去掉搜索符之后是相同的，则称这两个项目集具有相同的心。定义(核)：对于初始状态I0，有效项目[S.S,#]称为I0的核；而对于非初始状态，则其中“点不在最左端”的有效项目称为它的核。LALR分析法的基本思想：在LR(1)项目集规范族中，合并同心项以减少状态的数目；在存储LR(1)有效项目集时，仅存储其中的核。注意，由于同心项的合并，使项目的搜索符与活前缀的对应关系不唯一，降低了分析器的识别能力，参见以下两例。Cc.C,c/d/#C.cC,c/d/#C.d,c/d/#I36问题:LALR分析器识别活前缀的能力是否比LR(1)的差？例：考虑文法GSSSaAd|bBd|aBe|bAeAcBc构造G的LR(1)项目集规范族如下若将同心项I6和I9合并，则得到项目集I69:Ac.d/eBc.d/e该项目集含“归约-归约”冲突。一、LALR(1)分析表的