LR分析器.pptx

LR分析器（LALR）4.7基于栈的LR分析4.5 LR分析器分析器 v例例 E E+T|E T 下表绿色部分构成下表绿色部分构成 T T F|T E识别可行前缀识别可行前缀DFA的的 F (E)|F id状态转换表状态转换表状态状态动动 作作 转转 移移 id +()$E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 4.5 LR分析器分析器 栈栈 输输 入入 动动 作作 0 id id+id$移进移进 0 id 5 id+id$按按F id归约归约 0 F 3 id+id$按按T F归约归约 0 T 2 id+id$移进移进 0 T 2 7 id+id$移进移进 0 T 2 7 id 5 +id$按按F id归约归约 0 T 2 7 F 10 +id$按按T T F归归约约.0 E 1$接受接受 SLR4.5 LR分析器分析器 4.5.3 构造构造SLR分析表分析表v术语：术语：LR(0)项目项目（简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态v例例 AXYZ对应有四个项目对应有四个项目A XYZA XYZA XYZA XYZ例例 A 只有一个项目和它对应只有一个项目和它对应A 4.5 LR分析器分析器 构造构造SLR分析表的两大步骤分析表的两大步骤1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2、从上述、从上述DFA构造分析表构造分析表例子v1.给出接受文法S-(L)|a L-L,S|S的活前缀的一个DFA答案-1例子v2.求接受文法S-Aa|bAc|dc|bdaA-d的活前缀DFA和SLR(1)分析表答案-2（DFA）答案-2（状态分析表）练习v构造E-E+id|id的SLR(1)文法答案SLR分析v构造SLR分析表的两大步骤从文法构造识别可行前缀的DFA从上述DFA构造分析表vShiftvReduce-整个表达式执行完成vAccept-只有归约到开始符号规范的LR练习v构造下列文法的SLRS-V=ES-EV-*EV-idE-V答案4.5 LR分析器分析器 v例例 SLR(1)文法的描述能力有限文法的描述能力有限S V=ES E V EV id E V I0:S S S V=ES E V EV id E V I2:S V =EE V V 第一项目使得第一项目使得action2,=s6 第二项目使得第二项目使得action2,=为按为按EV归约，因为归约，因为=是是E的一个后继符的一个后继符在所关注场合在所关注场合E的后继是的后继是$：S$V=E$E=E$S$E$V$4.5 LR分析器分析器 4.5.4 构造规范的构造规范的LR分析表分析表LR(1)项目：项目：重新定义项目重新定义项目，让它带上搜索符，成为如下形式让它带上搜索符，成为如下形式A ,aLR(1)项目项目A ,a对可行前缀对可行前缀 有效：有效：如果存在着推导如果存在着推导S *rm Aw rm w，其中：其中：=；a是是w的第一个符号，或者的第一个符号，或者w是是 且且a是是$4.5 LR分析器分析器 v例例 S BBB bB|a从最右推导从最右推导S*rm bbBba rm bbbBba看出：看出：BbB,b对可行前缀对可行前缀 =bbb是有效的是有效的 对于项目对于项目A ,a，当当 为空时，是根据搜为空时，是根据搜索符索符a来填表（归约项目），而不是根据来填表（归约项目），而不是根据A的后继符的后继符来填表来填表4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/a4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/a I3B a,b/a I4ab4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/a I3B a,b/a I4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/a I8BbbBaaB4.5 LR分析器分析器 构造规范的构造规范的LR分析表分析表(1)基于基于LR(1)项目来构造识别项目来构造识别G 可行前缀的可行前缀的DFA(2)从从Ii构造分析器的状态构造分析器的状态i,状态状态i的的action函数如下确函数如下确定定如果如果A a,b在在Ii中，且中，且goto(Ii,a)=Ij，那那么置么置actioni,a为为sj如果如果A ,a在在Ii中，且中，且A S，那么置那么置actioni,a为为rj 如果如果SS,$在在Ii中，那么置中，那么置actioni,$=acc如果用上面规则构造出现了冲突，那么文法就不是如果用上面规则构造出现了冲突，那么文法就不是LR(1)的的4.5 LR分析器分析器 v先前基于先前基于SLR(1)有移进有移进-归约冲突的例子，在归约冲突的例子，在基于规范基于规范LR(1)时无冲突时无冲突S V=ES E V EV id E V I0:S S，$S V=E,$S E,$V E,=/$V id,=/$E V,$I2:S V =E,$E V,$V LALR4.5 LR分析器分析器 4.5.5 构造构造LALR分析表分析表v研究研究LALR的的原因原因规范规范LR分析表的状态数偏多分析表的状态数偏多vLALR特点特点LALR和和SLR的分析表有同样多的状态，比规范的分析表有同样多的状态，比规范LR分析表要小得多分析表要小得多LALR的能力介于的能力介于SLR和和规范规范LR之间之间LALR的能力在很多情况下已经够用的能力在很多情况下已经够用vLALR分析表构造方法分析表构造方法通过合并规范通过合并规范LR(1)项目集来得到项目集来得到4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/a I3B a,b/a I4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/a I8BbbBaaBI4和和I7仅搜索符不一样仅搜索符不一样4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/a I3B a,b/a I4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/a I8BbbBaaBI4和和I7合并合并4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/a I3B a,b/a I4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/a I8BbbBaaB输入为输入为bbabba$4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/a I3B a,b/a I4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/a I8BbbBaaB输入为输入为bba$4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/aB bB,b/aB a,b/a I3B a,b/a I4aabbS BB,$I5B bB,$B bB,$B a,$I6B bB,$I9B a,$I7B bB,b/a I8BbbBaaB有三组同心集，都合并有三组同心集，都合并4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈 输入输入0 bba$4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈 输入输入0b36 ba$4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈 输入输入0b36b36 a$4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈 输入输入0b36b36a47$4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈 输入输入0b36b36B89$4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈 输入输入0b36B89$4.5 LR分析器分析器 S S,$I0S BB,$B bB,b/aB a,b/aS S,$I1S BB,$B bB,$B a,$I2SBB bB,b/a/$B bB,b/a/$B a,b/a/$I36B a,b/a/$I47aabbS BB,$I5B bB,b/a/$I89BbBa栈栈 输入输入0B2$报错报错练习v构造下列文法的规范LR(1)S-V=ES-EV-*EV-idE-V答案