编译原理课件 语法分析_自下而上__LR(0)项目集规范族的构造

1.构造识别文法所有活前缀的DFA0245136897SaAbcBed*bG:S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]~~构造识别文法所有活前缀的DFAG':S'→S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]拓广文法~~构造识别文法所有活前缀的DFA0245136897SaAbcBed*bG':S'→S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]LR(0)项目LR(0)项目集精细刻画每个状态I0S'→•SS→•aAcBeLR(0)项目集规范族~~构造识别文法所有活前缀的DFA0245136897SaAbcBed*bG':S'→S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]状态转换函数GO(I,X)I1S'→S•SaI2S→a•AcBeA→•bA→•Ab闭包函数CLOSURE(I)I0S'→•SS→•aAcBe~~构造识别文法所有活前缀的DFA0245136897SaAbcBed*bG':S'→S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]状态转换函数GO(I,X)LR(0)项目LR(0)项目集LR(0)项目集规范族项目集I的闭包函数CLOSURE(I)拓广文法拓广文法AugmemtedGrammar•文法G的开始符号为S,在G中加入S'→S后得到文法G的拓广文法G'•注:即使原开始符号S不出现在任何产生式右部,为了统一起见也要增加该产生式。G':S'→S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]LR(0)项目定义•在文法G中每个产生式的右部适当位置添加一个圆点构成项目•对空产生式A→ε,仅有项目A→•例:产生式AXYZ对应的项目有A•XYZAX•YZAXY•ZAXYZ••项目的含义I1S'→S•SaI2S→a•AcBeA→•bA→•AbI0S'→•SS→•aAcBeLR(0)项目的分类•移进项目:A→α•aβ•待约项目:A→α•Bβ•归约项目:A→α••接受项目:S'→S•项目集I的闭包函数CLOSURE(I)a)I的项目均在CLOSURE(I)中。b)若A→α•Bβ属于CLOSURE(I),则每一形如B→•γ的项目也属于CLOSURE(I)c)重复b)直到CLOSURE(I)不再扩大。I={S→a•AcBe}CLOSURE(I)={S→a•AcBe,A→•b,A→•Ab}G':S'→S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]核KernelItem核KernelItem-圆点不在产生式右部最左边的项目称为核-S‘→•S除外I1S'→S•SaI2S→a•AcBeA→•bA→•AbI0S'→•SS→•aAcBe状态转换函数GO(I,X)GO(I,X)=CLOSURE(J)J={A→αX•β|A→α•Xβ∈I}IA→α•XβJA→αX•βXI1S'→S•SaI2S→a•AcBeA→•bA→•AbI0S'→•SS→•aAcBeG':S'→EE→aA|bBA→cA|dB→cB|dI0:S'•EE•aAE•bBI8:Bc•BB•cBB•dI3:Eb•BB•cBB•dI2:Ea•AA•cAA•dI1:S'E•I5:Ac•AA•cAA•dI10:AcA•I6:Ad•I4:EaA•I7:EbB•I9:Bd•I11:BcB•bEaccccddddAABB构造DFA-识别文法所有活前缀LR(0)项目集规范族{I0,I1,…,I11}拓广构造文法的LR(0)项目集规范族C={I0,I1,……,In}a)置项目S'→•S为初态集的核，然后对核求闭包,CLOSURE({S'→•S}）得到初态的项目集b)对初态集或其它所构造的项目集应用转换函数GO(I,X)=CLOSURE(J)求出新状态J的项目集c)重复b)直到不出现新的项目为止算法Procedureitemsets(G')BeginC:={CLOSURE({S'•S})}RepeatforC中的每一个I和每一个XdoifGO(I,X)非空且不属于Cthen把GO(I,X)放入C中untilC不再增大end初态的项目集应用状态转换函数得到新的项目集问题☆•项目集中的项目代表的不同含义？•若栈中的活前缀为γ,接下来应采取怎样的动作?(0)S'→E(1)E→aA(2)E→bB(3)A→cA(4)A→d(5)B→cB(6)B→d例:构造LR(0)分析表I0:S'•EE•aAE•bBI8:Bc•BB•cBB•dI3:Eb•BB•cBB•dI2:Ea•AA•cAA•dI1:S'E•I5:Ac•AA•cAA•dI10:AcA•I6:Ad•I4:EaA•I7:EbB•I9:Bd•I11:BcB•bEaccccddddAABBLR0分析表(0)S'→E(1)E→aA(2)E→bB(3)A→cA(4)A→d(5)B→cB(6)B→dr6r6r6r6r611r4r4r4r4r410r5r5r5r5r59r3r3r3r3r38r2r2r2r2r27r1r1r1r1r1610S6S55847S9S834S6S52acc11S3S20BAE$dcbaGOTOACTION状态11S6S8LR(0)分析表的构造ParsingTable假设已构造出LR(0)项目集规范族为:C={I0,I1,…,In}令包含S'→•S项目的集合Ik的下标k为分析器的初始状态。……a)若项目A→α•aβ属于Ik,且GO(Ik,a)=Ij则置ACTION[k,a]为Sjb)若项目A→α•属于Ik，则对任何终结符a和‘#’置ACTION[k,a]和ACTION[k,#]为“rj”,j为在文法G'中某产生式A→α的序号。c)若项目S'→S•属于Ik,则置ACTION[k,#]为“acc”/接受d)若GO(Ik,A)＝Ij，则置GOTO[k,A]为je)凡不能用上述方法填入的元素,均填上“报错标志”/“空白”LR(0)文法的定义•如果一个文法G的LR(0)分析表不含多重定义,则称G为LR(0)文法项目集中存在的冲突•移进-归约冲突Shift-ReduceConflict一个项目集中移进和归约项目同时存在:A→α•aβB→γ••归约-归约冲突Reduce-ReduceConflict一个项目集中归约和归约项目同时存在:A→β•B→γ•LR(0)文法的定义•若一个文法G的拓广文法G的活前缀识别自动机中的每个状态(项目集)不存在下述情况①移进-归约冲突②归约-归约冲突则称G是一个LR(0)文法•LR(0)分析表不含多重定义练习:构造LR(0)项目集规范族G':S'→S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]提纲2.LR(0)项目(1)LR(0)项目的定义(2)基于LR(0)项目构造识别文法活前缀的DFA(3)LR(0)项目的分类(4)LR(0)项目集、LR(0)项目集规范族3.LR(0)项目集规范族的构造CanonicalLR(0)Collection(1)拓广文法(2)项目集I的闭包函数CLOSURE(I)(3)状态转换函数GO(I,X)(4)构造文法的LR(0)项目集规范族4LR(0)项目集规范族的构造1.构造识别文法所有活前缀的DFA2.LR(0)项目3.LR(0)项目集规范族的构造4.LR(0)分析表的构造5.LR(0)文法的定义