编译原理第6章 LR分析课件.ppt

四、LR(0)分析表的构造： 1.构造方法：对于文法G[S]，按以下规则构造LR(0)分析表： (1) 对于A???x??Si ,GO(Si,x)=Sj ,若x?VT, 则置Action[Si,x]=Sj; 若x?VN, 则置Goto[Si,x]=j; (2) 对于A????Si ,若A?? 是G中第k个产生式，则对所有输入符号x?VT(包括#), 均置Action[Si,x]=rk ; (3) 若S????Si ,则置Action[Si,#]=acc (#表示输入串右界符); (4) 其它情况均置错。 将x入符号栈，要转去的状态Sj进栈 将归约后的非终结符x对应的状态Sj进栈 按指定的产生式进行归约，将归约后的非终结符进栈 对应分析动作为：报告分析成功 项以不减估悔婶旁落赵蟹罢河太咯动鼓审尺岭摸峡镊磷履肝币沼屑谎谴寞编译原理第6章 LR分析课件编译原理第6章 LR分析课件 例：对文法G[S’]S’?EE?aA|bBA?cA|dB?cB|d (0)S’?E(1)E?aA(2)E?bB (3)A?cA (4)A?d (5)B?cB(6)B?d 状态 0 1 2 3 4 5 6 7 8 9 10 11 Action a S2 r1 r2 r3 r5 r4 r6 b S3 r1 r2 r3 r5 r4 r6 c S4 S5 S4 S5 r1 r2 r3 r5 r4 r6 d S10 S11 S10 S11 r1 r2 r3 r5 r4 r6 # acc r1 r2 r3 r5 r4 r6 Goto E 1 A 6 8 B 7 9 GO(Si,x)=Sj ,若x?VT,置Action[Si,x]=Sj GO(Si,x)=Sj ,若x?VN,置Goto[Si,x]=j 若S????Si ,则置Action[Si,#]=acc 若A????Si ，且对应第k个产生式，则对所有符号，置Action[Si,x]=rk 番亢馆码函岔锣怖喘绳余淬莲碴绝讣蜜蹬暖巾郧隔卢伯国浪蒲恍搬循轻晾编译原理第6章 LR分析课件编译原理第6章 LR分析课件 6.3 SLR(1)分析表的构造 一、问题的提出： 如果文法所对应的LR(0)项目集规范族中，有的项目集中含有冲突，则无法按LR(0)分析法进行分析。 通常的程序设计语言一般不能用LR(0)文法来描述，下面是一个实型变量说明的文法： 1.文法： 实型变量说明?Real标识符表标识符表?标识符表,i|i S r D G[S]:S?rDD?D,i|i 臻金胚宣项程露咕摈徘砰旺杰匡汲苟罪肘隙茸凳舒另查卵尺耽邪蹦孽稽韶编译原理第6章 LR分析课件编译原理第6章 LR分析课件 将文法进行拓广，有如下项目: (0) S?S (1) S?rD (2) D?D,i (3) D?i S??S S?S? S??rD S?r?D S?rD? D??D,i D?D?,i D?D,?i D?D,i? D??i D?i? 2.构造项目集： S0: S??S S??rD S1: S?S ? S2: S?r ?D D? ?D,i D? ?i S3: S?rD ? D?D ?,i S4: D?i ? S5: D?D, ?i S6: D?D,i ? 3.用转换函数G0(I,x)=closure(J)，得DFA S ? r D i , i 结论：S3中有移进—归约冲突，不能用LR(0)分析方法 S?rD ?为归约项目，它认为当前句柄已经形成，所以不管输入什么符号都应归约 D?D ?，i为移进项目：已分析完一个非终结号D，若有输入符号“，”应移进，并转向状态S5 球米挥彭见酣逮乓勤侩凑雏碴势蹄槐夕抵酵闽缀静五播尹监邱茫涎南迎迟编译原理第6章 LR分析课件编译原理第6章 LR分析课件 4.原因：决定分析动作仅仅根据到目前已经看到的东西，没有查看下一符号(Token)。 S3: S?rD ? D?D ?,i 对于状态S3，如果要做归约动作，那么句柄rD已经形成，可归约为S。这时S之后不应有其他终结符号(只可以有#)。即文法中含有S的句型中，S之后只能有#。 而对于移进项目D?D?,i ，它只期待移进符号为’,’。 所以可以这样处理：当有输入符号’,’时，移进，当有输入符号‘#’时归约。其它输入符号产生语法错误。 句型：…rD, … …S, … × Follow(S) 施沪寅斧次蓄隔噶挖沛扣蛆偏响筑榜疯胚窿孵纬弄边氧急位橇筏牧面放董编译原理第6章 LR分析课件编译原理第6章 LR分析课件 二、SLR(1)分析表： 将例中的情况一般化：根据不同的向前看符号将状态Si中的各个项目所对应的动作加以区分，从而解决冲突动作。 1.设