第五章 LR(0)方法

第五章自底向上的语法分析5.1自底向上的语法分析方法概述5.2LR(0)分析的有限自动机5.3LR(0)分析5.4SLR(1)分析5.5LR(1)分析5.6LALR(1)分析5.7LALR(1)语法分析器的自动生成器(YACC)内容回顾自底向上的分析过程LR分析机制LR分析的关键问题自底向上语法分析的例子P:(1)ZABb(2)Aa(3)Ab(4)Bb(5)Bc(6)BbBabcb输入符号栈动作abcb移入abcb归约(2)Abcb移入Abcb移入Abcb归约(5)AbBb归约(6)ABb移入归约(1)ABbZ成功自底向上分析过程是从所给输入串出发，对其进行最左归约的过程。LR分析机制分析栈输入#………aLR驱动程序:-shift(移入):移入型规范活前缀-reduce(归约):可归约规范活前缀LR分析表规范活前缀LR分析的关键问题如何判定规范活前缀?如何判定移入型规范活前缀?如何判定归约规范活前缀以及用哪一个产生式归约?如何判定分析结束?LR(k)自动机可以解决这些问题!5.2LR(0)分析的有限自动机构造LR(0)自动机的依据---派生定理应用派生定理的例子LR(0)自动机–LR(0)item(项)–LR(0)automata构造LR(0)自动机的过程构造LR(0)自动机的依据---派生定理派生定理:给出了对任意一个CFG构造归约规范活前缀的方法–[1]*把CFG扩展为增广文法,ZS;–[2]文法开始符Z或S是归约规范活前缀;–[3]如果A是一个归约规范活前缀,且有产生式A,那么,也是一个归约规范活前缀;(,和是由终极符和非终极符构成的符号串,也可以是空串)–[4]任何一个归约规范活前缀都是按照[3]方式派生出来的;(证明略)派生定理应用例1[1]{S}[2]S和SaAc产生{aAc}[3]aAc和AAbb产生{aAbb}[4]aAc和Ab产生{ab}[5]aAbb和AAbb产生{aAbb}[6]aAbb和Ab产生{ab}[7]最后,合起来得到{S,aAc,aAbb,ab}VT={a,b,c}VN={S,A}S=SP:{SaAcAAbbAb}派生定理应用例2[1]{S}[2]S和SaAc产生{aAc}[3]aAc和AABb产生{aABb}[4]aAc和Aa产生{aa}[5]aABb和BbB产生{aAbB}[6]aABb和Bb产生{aAb}[7]aAbB和BbB产生{aAbbB}[8]aAbB和Bb产生{aAbb}……VT={a,b,c}VN={S,A,B}S=SP:{SaAcAABbAaBbBBb}LR(0)自动机LR(0)项目:带圆点的产生式,圆点只能出现在产生式的右部符号串的任意位置;–产生式SaAc，–LR(0)项目：SaAcSaAcSaAcSaAc–特别地，空产生式:S,–对应LR(0)项目SLR(0)自动机LR(0)项目集合IS关于符合X的投影–IS是一个LR(0)项目的集合;–X是一个符号(终极符或非终极符);–IS(X)表示项目集IS关于符号X的投影:–IS(X)={SX|SXIS,XVTVN}–IS(x)只对IS中圆点后面是X的项目起作用，所起的作用就是将圆点从X的前面移到X的后面IS={AABb,Ba,BbB,ZcB}X=BIS(B)={AABb,BbB}LR(0)自动机LR(0)项目集合的闭包–IS是LR(0)项目的集合;–CLOSURE(IS)也是一个LR(0)项目集合,按照下面的步骤计算:[1]初始,CLOSURE(IS)=IS[2]对于CLOSURE(IS)中没有处理的LR(0)项目,如果该项目的圆点后面是一个非终极符A,而且A的全部产生式是{A1,…,An}则增加如下LR(0)项目到CLOSURE(IS){A1,…,An}[3]重复[2]直到CLOSURE(IS)收敛;LR(0)自动机VT={a,b,c}VN={S,A,B}S=SP:{SaAcAABbABaBb}IS={SaAc}CLOSURE(IS)={SaAc}IS={SaAc}CLOSURE(IS)={SaAc,AABb,ABa,Bb}LR(0)自动机goto函数–IS是LR(0)项目集合;–X是一个符号(VTorVN终极符或非终极符);–goto(IS,X)=CLOSURE(IS(x))LR(0)自动机CFGG={VT,VN,S,P}的LR(0)自动机(，SS，S0，TS，)–是否需要增广产生式ZS？–=VTVN{#}–S0=CLOSURE(ZS)–SS–TS–构造LR(0)自动机的过程中逐步生成的。构造LR(0)自动机的过程[1]增广产生式ZS[2]=VTVN{#}[3]S0=CLOSURE(ZS)[4]SS={S0}[5]对于SS中的每一个项目IS,和每个符号X,计算IS’=goto(IS,X),如果IS’不为空,则建立ISIS’,如果IS’不为空且IS’不属于SS,则把IS’加入SS;[6]重复[5]直到SS收敛;[7]终止状态:包含形如A项目的项目集合;X构造LR(0)自动机的过程VT={a,b,c}VN={S,A,B}S=SP:{SaAcAABbABaBb}ZSSaAcZSSaSaAcAABbABaBbASaAcAABbBbbBABaaABaBbSaAccBAABbbAABbb0*****构造LR自动机的过程VT={a,b,c}VN={S,A,B}S=SP:{SaAcAABbABaB}ZSSaAcZSSaSaAcAABbABaBASaAcAABbBBABbbABbSaAccBAABbAABbb0******[1]{S}[2]S和SaAc产生{aAc}[3]aAc和AAbb产生{aAbb}[4]aAc和Ab产生{ab}[5]aAbb和AAbb产生{aAbb}[6]aAbb和Ab产生{ab}[7]最后,合起来得到{S,aAc,aAbb,ab}VT={a,b,c}VN={S,A}S=SP:{SaAcAAbbAb}VT={a,b,c}VN={S,A}S=SP:{SaAcAAbbAb}ZSSaAcSZSaSaAcAAbbAbASaAcAAbbbAbcSaAcbAAbbbAAbbLR(0)自动机接受的语言恰好是归约规范活前缀的集合：{S,aAc,aAbb,ab}VT={a,b,c}VN={S,A,B}S=SP:{SaAcAABbAaBbBBb}[1]{S}[2]S和SaAc产生{aAc}[3]aAc和AABb产生{aABb}[4]aAc和Aa产生{aa}[5]aABb和BbB产生{aAbB}[6]aABb和Bb产生{aAb}[7]aAbB和BbB产生{aAbbB}[8]aAbB和Bb产生{aAbb}……{S,aAc,aa,aABb,aAb+B,aAb+}VT={a,b,c}VN={S,A,B}S=SP:{SaAcAABbAaBbBBb}ZSSaAcSZSaSaAcAABbAaASaAcAABbBbBBbaAacSaAcbBbBBbBbBBbBBbBBAABbbAABbb结论:–一个CFG的LR(0)自动机接受的是该CFG的所有LR0归约规范活前缀;第五章自底向上的语法分析5.1自底向上的语法分析方法概述5.2LR(0)分析的有限自动机5.3LR(0)分析5.4SLR(1)分析5.5LR(1)分析5.6LALR(1)分析5.7LALR(1)语法分析器的自动生成器(YACC)5.3LR(0)分析LR(0)自动机的相关概念LR(0)文法LR(0)语法分析方法–LR(0)分析表–LR(0)分析的驱动程序LR(0)分析过程LR(0)自动机的相关概念移入项目:Aa,aVT归约项目:A,接受项目:ZS,(ZS是增广产生式)移入状态:包含移入项目的状态归约状态:包含归约项目的状态冲突状态(同一个状态中):–包含不同的归约项目，则称该状态存在归约-归约冲突；–既包含移入项目，又包含归约项目，则称该状态存在移入-归约冲突LR(0)文法给定一个上下文无关文法GLR0是G的LR(0)自动机如果LR0的任意一个状态都不存在冲突(归约-归约冲突、移入-归约冲突),则G称为LR(0)文法;可以推知：在LR(0)文法中，–任意状态或者是移入状态,或者是归约状态–如果是归约状态,一定存在一个唯一的归约项目,该归约项目对应一个产生式p,因此,该归约状态称为p-归约状态LR(0)分析方法StackInput#………aLR驱动程序:-shift(移入):移入型规范活前缀-reduce(归约):归约规范活前缀LR分析表规范活前缀状态栈action表goto表LR(0)驱动程序LR(0)文法VT={a,b,c}VN={S,A,B}S=SP:{(1)SaAc(2)AABb(3)ABa(4)Bb}ZSSaAcZSSaSaAcAABbABaBbASaAcAABbBbbBABaaABaBbSaAccBAABbbAABbb0123567894LR(0)分析的例子P:(0)ZS(1)SaAc(2)AABb(3)ABa(4)Bbabac符号栈输入流分析动作abac#移入abac#移入abac#归约(4)aBac#移入aBac#归约(3)aAc#移入aAc#归约(1)S#归约(0)Z#接受LR(0)分析的例子状态栈符号栈输入流分析动作0abac#移入02abac#移入027abac#归约(4)025aBac#移入0256aBac#归约(3)023aAc#移入0234aAc#归约(1)01S#归约(0)01Z#接受P:(0)ZS(1)SaAc(2)AABb(3)ABa(4)BbabacLR(0)分析表action表goto表LR(0)分析表action表终极符状态a1…#S1…Snaction(Si,a)=Sj,如果Si到Sj有a输出边action(Si,c)=Rp,如果Si是p-归约状态,cVt{#}action(Si,#)=accept,如果Si是接受状态action(Si,a)=error,其他情形LR(0)分析表goto表非终极符状态A1…S1…Sngoto(Si,A)=Sj,如果Si到Sj有A输出边goto(Si,A)=error,如果Si没有A输出边LR(0)分析表的例子VT={a,b,c}VN={S,A,B}S=SP:{(1)SaAc(2)AABb(3)ABa(4)Bb}ZSSaAcZSSaSaAcAABbABaBbASaAcAABbBbbBABaaABaBbSaAccBAABbbAABbb0123567894action表goto表abc#SAB0S211accept2S7353S7S484R1R1R1R15S66R3R3R3R37R4R4R4R48S99R2R2R2R2LR(0)分析驱动程序符号约定：–S0:开始状态–Stack:状态栈–Stack(top):栈顶元素–P:产生式–|P|:产生式P右部符号个数;–PA:产生式P左部非终极符;–Push(S):把状态S压入stack;–Pop(n):从stack弹出n个栈顶元素;LR(0