《编译原理课程教案》第4章：LR分析方法.ppt

LR分析方法,第四章（3）,本章要求,主要内容：LR分析方法及其相关概念，语法分析器的自动生成，各种语法分析中的错误处理重点掌握：LR分析方法与分析过程，活前缀、LR(0)项目、Closure 和 go函数的定义，项目集规范族及识别活前缀的有穷自动机的构造，LR(0)分析表的构造，SLR文法及其分析表的构造。,LR分析概述,LR分析法：L从左向右扫描输入串，R构造最右推导的逆过程大多数用上下文无关文法描述的高级语言的语法成分可以用LR分析器来识别。LR分析：采用移进-归约分析，严格的规范归约。LR分析根据当前分析栈中的符号串和向右顺序查看输入串的K(K0)个符号就可以唯一确定分析的动作是移进还是归约。向前查看0个符号，就是LR(0)分析方法，向前查看1个符号，就是LR(1)方法。,LR分析的优缺点,优点：比其他“移进-归约”方法使用广泛，识别率高能用LL(1)分析法分析的所有文法都能使用LR方法来进行分析。LR分析法在扫描输入串时就能发现其中的任何错误，并能准确地指出出错位置。缺点：手工构造分析表工作量太大。必须使用自动生成器。,自底向上分析法的关键问题是如何确定句柄。LR分析法与算符优先方法一样，LR方法也是通过求句柄逐步归约来进行语法分析。在算符优先分析中，通过算符的优先关系得到句柄“最左素短语”，LR方法中句柄是通过识别活前缀而求得。,LR分析方法的基本思想是：在规范归约过程中，一方面记住已移进和归约出的整个符号串(历史)，另一方面又根据所用产生式推测未来可能碰到的输入符号(对未来的展望)。当某一符号串类似于句柄出现在栈顶时，需要根据已记载的“历史”、“展望”和“现实”的输入符号三方面的内容来决定栈顶的符号串是否构成了真正的句柄，是否需要归约。一个LR分析器的组成见下图。,1、LR分析方法的逻辑结构,一个LR分析器由3个部分组成：LR分析程序，又称总控程序。所有的LR分析器都是相同的。分析表(分析函数)，不同的文法分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。,状态栈：(S0,#)为预先放到栈中的初始状态和符号。,文法符号：X1X2Xm是目前已移进并归约出的句型部分。其实它是多余的，已经概括到状态里。,分析器实际上是一个带有先进后出栈的确定的有穷自动机。将“历史”和“展望”综合成“状态”，分析栈用来存放状态，状态概括了从分析开始直到某一归约阶段的全部历史和展望资料，不必象算符优先分析法中要翻阅栈中的内容才能决定是否要进行归约。只需根据栈顶状态和输入符号就可以唯一决定下一个动作。,总控程序根据分析表的内容来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。LR方法：根据具体文法的分析表对输入串进行分析处理。LR分析过程：在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和当前输入符号，按分析表中的内容完成相应的分析工作。,2.分析表的组成：,表中actionSi,aj，指出如果当前栈顶为状态Si，输入符号为aj时应执行的动作。其动作有四种可能，分别为：移进(S)、归约(r)、接受(acc)、出错(error)。,(1)分析动作表Action是一个二维数组,表中gotoSi,xj指出状态为Si，遇到Xj时应转到的下一状态。显然：分析表定义了一个以文法符号为字母表的DFA,(2)状态转换表goto 也是一个二维数组,ri表示按第i个产生式进行归约,Si表示把当前输入符号移进栈，第i个状态进状态栈。,i表示转第i个状态，即第i个状态进状态栈。,空白表示分析动作出错,例：LR的Action和GoTo表,(1)E E+T(2)E T(3)T T*F(4)T F(5)F(F)(6)F i,产生式的序号,设文法为GL：,用三元式:(状态栈，符号栈，输入符号串)表示分析过程中状态栈，符号栈，输入符号串的变化初始时，将状态S0和#进分析栈。三元式为：(S0,#,a1a2an#)任一时刻的三元式为：(S0S1Sm,#X1X2Xm,aiai+1an#)分析器的下一步动作是由栈顶状态Sm和当前面临的输入符号ai唯一确定的。,3、LR分析过程：,移进：当前输入符号ai移进符号栈，将action表中指出的状态S进状态栈。(S0S1SmS,#X1X2Xmai,ai+1an#),根据Sm和ai查action表,actionSm,ai有4种情况：,出错：报告出错信息。三元式的变化过程终止。,接受：分析成功，终止分析。三元式不再变化。,归约：若产生式A的右端长度为r，则两个栈顶的r个元素同时出栈，A进符号栈;再根据Sm-r和A查goto表，S=gotoSm-r,A进状态栈。三元式变为：(S0S1 Sm-r S,#X1X2Xm-rA,aiai+1an#),LR分析器示例：,文法G(E)：(1)EET(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi,其LR分析表为:,sj:：把下一状态j和现行输入符号a移进桟。,rj:：按第j个产生式进行规约。,acc：接受。,空白格：出错标志。,若a为终结符，则GOTOs，a的值已列在ACTIONs，a的sj之中（状态j），因此，GOTO表仅对所有非终结符A列出GOTOs，A的值。,假定输入串为i*i+i，LR分析器的工作过程:步骤状态桟 符号桟输入串(1)0#i*i+i#(2)05#i*i+i#(3)03#F*i+i#(4)02#T*i+i#(5)027#T*i+i#,i,*,归约 指用某产生式A进行归约.假若的长度为r，归约动作是，去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r,A)的下一状态s=GOTOsm-r,A和文法符号A推进栈。,假定输入串为i*i+i，LR分析器的工作过程:步骤状态符号输入串(5)027#T*i+i#(6)0275#T*i+i#(7)02710#T*F+i#(8)02#T+i#(9)01#E+i#(10)016#E+i#,+,i,步骤状态符号输入串(10)016#E+i#(11)0165#E+i#(12)0163#E+F#(13)0169#E+T#(14)01#E#(15)接受,+,i,i,为了介绍LR分析过程，直接给出该文法的分析表，以后再介绍如何生成,例：LR的具体分析过程：,(1)E E+T(2)E T(3)T T*F(4)T F(5)F(F)(6)F i,设文法为GL：,根据上述分析表，对输入串 i*i+i 的分析过程如下：,LR文法：对一个文法，如果能够构造一个分析表，且它的每个入口均是唯一的如何构造LR分析表？,4.3.1 LR(0)项目集族和LR(0)分析表的构造,假定是文法G的一个句子，我们称序列 n，n-1，0 是的一个规范归约，如果此序列满足：1 n=2 0为文法的开始符号，即0=S 3 对任何i，0 i n，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,LR(0)分析就是在分析的每一步，只需根据当前桟顶状态而不必向前查看输入符号就能确定应采取的分析动作。,规范归约过程中栈内的符号串和扫描剩下的输入符号串构成了一个规范句型。栈内的如果出现句柄（最左直接短语），句柄一定在栈的顶部。,栈内永远不会出现句柄之后的符号！,字的前缀：是指字的任意首部，如字abc的前缀有，a，ab，abc活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型，为句柄，如果=u1u2ur，则符号串u1u2ui(1ir)是的活前缀。(必为终结符串)。在LR分析工作过程中的任何时候，桟里的文法符号（自桟底而上）X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。,引入一个新的概念：规范句型的活前缀,为什么？,因为首先规约的是句柄。,为什么要引入活前缀的概念？,因为句柄是活前缀的后缀，识别活前缀就可以找到句柄；找到了句柄，就可以对句柄归约。,对于一个文法G,可以构造一个有限自动机DFA,它能识别G的所有活前缀。在这个基础上，我们再研究如何把这种自动机转变成LR分析表。,构造LR(0)分析表的基本思想是：从给定的上下文无关文法直接构造识别文法所有规范句型的活前缀的DFA，然后再将DFA转换为一张LR(0)分析表。,文法G的每个产生式的右部添加一个圆点称为G的一个LR(0)项目（简称项目）。如:AXYZ有四个项目：A.XYZ AX.YZ AXY.Z AXYZ.一个项目指明了在分析过程的某个时刻看到产生式的多大一部分。为什么要引入项目的概念？,LR(0)项目,为什么要引入项目的概念？,活前缀与句柄之间的关系有三种情况：活前缀中已含有句柄的全部符号，表明此时某一规则A的右部符号串已出现在桟顶，其相应的分析动作是用此规则进行规约。(2)活前缀中只含句柄的一部分符号，此时意味着形如A12规则的右部子串1已出现在桟顶，正期待着从剩余的输入串中移进2；(3)活前缀中全然不含有句柄的任何符号，此时意味着期望从剩余输入串中能看到由某规则A的右部所推出的符号串。为了刻画在分析过程中，文法的某一规则的右部符号串已有多大一部分被识别，我们可在文法的每个规则的右部适当位置上加一个圆点来表示。针对上述活前缀与句柄之间关系的三种情况，标有圆点的规则分别是：(1)A.(2)A1.2(3)A.,由于不同的LR(0)项目反映了在分析过程中桟顶的不同状态，因此，可以根据圆点的位置和圆点后是终结符还是非终结符，将一个文法的全部LR(0)项目进行分类（4类）：(1)A.称为“归约项目”规约项目表示文法的某一个规则的右部已分析完，句柄已形成，应按次规则进行规约。(2)归约项目 S.称为“接受项目”接受项目是对文法开始符号的规约项目。(3)A.a(aVT)称为“移进项目”移进项目表示期待从输入串中移进一个符号，以待形成句柄。(4)A.B(BVN)称为“待约项目”.待约项目表示期待从剩余的输入串中规约而得到B，然后才能继续分析A的右部。,文法G(S)SE EaA|bB AcA|d BcB|d 该文法的项目有：1.SE2.SE3.EaA 4.EaA5.EaA6.AcA7.AcA8.AcA9.Ad 10.Ad11.EbB12.EbB13.EbB14.BcB15.BcB 16.BcB17.Bd18.Bd,有效项目,我们说项目A 1.2对活前缀1是有效的，其条件是存在规范推导,指规范推导。,有效项目中的圆点“.”,意味着对应产生式中的“.”所在处就是这个活前缀的终止点。,项目A1.2对活前缀1有效，具有两层含意：从文法开始符号，经1可到达该项目(项目所在状态)；在当前活前缀的情况下，该项目可指导下一步分析动作(A=12)。,有效项目的意义：1.到目前为止分析是正确的；2.指导下一步的分析：(1)规约项目A1.对活前缀1是有效的，意味着我们应把符号串1规约为A，即把活前缀1变成A；(2)移进项目A1.2对活前缀1是有效的，意味着句柄尚未形成，下一步动作应是移进。,活前缀与项目的关系：一个项目可能对若干个活前缀有效 项目A1.2对所有从初态出发可以到达此项目的路径上的标记均有效（一个路径标记是一个活前缀）。若干个项目可能对同一个活前缀有效 项目集中的所有项目对同一活前缀均有效。,综合可知：同一项目集中的所有项目，对此项目集的所有活前缀均有效。即，项目集中的每个项目均有同等权利指导下一步动作。,同一项目可能对好几个活前缀都是有效的，此时，该项目出现在好几个不同的LR(0)项目集中。（用子集法对NFA的确定化过程中，某个状态会出现在多个状态子集中吗？）同一活前缀，是否存在多个项目对它都是有效的？如果存在的话，并且不同项目告诉我们应做的事情各不相同，就会产生冲突。这种冲突通过向前多看几个输入符号，或许能够解决，这种情形就是LR(K)文法；对于非LR文法，不论超前看几个输入符号都绝对无法解决冲突。,在识别活前缀的DFA中，一个活前缀的有效项目集就是从该DFA的初态出发，经读出后而到达的那个项目集（状态）。换言之，在任何时候，分析栈中的活前缀X1X2 Xm的有效项目集正是栈顶状态Sm所代表的那个集合。也正是从识别活前缀的DFA的初态出发，读出X1X2 Xm后到达的那个项目集(状态)。即，桟顶的项目集（状态）体现了桟里的一切有用信息历史。（这是LR分析理论的一条基本定理。）,文法G(S)SE EaA|bB AcA|d BcB|d 考虑：在该文法的活前缀识别自动机DFA（见前图）中，符号串bc是一个活前缀，这个DFA（见前图）在读出这个串后到达状态5。状态5含有三个项目：B c.BB.cB B.D，我们分析这个项目集对bc的有效性。S E bB bcB（表明B c.B 的有效性。）S E bB bcB bccB（表明B.cB的有效性。）S E bB bcB bcd（表明B.d 的有效性。）,项目A 1.2对活前缀1是有效的，其条件是存在规范推导,对于一个文法G,可以构造一个有限自动机DFA,它能识别G的所有活前缀。在这个基础上，我们再研究如何把这种自动机转变成LR分析表。,构造LR(0)分析表的基本思想是：从给定的上下文无关文法直接构造识别文法所有规范句型的活前缀的DFA，然后再将DFA转换为一张LR(0)分析表。,步骤一：构造识别文法所有活前缀的NFA,我们可以使用文法的LR(0)项目构造一个NFA，用来识别这个文法的所有活前缀。构造方法如下：(1)规定文法中开始符号S仅在第一个产生式左部出现(拓广文法)，将含有S的并且圆点出现在最左边的项目作为NFA的唯一初态；(2)文法的任何项目均认为是NFA的状态（活前缀识别态）；(3)规定所有那些圆点出现在最右边的项目为NFA的终态（句柄识别态）；,(4)如果状态i和j出自同一产生式，而且状态j的圆点只落后于状态i的圆点一个位置，如状态i为 XX1 Xi-1.Xi Xn 而状态j为XX1 Xi-1Xi.Xi+1 Xn，则从状态i画一条标志为Xi的有向边到状态j；(5)若状态i为X.A，A为非终结符，则从状态i画一条边到所有状态A.（即，所有那些圆点出现在最左边的A的项目）。,6:AcA,7:AcA,8:AcA,9:Ad,10:Ad,4:EaA,5:EaA,3:EaA,2:SE,11:EbB,12:EbB,13:EbB,14:BcB,15:BcB,16:BcB,18:Bd,17:Bd,识别活前缀的NFA,1:SE,文法G：SE EaA|bB AcA|d BcB|d,6,7,8,9,10,4,5,3,1,2,11,12,13,14,15,16,18,17,a,A,E,b,B,B,c,A,c,d,识别活前缀的NFA,句柄识别态（即，这个活前缀的后半截含有句柄。）,即：每个产生式是一个识别活前缀的NFA；每个项目是NFA的一个状态。,于是：所有产生式构成文法G识别活前缀的NFA集合。,使用第二章介绍的子集法，可以将识别活前缀的NFA确定化，使之成为一个以项目集合为状态的DFA。这个DFA就是建立LR分析算法的基础。,步骤二：把识别文法所有活前缀的NFA确定化。,这个DFA就是建立 LR(0)分析表的基础。,构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族。这个规范族是建立LR(0)分析表的基础。,LR(0)项目集规范族,LR(0)项目集规范族的另一个构造方法,先假定文法G是一个以S为开始符号的文法，我们构造一个G，它包含了整个G，但它引进了一个不出现在G中的非终结符S，并加进一个新产生式SS，而这个S是G的开始符号。那么，我们称G是G的拓广文法。这样，便会有一个仅含项目SS.的状态，这就是唯一的“接受”态。,前述构造LR(0)项目集规范族的方法是：列出拓广文法的所有项目，按规定原则构造其NFA，然后再确定化为DFA，该DFA的所有状态即为该文法的LR(0)项目集规范族。这种方法的工作量很大。我们现在研究一种新的更为简单直接的方法来构造LR(0)项目集规范族。,我们发现如下规律：若状态中包含形如AB的待约项目，则形如B的项目也在此状态内。例如0状态中项目集为：SE，EaA，EBb,我们研究识别活前缀的DFA，分析其每个状态中项目集的构成。,回顾NFA的构造规则中，(5)若状态i为X.A，A为非终结符，则从状态i画一条边到所有状态A.。这与第三章中介绍的-闭包概念是一致的。即EaA和EbB正是属于SE的闭包中。因而，我们也可用闭包函数来求DFA中一个状态的项目集。,假定I是文法G的任一项目集，定义和构造I的闭包CLOSURE(I)如下：1.I的任何项目都属于CLOSURE(I)；2.若AB属于CLOSURE(I)，那么，对任何关于B的产生式B，项目B也属于CLOSURE(I)；3.重复执行上述两步骤直至CLOSURE(I)不再增大为止。,P50：NFA确定化设I是的状态集的一个子集，定义I的-闭包-closure(I)为:i)若sI，则s-closure(I)；ii)若sI，则从s出发经过任意条弧而能到达的任何状态s都属于-closure(I)-closure(I)=Is|从某个sI出发经过任意条弧能到达s,2.若状态i为X.A，A为非终结符，则从状态i画一条边到所有状态A.。,用上述方法，我们可以很容易构造出初态的项目集，即SS属于I，再按上述三点求其闭包。有了初态的项目集，其它状态的项目集如何求出？回顾在构造识别活前缀的NFA时，除了箭弧上标记为的外，其它两个相邻状态对应的项目都是出自同一个产生式，只是圆点的位置相差1。箭弧上的标记为前一个状态和后一个状态对应项目的圆点间的符号。,(4)如果状态i和j出自同一产生式，而且状态j的圆点只落后于状态i的圆点一个位置，如状态i为 XX1 Xi-1.Xi Xn 而状态j为XX1 Xi-1Xi.Xi+1 Xn，则从状态i画一条标志为Xi的有向边到状态j；,而识别活前缀的DFA的每个状态是一个项目集，项目集中的每个项目都不相同，每个项目圆点后的符号不一定相同，因而对每个项目圆点移动一个位置后，箭弧上的标记也不会完全相同，这样，对于不同的标记将转向不同的状态。例如初态SE，EaA，EbB 对第一个项目圆点右移一个位置后变为SE箭孤标记应为E，对第二个项目EaA，圆点有移一个位置后，项目变为EaA，箭弧标记为a，同样第三个项目为圆点右移一个位置后变为EbB，箭弧标记为b。,显然，初态可发出三个不同标记的箭弧，因而转向三个不同的状态，也就由初态派生出三个新的状态。对于每个新的状态我们又可以利用前面的方法，若圆点后为非终结符则可对其求闭包，得到该状态的项目集。圆点后面为终结符或在一个产生式的最后，则不会再增加新的项目。例中新状态的项目EaA求其闭包可得到项目集为EaA，AcA，Ad。同样，另一新状态的项目EbB，求其闭包得到项目集为EbB，BcB，Bd，对于新状态仅含项目为SE的则不会再增加新的项目。,这样我们由初态出发对其项目集的每个项目的圆点向右移动一个位置，用箭弧转向不同的新状态，箭弧上用移动圆点经过的符号标记。新状态的初始项目即圆点移动后的项目称为核。例如AaA和BbB都为核，对核求闭包就为新状态的项目集。为把这个过程写成一般的形式，我们定义转换函数GO(I，X)。,为了识别活前缀，我们定义一个状态转换函数GO(I,X)。设I是一个项目集，X是一个文法符号。函数值GO(I，X)定义为：GO(I，X)CLOSURE(J)其中 J任何形如AX的项目|A X属于I。直观上说，若I是对某个活前缀 有效的项目集，那么，GO(I，X)便是对 X 有效的项目集。,P50：设a是中的一个字符，定义Ia=-closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。,文法G(S)SE EaA|bB AcA|d BcB|d I0=SE,EaA,EbB GO(I0,E)=closure(J)=closure(SE)=SE=I1 GO(I0,a)=closure(J)=closure(EaA)=EaA,AcA,Ad)=I2 GO(I0,b)=closure(J)=closure(E b.B)=E b.B,B.cB,B.d=I3,求GO(I,a)的方法是：检查I中所有那些圆点之后紧跟a的项目，我们把这个项目的圆点向右移一个位置，得到项目J，然后对这个J求其闭包CLOSURE(J)。,构造文法G的拓广文法G的LR(0)项目集规范族算法：PROCEDURE ITEMSETS(G)；BEGINC:=CLOSURE(SS)；REPEAT FOR C中每个项目集I和G的每个符号X DO IF GO(I，X)非空且不属于C THEN 把GO(I，X)放入C族中;UNTIL C不再增大END,这个算法的工作结果C就是文法G的LR(0)项目集规范族，其中的每一个元素是LR(0)项目集合。转换函数GO把这些项目集连接成一个DFA转换图.,1.拓广文法：在原文法GS上增加一个产生式S S，这是为了得到唯一的接受状态S S；2.设项目集规范族C只包含第一个状态S S的闭包，即C=Closure(S S)；3.利用GO函数对C中的每个项目集和每个符号X计算其下一状态，并将下一状态GO(I,X)加入到C中，直到C中状态数不再增加；C即为文法G的LR(0)项目集规范族。,总结：LR(0)项目集规范族的构造算法：,例：设文法G为：E aA bB A cAd B cBd求该文法的LR(0)分析表。,(0)S E(1)E aA(2)E bB(3)A cA(4)A d(5)B cB(6)B d,第步：拓广文法，并对产生式给予序号：,第步：写出拓广后的文法的项目集：,1.S E 2.S E 3.E aA 4.E a A 5.E aA 6.E bB 7.E b B 8.E bB 9.A cA 10.A c A 11.A cA 12.A d13.A d 14.B cB 15.B c B 16.B cB 17.B d18.B d,第3步：从SE开始求项目集规范族,由 S0=S E知：Closure(S0)=S E,E aA,E bB,由此初值CClosure(S0)再根据GO函数计算后继状态,由此表明显看出：Go(状态，后继符号)后继状态,最后得到LR(0)的项目集规范族,0:SE EaA EbB,4:AcA AcA Ad,5:BcB BcB Bd,3:EbB BcB Bd,1:SE,2:EaA AcA Ad,11:Bd,8:AcA,10:Ad,9:BcB,6:EaA,7:EbB,小结：构造LR(0)项目集规范族的两种方法：,1)先构造识别文法所有活前缀的NFA，然后用子集法将NFA确定化为一个以项目集合为状态的DFA。2)直接使用闭包和状态转换函数进行计算。,最后需要说明的是，由于任何一个高级语言相应文法的产生式是有限的，每个产生式右部的文法符号个数是有限的，因此每个产生式可列出的项目也为有限的，由有限的项目组成的子集即项目集作为DFA的状态也是有限的，所以不论用哪种方法构造识别活前缀的有限自动机必定会在有穷的步骤内结束。,假若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况：1)既含移进项目又含归约项目，2)含有多个归约项目。则称G是一个LR(0)文法。换言之，LR(0)文法规范族的每个项目集不包含任何冲突项目。,4.3.2 LR(0)分析表的构造,对于LR(0)文法，我们可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数GO构造出LR分析表。,构造LR(0)分析表的算法,令每个项目集Ik的下标k作为分析器的状态，特别令包含项目SS的集合Ik的下标k为分析器的初态。分析表的ACTION和GOTO子表构造方法如下：,若项目Aa属于Ik且GO(Ik,a)Ij，a为终结符，则置ACTIONk,a 为“把(j,a)移进桟”，简记为“sj”。若项目A属于Ik，那么，对任何终结符a(或结束符#)，置ACTIONk,a为“用产生式A进行规约”，简记为“rj”(假定产生式A是文法G的第j个产生式)。若项目SS属于Ik，则置ACTIONk,#为“接受”，简记为“acc”。若GO(Ik,A)Ij，A为非终结符，则置GOTOk,A=j。分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。,例：文法G(S)SE EaA|bB AcA|d BcB|d 构造该文法的LR(0)分析表，并对输入acccd进行分析。,识别活前缀的DFA,LR(0)分析表为,ACTION,GOTO,状态,0,1,2,3,4,5,6,7,8,9,10,11,a,b,c,d,#,E,A,B,s2,s3,1,acc,s4,s10,s10,s11,s11,s4,s5,s5,6,8,7,r1,r1,r1,r1,r1,r2,r2,r2,r2,r2,r3,r3,r3,r3,r3,r5,r5,r5,r5,r5,r4,r4,r4,r4,r4,r6,r6,r6,r6,r6,9,规则1.若项目Aa属于Ik且GO(Ik,a)Ij，a为终结符，则置ACTIONk,a 为“把(j,a)移进桟”，简记为“sj”。,规则2:若项目A属于Ik，那么，对任何终结符a(或结束符#)，置ACTIONk,a为“用产生式A进行规约”，简记为“rj”(假定产生式A是文法G的第j个产生式)。,规则3：若项目SS属于Ik，则置ACTIONk,#为“接受”，简记为“acc”。,规则4：若GO(Ik,A)Ij，A为非终结符，则置GOTOk,A=j。,规则5：分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。,LR(0)分析表为,识别活前缀的DFA,0:SE EaA EbB,4:AcA AcA Ad,2:EaA AcA Ad,1:SE,3:EbB BcB Bd,5:BcB BcB Bd,11:Bd,9:BcB,7:EbB,10:Ad,6:EaA,8:AcA,c,c,b,E,a,d,A,c,c,d,d,d,B,A,B,规则1.若项目Aa属于Ik且GO(Ik,a)Ij，a为终结符，则置ACTIONk,a 为“把(j,a)移进桟”，简记为“sj”。,识别活前缀的DFA,0:SE EaA EbB,4:AcA AcA Ad,2:EaA AcA Ad,1:SE,3:EbB BcB Bd,5:BcB BcB Bd,11:Bd,9:BcB,7:EbB,10:Ad,6:EaA,8:AcA,c,c,b,E,a,d,A,c,c,d,d,d,B,A,B,规则2:若项目A属于Ik，那么，对任何终结符a(或结束符#)，置ACTIONk,a为“用产生式A进行规约”，简记为“rj”(假定产生式A是文法G的第j个产生式)。,识别活前缀的DFA,0:SE EaA EbB,4:AcA AcA Ad,2:EaA AcA Ad,1:SE,3:EbB BcB Bd,5:BcB BcB Bd,11:Bd,9:BcB,7:EbB,10:Ad,6:EaA,8:AcA,c,c,b,E,a,d,A,c,c,d,d,d,B,A,B,规则3:若项目SS属于Ik，则置ACTIONk,#为“接受”，简记为“acc”。,识别活前缀的DFA,0:SE EaA EbB,4:AcA AcA Ad,2:EaA AcA Ad,1:SE,3:EbB BcB Bd,5:BcB BcB Bd,11:Bd,9:BcB,7:EbB,10:Ad,6:EaA,8:AcA,c,c,b,E,a,d,A,c,c,d,d,d,B,A,B,规则4:若GO(Ik,A)Ij，A为非终结符，则置GOTOk,A=j。,例:按上表对acccd进行分析步骤状态符号输入串10#acccd#202#acccd#3024#acccd#40244#acccd#502444#acccd#60244410#acccd#7024448#acccA#802448#accA#90248#acA#10026#aA#1101#E#,练 习,给定文法：S aS|bS|c(1)构造的LR(0)项目集规范族，(2)构造识别该文法所产生的活前缀的DFA(3)该文法是否是LR(0)的，若是，构造LR(0)分析表,三.求项目集规范族,每个项目集中的各个项目不冲突,则是LR(0)文法。,四.画出DFA,五.构造LR(0)分析表,4.4 SLR分析表的构造,SLR(1)分析法为了对语言句子进行确定性的分析，针对LR(0)的局限性，需要解决移进-规约或规约-规约冲突。我们采用对含有冲突的项目集向前查看一个输入符号的办法来解决冲突，这种分析方法称为简单的LR分析法，即SLR(1)分析法。,LR(0)文法太简单，没有实用价值.只有当一个文法G是LR(0)文法，即G的每一个状态不出现冲突时，才能构造出LR(0)分析表。由于大多数实用的程序设计语言的文法不能满足LR(0)文法的条件，因此使用向前查看一个符号的办法来处理冲突。只对有冲突的状态向前查看一个符号，即查看follow集，以确定做哪个动作，这种分析方法为简单的LR分析法，用SLR表示。如果每个项目都附上k个终结符号，表示要对它进行归约时，后续的k个输入符号与这k个符号相同时，才能对栈顶进行归约。这就是LR(k)分析。,LR(0)项目集规范族中的冲突现象假定一个LR(0)规范族中含有如下的一个项目集（状态）I：IXb，A，B第一个项目告诉我们的动作是：应把下一个输入符号b（如果是b）移进；第二个项目告诉我们的动作是：应把桟顶的规约为A；第三个项目告诉我们的动作是：应把桟顶的规约为B。,SLR(1)冲突的解决办法,若一个项目集中同时含有移进和归约项目，出现了冲突。解决冲突的办法是：考察非终结符A、B的的follow集，此时要求b,follow(A),follow(B)不相交。当面临的输入符号a为：当a=b，则b应移进；当a follow(A)，则用产生式A进行归约；当a follow(B)，则用产生式A进行归约.,I=XbA A B,(0)SE(1)E E+T(2)E T(3)T T*F(4)T F(5)F(F)(6)F i,移进-归约冲突,冲突的解决方法：,在I1中，Follow(S)=#，而SE是唯一的接受项目，所以当且仅当遇到句子的结束符#号时，句子才被接受。又因#+，因此I1中的冲突可解决。,SEE E+T,在I2中，Follow(E)=#,),+Follow(E)*=+,),#*，所以如果当前输入符号为#,),+时，就使用ET进行归约；如果当前输入符号为*时，就移进；当面临其他输入符号时，出错。,ETTT*F,在I9中，Follow(E)*=+,),#*，因此面临输入符为+，)或#时，用产生式EE+T进行归约；当面临输入符为*时，移进；其它情况则报错。,EE+TTT*F,解决冲突的方法分析所有含A或B的句型，考察句型中可能直接跟在A或B之后的终结符，也就是说，考察集合FOLLOW(A)和FOLLOW(B)。如果这两个集合的交集为，且不包含b，那么，当状态I面临任何输入符号a时，可以:1.若a=b，则移进；2.若aFOLLOW(A)，用产生式A进行归约；3.若aFOLLOW(B)，用产生式B进行归约；4.此外，报错。,假定LR(0)规范族的一个项目集I=A1a11，A2a22，Amamm，B1，B2，Bn 如果集合a1，am，FOLLOW(B1)，FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集合有#)，则：1.若a是某个ai，i=1,2,m，则移进；2.若aFOLLOW(Bi)，i=1,2,n，则用产生式Bi进行归约；3.此外，报错。冲突性动作的这种解决办法叫做SLR(1)解决办法。,构造SLR(1)分析表方法:首先把G拓广为G，对G构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO.然后使用C和GO，按下面的算法构造SLR分析表：令每个项目集Ik的下标k作为分析器的状态，包含项目SS的集合Ik的下标k为分析器的初态。,分析表的ACTION和GOTO子表构造方法：1.若项目Aa属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTIONk,a为“sj”；2.若项目A属于Ik，那么，对任何终结符a，aFOLLOW(A)，置ACTIONk,a为“rj”；其中，假定A为文法G的第j个产生式；3.若项目SS属于Ik，则置ACTIONk,#为“acc”;4.若GO(Ik,A)Ij，A为非终结符，则置GOTOk,A=j；5.分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。,按上述方法构造出的ACTION与GOTO表如果不含多重入口，则称该文法为SLR(1)文法。使用SLR表的分析器叫做一个SLR分析器。,例5.11 考察下面的拓广文法：(0)SE(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi,这个文法的LR(0)项目集规范族为：,I0:SE EE+T ET TT*F TF F(E)Fi,I1:SE EE+T,I2:ET TT*F,I3:TF,I4:F(E)EE+T ET TT*F TF F(E)Fi,I5:Fi,I6:EE+T TT*F TF F(E)Fi,I7:TT*F F(E)Fi,I8:F(E)EE+T,I9:EE+T TT*F,I10:TT*F,I11:F(E),识别活前缀的自动机,I1、I2和I9都含有“移进归约”冲突。FOLLOW(E)#,),+，,I2:ET TT*F,I1:SE EE+T,I9:EE+T TT*F,其分析表如下:,规则2：若项目A属于Ik，那么，对任何终结符a，aFOLLOW(A)，置ACTIONk,a为“rj”；其中，假定A为文法G的第j个产生式；,这个文法的LR(0)项目集规范族为：,I0:SE EE+T ET TT*F TT*F TF F(E)Fi,I1:SE EE+T,I2:ET TT*F,I3:TF,I4:F(E)EE+T ET TT*F TF F(E)Fi,I5:Fi,I6:EE+T TT*F TF F(E)Fi,I7:TT*F F(E)Fi,I8:F(E)EE+T,I9:EE+T TT*F,I10:TT*F,I11:F(E),规则2：若项目A属于Ik，那么，对任何终结符a，aFOLLOW(A)，置ACTIONk,a为“rj”；其中，假定A为文法G的第j个产生式；,I1、I2和I9都含有“移进归约”冲突。FOLLOW(E)+,),#,注意：计算FOLLOW集合所得到的超前符号集合可能大于实际能出现的超前符号集。,非SLR文法示例：考虑如下文法：(0)SS(1)SL=R(2)SR(3)L*R(4)Li(5)RL,SLR(1)分析方法的局限性：,这个文法的LR(0)项目集规范族为：,I0：SS SL=R SR S*R Li RL,I1：SS,I2：SL=R RL,I3：SR,I4：L*R RL L*R Li,I5：Li,I6：SL=R RL L*R Li,I7：L*R,I9：SL=R,I8：RL,I2含有“移进归约”冲突。FOLLOW(R)#,=，,I2：SL=R RL,当状态2显现于栈顶而且面临输入符号为=时，存在“移进-归约”冲突。,构造SLR(1)分析表时，第一个项目使ACTION2,=为S6；第二个项目使ACTION2,=为r5（“用RL规约”）。,SLR不能解决的问题,拓广文法G为：,（0）SS（1）SaAd（2）SbAc（3）Saec（4）Sbed（5）Ae,得到项目集规范族,项目集I5和I7中的冲突，不能用SLR(1)方法解决。Follow(A)=c，d,4.5 LR(1)分析表的构造,SLR(1)方法的局限性分析：用SLR(1)方法解决动作冲突时，仅孤立地考查归约项目中左部非终结符的FOLLOW集合。即，对于归约项目A.,只要当前面临的输入符号aFOLLOW(A)，就确定使用规则A进行归约，而没有考查符号串所在规范句型的环境。假设桟里的符号串为#,规约后变为#A，当前读到的输入符号为a，如果文法中根本不存在形如“Aa”为前缀的规范句型，那么这种归约是不合适的。,换句话说，在文法的所有规范句型中，FOLLOW(A)中元素有些不会出现在A的后面