LR分析器SLR规范的LR

1、LRLR分析器（分析器（SLRSLR，规范的，规范的LRLR）4.6-4.74.6-4.7SLR4.5 LR分析器分析器 4.5.3 构造构造SLR分析表分析表v术语：术语：LR(0)项目项目（简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式4.5 LR分析器分析器 4.5.3 构造构造SLR分析表分析表v术语：术语：LR(0)项目项目（简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态4.5 LR分析器分析器 4.5.3 构造构造SLR分析表分析表v术语：术语：LR(

2、0)项目项目（简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态exprexpr+term 4.5 LR分析器分析器 4.5.3 构造构造SLR分析表分析表v术语：术语：LR(0)项目项目（简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态exprexpr+term*termfactor 4.5 LR分析器分析器 4.5.3 构造构造SLR分析表分析表v术语：术语：LR(0)项目项目（简称（简称项目项

3、目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态exprexpr+term*termfactor 4.5 LR分析器分析器 4.5.3 构造构造SLR分析表分析表v术语：术语：LR(0)项目项目（简称（简称项目项目）在右部的某个地方加点的产生式在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态加点的目的是用来表示分析过程中的状态v例例 AXYZ对应有四个项目对应有四个项目A XYZA XYZA XYZA XYZ例例 A 只有一个项目和它对应只有一个项目和它对应A 4.5 LR分析器分析器 构造构造

4、SLR分析表的两大步骤分析表的两大步骤1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2、从上述、从上述DFA构造分析表构造分析表4.5 LR分析器分析器 1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA1）拓广文法）拓广文法E E + T | TT T F | F F ( E ) | id 4.5 LR分析器分析器 1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA1）拓广文法）拓广文法E E E E + T | TT T F | F F ( E ) | id 4.5 LR分析器分析器 1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2）构造）构

5、造LR(0)项目集规范族项目集规范族I0:E E4.5 LR分析器分析器 1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:E EE E + T E T4.5 LR分析器分析器 1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:E EE E + T E TT T F T F4.5 LR分析器分析器 1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:E EE E + T E TT T FT FF (E)F

6、id4.5 LR分析器分析器 1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0:E E( (核心项目核心项目) )E E + T E T( (非核心项目，非核心项目，T T F 通过对核心项目求闭包通过对核心项目求闭包T F 而获得而获得) )F (E)F id4.5 LR分析器分析器 1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0: I1:E EE E E E + T E E + T E TT T F T FF (E)F idE4.5 LR分析器分析器 1、从文法

7、构造识别可行前缀的、从文法构造识别可行前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0: I1:E EE E E E + T E E + T E TT T F I1 := goto ( I0, E )T FF (E)F idE4.5 LR分析器分析器 1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2）构造）构造LR(0)项目集规范族项目集规范族I0: I1:E EE E E E + T E E + T E TT T F I2:T FE T F (E)T T F F idET4.5 LR分析器分析器 1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2）构

8、造构造LR(0)项目集规范族项目集规范族I0: I1:E EE E E E + T E E + T E TT T F I2:T FE T F (E)T T F F id I3: T F ETF4.5 LR分析器分析器 I0: I4:E EF (E ) E E + T E TT T FT FF (E)F id(4.5 LR分析器分析器 I0: I4:E EF (E ) E E + T E E + T E TE TT T FT T FT FT FF (E)F (E)F idF id(4.5 LR分析器分析器 I0: I4:E EF (E ) E E + T E E + T E TE TT T FT

9、 T FT FT FF (E)F (E)F idF id I5:F id (id4.5 LR分析器分析器 I1I0EI3I2I4I5TF(id 4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI1:E E E E+ T 4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI1:E E E E+ TI6 :EE + TT T F T F F (E) F id +4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI1: I2:E EET E E+ TTT F I6 :EE + TT T F T F F (E) F id +4.5 LR分析器分析器 I1I0EI3

10、I2I4I5TF(idI1: I2:E EET E E+ TTT F I6 : I7:EE + TTT F T T F F (E) T F F id F (E) F id + 4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI3:T F 无状态转换无状态转换4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4:F (E )E E + TE TT T F T FF ( E )F id 4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F (E) E E + TE E+ T E TT T F T FF ( E )F id E4.5

11、LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id TE4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id I3:TF TFE4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id

12、 I3:TF I4: F (E ) . . .TF(E4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TT F F id I3:TF I4: I5: F (E ) F id . . .TF(idE4.5 LR分析器分析器 I1I0EI3I2I4I5TF(idI5:F id 无状态转换无状态转换4.5 LR分析器分析器 I1I0+EI6I3I2I4I8I7I5指向指向I2指向指向I3T* *F(Eidid(FT4.5 LR分析器分析器 I1I0+指向指向I7EI6I9I

13、3I2I4I11I8I7I10* *TI5指向指向I4指向指向I3指向指向I5指向指向I4指向指向I5指向指向I6指向指向I2指向指向I3F(FTid* *id(F(Eid+)id(FTE E E+T E+T F E+T id E+T F id把所有状态都把所有状态都作为接受状态作为接受状态这是一个这是一个DFAE+T F 的所有前缀都可接受的所有前缀都可接受4.5 LR分析器分析器 I0:E EE E + TE TT T FT FF (E)F id 也可以构造一个识别可行前缀的也可以构造一个识别可行前缀的NFA N例子v1. 给出接受文法S-(L)|a L-L,S|S的活前缀的一个DFA答案

14、-1例子v2. 求接受文法S-Aa|bAc|dc|bdaA-d的活前缀DFA和SLR(1)分析表答案-2（DFA）答案-2（状态分析表）4.5 LR分析器分析器 构造构造SLR分析表的两大步骤分析表的两大步骤1、从文法构造识别可行前缀的、从文法构造识别可行前缀的DFA2、从上述、从上述DFA构造构造分析表分析表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 第二

15、项目使得第二项目使得action2, = 为按为按EV归约，因为归约，因为=是是E的一个后继符的一个后继符=是是E的一个后继符：的一个后继符： S $ V = E $ E = E $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的一个后继符的一个后继符在所关注场合在所关注场合

16、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看出：

17、看出： 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

18、 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函数如下确函数

19、如下确定定如果如果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

20、 : S S， $S V = E, $S E, $V E, =/$V id, =/$ E V, $I2 : S V = E, $E V , $V 4.5 LR分析器分析器 4.5.5 构造构造LALR分析表分析表v研究研究LALR的的原因原因规范规范LR分析表的状态数偏多分析表的状态数偏多vLALR特点特点LALR和和SLR的分析表有同样多的状态，比规范的分析表有同样多的状态，比规范LR分析表要小得多分析表要小得多LALR的能力介于的能力介于SLR和和规范规范LR之间之间LALR的能力在很多情况下已经够用的能力在很多情况下已经够用vLALR分析表构造方法分析表构造方法通过合并规范通过合并规范L

21、R(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, $

22、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, $

23、 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,

24、$ 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

25、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/$ I3