第四章7-LR(1)文法

主要内容：LR(1)分析方法ZEE(L,E)ESLL,ELESidS(S)ZEE(L,E)ESSidS(S)0E(L,E)S(S)LL,ELEE(L,E)ESSidS(S)1ESS(S)2(S1(S2,))={Shift,Reduce3}即|1(S2,))|≤1不成立(Follow(E)={#,),,})非SLR(1)文法LR(0)方法不依赖输入流，直接判定归约，容易出现冲突。SLR(1)方法简单地把非终极符的follow集做为可归约的依据，并不精确。一个非终极符在不同的位置上出现，它所允许的后继符是不同的，而SLR(1)没有加以区分。LR(1)针对不同产生式上的非终极符，分别定义其后继符集（展望符集Reducelookup），减少了移入/归约冲突。任何SLR(1)都一定是LR(1)文法。1、构造文法的LR(1)自动机2、由LR(1)自动机构造LR(1)分析表（Action表和Goto表）3、根据当前状态和输入符号查分析表确定要执行的操作，进行相应的语法分析LR(1)分析步骤LR(1)分析方法LR(1)方法研究的对象是二元组：(,b)，其中是活前缀，而b是一个输入符号。我们称上述(，b)为LR1前缀模式。活前缀？规范活前缀：若规范前缀不含句柄或含一个句柄并且具有形式=(是句柄)，则称规范前缀为规范活前缀(简称活前缀）。（前缀中若有句柄，则句柄在前缀的最右端）物理含义：在归约过程中，若符号栈中的内容为活前缀，则表示到目前为止，语法正确。可以继续进行移入或归约操作。LR(1)分析方法LR(1)方法研究的对象是二元组：(,b)，其中是活前缀，而b是一个输入符号。我们称上述(，b)为LR1前缀模式。如果是文法的归约活前缀，b是的合法后继续符，则称(，b)为LR1归约前缀模式。归约活前缀？移入活前缀：如果活前缀不中不包含简单短语（句柄），则称为移入型活前缀。因为此时只能进行移入操作，不能进行归约操作。归约活前缀：若活前缀是含句柄的活前缀，即有=，且是句柄，则称活前缀为归约规范活前缀。（即含有句柄的规范活前缀。是可以归约的）不确定活前缀：如果一个活前缀既是移入型的又是归约型的，则称为不确定活前缀。例：SabcSab则ab既是移入型活前缀，又是归约型活前缀。LR(1)分析方法LR(1)方法研究的对象是二元组：(,b)，其中是活前缀，而b是一个输入符号。我们称上述(，b)为LR1前缀模式。如果是文法的归约活前缀，b是的合法后继续符，则称(，b)为LR1归约前缀模式。LR1归约前缀的派生定理假设0是拓广产生式的右部，#是输入流的结束符，则有：(0[p],#)是LR1归约前缀模式。设(A[p],b)是LR1归约前缀模式，且A→是q产生式，则([q],a)也是LR1归约前缀模式，其中aFirst(b)。派生定理的目的是要求得项目集合的闭包CLOSURE(IS)LR(1)项目：[A→,a]。LR(0)项目及一个VT{#}的展望符（输入符）集合。IS:LR(1)项目集IS(X):（目的：产生下一个状态）IS(X)={[A→X,a]|[A→X,a]IS}CLOSURE(IS)=IS∪{[B→,b]|[A→B,a]CLOSURE(IS),B→是产生式,bFirst(a)}目的：产生派生项目LRSM1的构造算法1.初始项目集：ISS=CLOSURE({[Z→S,{#}]})2.若所有状态都处理完，则结束3.选一未处理完状态IS，对所有语法符号X（VTVN{#}),求ISX,令IS’=CLOSURE(ISX)，若IS’不为空：若IS’为新状态，则增加ISIS’,把IS’加入LRSM1中；否则为图中某个状态ISj，则在IS和ISj之间增加一条转换边：ISISj4.转到步骤2XX非SLR(1)文法：Z→SS→L=RS→RL→aRL→bR→L0ZSSL=RSRLaRLbRL###=#=##1ZS#2SL=RRL##6SL=RRLLaRLb####7SL=R#3SR#4Lb=#10LaR#=5LaRRLLaRLb#=#=#=#=11RL#=8LaRRLLaRLb####9RL#12Lb#13RaR#SLabRb=RLRLabaaLRbZ→SS→L=RS→RL→aRL→bR→L非SLR(1)文法：Z→SS→L=RS→RL→aRL→bR→L2SL=RRL##2状态存在移入-归约冲突归约：Follow(R)=Follow(S)Follow(L)={#,=}因此不是SLR(1)文法。9RL#11RL#=展望符不一样，做为不同的状态LR(1)文法投影函数2:(用来求分析表)2：StateSet(VT∪{#})→22(S,a)={Reducej|[B→,a]S,B→是产生式j}∪{Shift|[A→a,b]S}如果LR(1)状态机的任一状态S和输入符a，都使得|2(S,a)|≤1，则称文法为LR(1)文法.LR(1)分析表的构造Action表的构造：Action(S,a)=Error若2(S,a)=Action(S,#)=Accept若2(S,#)={Reduce1}Action(S,a)=Reducej若2(S,a)={Reducej}Action(S,a)=Shifti若2(S,a)={Shift}andGoTo(S,a)=SiGoTo表的构造：GoTo(S,X)=Si若S与Si状态有X转向边，X为非终极符。0ZSSL=RSRLaRLbRL###=#=##1ZS#2SL=RRL##6SL=RRLLaRLb####7SL=R#3SR#4Lb=#10LaR#=5LaRRLLaRLb#=#=#=#=11RL#=8LaRRLLaRLb####9RL#12Lb#13RaR#SLabRb=RLRLabaaLRbAction表：输入a时，由0状态转入5状态R413R512R6R611R4R410R69139S12S88R2779S12S861011S4S55R5R54R33R6S62Accept1321S4S50RLS#=ba0ZSSL=RSRLaRLbRL###=#=##1ZS#2SL=RRL##6SL=RRLLaRLb####7SL=R#3SR#4Lb=#10LaR#=5LaRRLLaRLb#=#=#=#=11RL#=8LaRRLLaRLb####9RL#12Lb#13RaR#SLabRb=RLRLabaaLRbGoto表：由0状态归约到R后，转入3状态R413R512R6R611R4R410R69139S12S88R2779S12S861011S4S55R5R54R33R6S62Accept1321S4S50RLS#=ba0ZSSL=RSRLaRLbRL###=#=##1ZS#2SL=RRL##6SL=RRLLaRLb####7SL=R#3SR#4Lb=#10LaR#=5LaRRLLaRLb#=#=#=#=11RL#=8LaRRLLaRLb####9RL#12Lb#13RaR#SLabRb=RLRLabaaLRbAction表：3状态输入#时，按3产生式SR归约R413R512R6R611R4R410R69139S12S88R2779S12S861011S4S55R5R54R33R6S62Accept1321S4S50RLS#=ba0ZSSL=RSRLaRLbRL###=#=##1ZS#2SL=RRL##6SL=RRLLaRLb####7SL=R#3SR#4Lb=#10LaR#=5LaRRLLaRLb#=#=#=#=11RL#=8LaRRLLaRLb####9RL#12Lb#13RaR#SLabRb=RLRLabaaLRbLR(1)驱动程序LR(1)的驱动程序与SLR(1)的驱动程序是相同的，可共用一个。状态栈符号栈输入串ActionGoTo0aab=b#S50,5aab=b#S50,5,5aab=b#S40,5,5,4aab=b#R5110,5,5,11aaL=b#R6100,5,5,10aaR=b#R4110,5,11aL=b#R6100,5,10aR=b#R420,2L=b#S60,6L=b#S120,6,12L=b#R590,6,9L=L#R670,6,7L=R#R210,1S#A设文法G[S]为：SAS|AaA|b证明G[S]是LR(1)文法；构造它的LR(1)分析表；给出符号串abab#的分析过程TheEnd