编译原理5.3.2-LR项目集族和LR分析表的构造.ppt
第五章第五章 语法分析语法分析5.1 自下而上分析基本问题自下而上分析基本问题5.2 算符优先分析算符优先分析 5.3 LR分析分析5.4 YACC5.3 LR分析分析5.3.1 LR分析器分析器5.3.2 LR(0)项目集族项目集族LR(0)分析表的构造分析表的构造5.3.3 SLR分析表的构造分析表的构造5.3.4 规范规范LR分析表的构造分析表的构造5.3.5 LALR分析表的构造分析表的构造5.3.6 二义文法的应用二义文法的应用5.3.2 LR(0)项目集族项目集族LR(0)分析表的构造分析表的构造一、前缀、活前缀一、前缀、活前缀 p104p104二、构造识别文法所有活前缀的二、构造识别文法所有活前缀的DFA DFA p104p104三、三、LR(0)LR(0)项目集规范族的构造项目集规范族的构造 p106p106四、有效项目四、有效项目 p108p108五、五、LR(0)LR(0)分析表的构造分析表的构造 p109p109一、前缀、活前缀一、前缀、活前缀 前缀前缀:符号串的头符号串的头 活前缀活前缀:规范句型的一个前缀规范句型的一个前缀,这种前这种前缀不包含句柄之后的任何符号缀不包含句柄之后的任何符号.*可归前缀可归前缀:包含句柄的活前缀包含句柄的活前缀.规范规范推导推导序列序列 S=aAcBe=aAcde=aAbcde=abbcde,a,ab,a,aA,aAb,a,aA,aAc,aAcd,a,aA,aAc,aAcB,aAcBe活前缀活前缀可归前缀可归前缀ab,aAb,aAcd,aAcBe补充例补充例:找出找出句型句型#abbcde#abbcde#的所有活前缀的所有活前缀G:SaAcBe1 Ab2 AAb3 Bd4ab b 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#aAcBe#e#移进移进1010#aAcBeaAcBe#归约归约 SaAcBe1111#S#S#接受接受abb c d eAABS栈里的文法符号与栈里的文法符号与剩余符号串一起构剩余符号串一起构成了规范句型成了规范句型栈里的文法符号构栈里的文法符号构成活前缀成活前缀 S=aAcBe =aAcde =aAbcde =abbcde 规范规范推导推导序列序列#abbcde#的规范归约过程的规范归约过程二、构造识别文法所有活前缀的二、构造识别文法所有活前缀的DFA 1.LR(0)1.LR(0)项目项目2.2.构造识别文法所有活前缀的构造识别文法所有活前缀的DFADFA3.LR(0)3.LR(0)项目的分类项目的分类1.LR(0)1.LR(0)项目项目在文法在文法G中每个产生式的右部适当位置添加一中每个产生式的右部适当位置添加一个圆点构成项目个圆点构成项目.对空产生式对空产生式A,仅有项目仅有项目A例例:产生式产生式 A XYZ 对应的项目有对应的项目有 AXYZ AXYZAXYZ AXYZ一个产生式可对应的项目个数是它的右部符号长度加一个产生式可对应的项目个数是它的右部符号长度加1 1每个项目的含义与圆点的位置有关每个项目的含义与圆点的位置有关 补充例补充例:若有产生式若有产生式 S aAd,Abc对应的项目对应的项目:(1)SaAd (2)S aAd (3)S aAd (4)SaAd (5)Abc (6)Abc (7)Abc2.2.构造识别文法所有活前缀的构造识别文法所有活前缀的DFADFA1).文法的每个项目都为文法的每个项目都为NFA的一个状态的一个状态 2).确定状态之间的转换关系确定状态之间的转换关系 3).确定化最小化确定化最小化例例5.8 p105 G:SE EaA|bB AcA|d BcB|d 更更正正1SE 2SE 11.EbB3EaA 12.EbB4EaA 13.EbB5EaA 14.BcB6AcA15.BcB7AcA 16.BcB8AcA 17.Bd9Ad 18.Bd 10.Ad文法的项目文法的项目:1).文法的每个项目都为文法的每个项目都为NFA的一个状态的一个状态2).确定状态之间的转换关系确定状态之间的转换关系X Xi iXXXX1 1X X2 2XXi-1i-1X Xi iXXn nXXXX1 1X X2 2X Xi iX Xi+1i+1XXn nXXA AAA状态状态i状态状态j出自同一产生式出自同一产生式项目项目1 1为为初态初态 P106 NFA1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad 10.Ad 11.EbB12.EbB 13.EbB14.BcB15.BcB16.BcB 17.Bd 18.Bd 每个状态都为每个状态都为活前缀识别态活前缀识别态句柄识别态句柄识别态(可归前缀识别可归前缀识别态态):圆点在最后的项目圆点在最后的项目句子识别态句子识别态 p106识别一个文识别一个文法活前缀的法活前缀的DFADFA3).确定化确定化最小化最小化每个状态是一每个状态是一个项目集个项目集,称作称作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 表明一个产生式的右部已分析完，句柄已形成可表明一个产生式的右部已分析完，句柄已形成可以归约以归约 接受项目接受项目:SSSS 表明已分析成功表明已分析成功 三、三、LR(0)项目集规范族的构造项目集规范族的构造构造识别文法活前缀构造识别文法活前缀DFA的三种方法的三种方法*1.求出活前缀的正规表达式，然后由此正规表求出活前缀的正规表达式，然后由此正规表达式构造达式构造NFA,再确定化为再确定化为DFA。2.求出文法的所有项目，按一定规则构造识别求出文法的所有项目，按一定规则构造识别活前缀的活前缀的NFA,再确定化为再确定化为DFA。3.通过闭包函数和转换函数，直接求出通过闭包函数和转换函数，直接求出LR(0)项目集规范族，再由转换函数建立状态之间项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的的连接关系得到识别活前缀的DFA。1.1.拓广文法拓广文法2.2.项目集项目集I I的闭包函数的闭包函数 CLOSURE(I)CLOSURE(I)3.3.状态转换函数状态转换函数 GO(I,X)GO(I,X)4.4.构造文法的构造文法的LR(0)LR(0)项目集规范族项目集规范族1.1.拓广文法拓广文法原文法原文法G G的开始符号为的开始符号为S,S,在在G G中加中加SSSS 后得新的文法后得新的文法GG，则称则称 GG为原文法为原文法G G的拓广文法。的拓广文法。使文法的开始符号不出现在任何产生式右部，使文法的开始符号不出现在任何产生式右部，当栈顶出现当栈顶出现S,S,则分析完成则分析完成 。注注:即使原开始符号即使原开始符号S S不出现在任何产生式右部不出现在任何产生式右部,为了统一起见也要增加该产生式。为了统一起见也要增加该产生式。2.2.项目集项目集I I的闭包函数的闭包函数 CLOSURE(I)CLOSURE(I)a)I 的项目均在的项目均在 CLOSURE(I)中。中。b)若若AB属于属于CLOSURE(I),则每一形如则每一形如 B的项目也属于的项目也属于CLOSURE(I)c)重复重复b)直到直到CLOSURE(I)不再扩大。不再扩大。NFA:状态集合状态集合I的的-闭包闭包-closure(I)ABB补充例补充例I SE CLOSURE(I)=SE,EaA,EbB 1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad 10.Ad 11.EbB12.EbB 13.EbB14.BcB15.BcB16.BcB 17.Bd 18.Bd 13113.3.状态转换函数状态转换函数 GO(I,X)GO(I,X)GO(I,X)=CLOSURE(J),X(VNVT),J=AX|AXI X XAXAX若状态若状态I I识别活前缀识别活前缀,则状态则状态J J识别活前缀识别活前缀XX 状态状态I I状态状态J JNFA:状态集合状态集合I的的a弧转换弧转换 补充例补充例I SE,EaA,EbB GO(I,a)=CLOSURE(EaA )=EaA,AcA,Ad 1SE2SE 3EaA4EaA 5EaA 6AcA7AcA8AcA 9Ad 10.Ad 11.EbB12.EbB 13.EbB14.BcB15.BcB16.BcB 17.Bd 18.Bd 13114694.4.构造文法的构造文法的LR(0)LR(0)项目集规范族项目集规范族 C=IC=I0 0,I,I1 1,I,In n 核核:圆点不在产生式右部最左边的项目称为核圆点不在产生式右部最左边的项目称为核 a)置项目置项目SS为初态集的核，然后对核求闭为初态集的核，然后对核求闭包，包，CLOSURE(SS）得到初态的项目）得到初态的项目集。集。b)对初态集或其它所构造的项目集应用转换函对初态集或其它所构造的项目集应用转换函数数GO(I，X)=CLOSURE(J)求出新状态求出新状态J的项的项目集。目集。c)重复重复b)直到不出现新的项目为止。直到不出现新的项目为止。算法算法Procedure itemsets(G)Begin C:=CLOSURE(SS)Repeat for C中的每一个中的每一个I 和每一个和每一个X do if GO(I,X)非空且不属于非空且不属于C then 把把GO(I,X)放入放入C中中 until C不再增大不再增大end p107初态的项目集初态的项目集 应用状态转换应用状态转换函数得到新的函数得到新的项目集项目集 G:SE EaA|bB AcA|d BcB|d I0:SE E aA E bBI8:BcB B cB B dI3:EbB B cB B dI2:EaA A cA A dI1:S EI5:AcA A cA A dI10:Ac AI6:A dI4:EaAI7:EbBI9:B dI11:BcB b E a c c c c d d d d A A B B识别文法所有活前识别文法所有活前缀的缀的DFADFALR(0)LR(0)项目集规范族项目集规范族 II0 0,I,I1 1,I,I1111 四、有效项目四、有效项目*移进移进-归约冲突归约冲突 一个项目集中移进和归约项目同时存在：一个项目集中移进和归约项目同时存在：AaB归约归约-归约冲突归约冲突一个项目集中归约和归约项目同时存在一个项目集中归约和归约项目同时存在:AB五、五、LR(0)分析表的构造分析表的构造LR(0)文法文法假若一个文法假若一个文法G的拓广文法的拓广文法G 的活前缀识别的活前缀识别自动机中的每个状态自动机中的每个状态(项目集项目集)不存在下述情况不存在下述情况既含移进项目又含归约项目既含移进项目又含归约项目或者含有多个归约项目或者含有多个归约项目则称则称G是一个是一个LR(0)文法文法。LR(0)文法规范族的每个项目集不包含任何冲文法规范族的每个项目集不包含任何冲突项目突项目(移进移进-归约冲突、归约归约冲突、归约-归约冲突归约冲突)。LR(0)分析表的构造分析表的构造假设已构造出假设已构造出LR(0)项目集规范族为项目集规范族为:C=I0,I1,In 令包含令包含SS 项目的集合项目的集合Ik的下标的下标k为分析为分析器的初始状态。器的初始状态。a)若项目若项目Aa属于属于Ik ,且且 GO(Ik,a)=Ij 则置则置 ACTIONk,a 为为Sjb)若项目若项目A 属于属于Ik，则对任何终结符，则对任何终结符a 和和#置置ACTIONk,a 和和ACTIONk,#为为“rj”,j为在文法为在文法G中某产生式中某产生式 A的序号。的序号。c)若项目若项目 SS 属于属于Ik,则置则置ACTIONk,#为为“acc”/接受接受d)若若GO(Ik,A)Ij，则置，则置GOTOk,A 为为je)凡不能用上述方法填入的元素凡不能用上述方法填入的元素,均填上均填上“报错标志报错标志”/“空白空白”I0:SE E aA E bBI8:BcB B cB B dI3:EbB B cB B dI2:EaA A cA A dI1:S E I5:AcA A cA A dI10:Ac AI6:A d I4:EaA I7:EbBI9:B d I11:BcB b E a c c c c d d d d A A B B(0)SE(1)EaA(2)EbB (3)AcA(4)Ad(5)BcB(6)Bd构造构造LR(0)LR(0)分析表分析表过程见黑板过程见黑板根据这种方法构造的根据这种方法构造的LR(0)分析表不含多重分析表不含多重定义时，称这样的分析表为定义时，称这样的分析表为LR(0)分析表分析表能用能用LR(0)分析表的分析器称为分析表的分析器称为LR(0)分析器分析器
