文法与语法分析(下).ppt

《文法与语法分析(下).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第04章文法与语法分析主要内容：LR(1)分析方法LALR(1)分析方法进行语法分析的几种方法语法错误处理4.5.6LR(1)方法前两种的不足之处：1）LR(0)方法：不依赖输入流，直接判定归约，容易出现冲突。2）SLR(1)方法：简单的把非终极符的follow集做为可归约的依据，不区分相同符号的不同出现，故并不精确。LR(1)基本思想：对非终极符的每个不同出现求其后继符集（展望符集Reducelookup），故减少了移入/归约冲突。例：下列文法的部分LRSM如右图：ZEE(L,E)ESLL

2、,ELESidS(S)ZEE(L,E)ESSidS(S)1E(L,E)S(S)LL,ELEE(L,E)ESSidS(S)2ESS(S)3(S注：因为：Follow(E)={)、#}Follow(L)={)、#、,}所以，状态3有冲突，故不能用SLR(1)方法。为什么要LR(1)分析？LR(1)分析中的相关定义LR(1)归约活前缀：定义为三元组(β,p,ss)形式，其中β是活前缀，p是产生式号，ss是展望符集。LR(1)归约活前缀定

3、理：设ZS#为增广产生式，则定理可描述如下：[1](S,0,{#})是LR(1)归约活前缀；[2]若(αAβ,p,ss)是LR(1)归约活前缀，Aπ是Q产生式，First2(β,ss)=ss1，则(απ,Q,ss1)也是LR(1)归约活前缀。LR(1)项目：定义为[Aα·β,ss]，其中Aα·β是项目的心，而ss为展望符集。LR(1)项目的产生途径：[1]发射：[A→X,a][A→X,a][2]扩展：[A→B,a][B→,b]其中B→是产生式,bFirst(a

4、)}展望符的计算原理：设ZS为增广产生式，#为结束符，(A)为A的后继符，则：[1](Z)={#}[2]若(A)=ss，AαB，则(B)=First2(,ss)其中，当时，First2(,ss)=First()-{}∪ss；否则First2(,ss)=First(）shift函数：假设给定项目集IS，则：shift(IS)={[A→X,a]

5、[A→X,a]IS}它表示IS中“·”右移一位所得的项目集。LR(1)项目集的闭包：假设IS是LR(1)项目集，则

6、称下面close_lr(IS)为IS的闭包集：[1]ISclose_lr(IS)；[2]若[A→αB,ss]close_lr(IS),B→G,First2(β,ss)=ss1，则[B→,ss1]close_lr(IS)；goto函数：假设给定项目集IS，则：goto(IS,X)=close_lr(shift(project(IS,X)))它表示IS状态的X输出边所指向状态的项目集闭包。例：已知文法G[Z]：Z→S,S→L=R,S→R,L→aR,L→b,R→L设：IS={[ZS，

7、#]}则：close_lr(IS)={[ZS，#]，[SL=R，#]，[SR，#]，[LaR，=]，[Lb，=]，[RL，#]}LR(1)状态机的构造[1]初始化：ss0=close({[Z→S#,]});AllStateSet={ss0};UnHandledStateSet={ss0};[2]判断结束：若UnHandledStateSet空，则结束，否则转[3]；[3]从UnHandledStateSet选择一个状态ss，并做对每个符号a做下面动作：1)求ss1=got

8、o(ss,a)，若ss1空，则TT[ss,a]=空；2)否则，检查在AllStateSet中有无ss1;①若无，则把ss1追加到UnHandledStateSet和AllStateSet中，并构造ss(a)ss1；②否则，构造ss(a)ss1；[4]从UnHandledStateSet中删除状态ss，并转向步骤[2]。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

9、#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)分析表的构造Action表Action(S,a)=Shiftj....当S有到Sj的a输出边Action(S,a)=Reducep...当S是p-归约状态Action(S,#)=Accept....当S是接受状态Action(S,a)=Error.