LR分析器（SLR,规范的LR）.ppt

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

2、状态,4.5 LR分析器,4.5.3 构造SLR分析表术语：LR(0)项目（简称项目）在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态,4.5 LR分析器,4.5.3 构造SLR分析表术语：LR(0)项目（简称项目）在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态例AXYZ对应有四个项目A XYZA XYZA XYZA XYZ例A 只有一个项目和它对应A ,4.5 LR分析器,构造SLR分析表的两大步骤1、从文法构造识别可行前缀的DFA2、从上述DFA构造分析表,4.5 LR分析器,1、从文法构造识别可行前缀的DFA1）拓广文法E E + T | TT T F

3、| 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）构造LR(0)项目集规范族I0:E E,4.5 LR分析器,1、从文法构造识别可行前缀的DFA2）构造LR(0)项目集规范族I0:E EE E + T E T,4.5 LR分析器,1、从文法构造识别可行前缀的DFA2）构造LR(0)项目集规范族I0:E EE E + T E TT T F T F,4.5 LR分析器,1、从文法构造识别可行前缀的DFA2）构造LR(

4、0)项目集规范族I0:E EE E + T E TT T FT FF (E)F id,4.5 LR分析器,1、从文法构造识别可行前缀的DFA2）构造LR(0)项目集规范族I0:E E(核心项目)E E + T E T(非核心项目，T T F 通过对核心项目求闭包T F 而获得)F (E)F id,4.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 id,4.5 LR分析器,1、从文法构造识别可行前缀的DFA2）构造LR(0)项目集规范族I0: I1:E EE E E

5、 E + T E E + T E TT T F I1 := goto ( I0, E )T FF (E)F id,4.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 id,4.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 id I3: T F,4.5 LR分析器,I0: I4:E EF

6、 (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 T FT FT FF (E)F (E)F idF id I5:F id,4.5 LR分析器,4.5 LR分析器,I1:E E E E+ T,4.5 LR分析器,I1:E E E E+ TI6 :EE + TT T F T F F (E) F id,4

7、.5 LR分析器,I1: I2:E EET E E+ TTTF I6 :EE + TT T F T F F (E) F id,4.5 LR分析器,I1: I2:E EET E E+ TTTF I6 : I7:EE + TTTF T T F F (E) T F F id F (E) F id,4.5 LR分析器,I3:T F 无状态转换,4.5 LR分析器,I4:F (E )E E + TE TT T F T FF ( E )F id,4.5 LR分析器,I4: I8:F (E )F (E) E E + TE E+ T E TT T F T FF ( E )F id,4.5 LR分析器,I4:

8、I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TTF F id,4.5 LR分析器,I4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TTF F id I3:TF,4.5 LR分析器,I4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T FETF ( E )TTF F id I3:TF I4: F (E ) . . .,4.5 LR分析器,I4: I8:F (E )F (E) E E + TE E+ T E TT T F I2:T

9、FETF ( E )TTF F id I3:TF I4: I5: F (E ) F id . . .,4.5 LR分析器,I5:F id 无状态转换,4.5 LR分析器,4.5 LR分析器,E E E+T E+T F E+T id E+T F id,把所有状态都作为接受状态这是一个DFA,E+T F 的所有前缀都可接受,4.5 LR分析器,I0:E EE E + TE TT T FT FF (E)F id,也可以构造一个识别可行前缀的NFA N,例子,1. 给出接受文法S-(L)|a L-L,S|S的活前缀的一个DFA,答案-1,例子,2. 求接受文法S-Aa|bAc|dc|bdaA-d的活前

10、缀DFA和SLR(1)分析表,答案-2（DFA）,答案-2（状态分析表）,4.5 LR分析器,构造SLR分析表的两大步骤1、从文法构造识别可行前缀的DFA2、从上述DFA构造分析表,4.5 LR分析器,例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 $,4.5 LR分析器,例SLR(1)文法

11、的描述能力有限,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的第一个

12、符号，或者w是且a是$,4.5 LR分析器,例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/a,4.5 LR分析器,4.5 LR分析器,4.5 LR分析器,构造规范的LR分析表(1) 基于LR(1)项目来构造识别G可行前缀的DFA(2)从Ii构造分析器的状态i, 状态i的action函数如下确定如果A a, b在Ii中，且goto(Ii,

13、a) = Ij ，那么置actioni, a为sj如果A , a在Ii中，且A S，那么置actioni, a为rj 如果SS, $在Ii中，那么置actioni, $ = acc如果用上面规则构造出现了冲突，那么文法就不是LR(1)的,4.5 LR分析器,先前基于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,4.5 LR分析器,4.5.5 构造LALR分析表研究LALR的原因

14、规范LR分析表的状态数偏多LALR特点LALR和SLR的分析表有同样多的状态，比规范LR分析表要小得多LALR的能力介于SLR和规范LR之间LALR的能力在很多情况下已经够用LALR分析表构造方法通过合并规范LR(1)项目集来得到,4.5 LR分析器,I4和I7仅搜索符不一样,4.5 LR分析器,I4和I7合并,4.5 LR分析器,输入为bbabba$,4.5 LR分析器,输入为bba$,4.5 LR分析器,有三组同心集，都合并,4.5 LR分析器,4.5 LR分析器,栈 输入0 bba$,4.5 LR分析器,栈 输入0b36 ba$,4.5 LR分析器,栈 输入0b36b36 a$,4.5 LR分析器,栈 输入0b36b36a47 $,4.5 LR分析器,栈 输入0b36b36B89 $,4.5 LR分析器,栈 输入0b36B89 $,4.5 LR分析器,栈 输入0B2 $,报错,练习,构造E-E+id|id的SLR(1)文法,练习,构造下列文法的SLR，规范LR(1)S-V=ES-EV-*EV-idE-V,