LR分析器SLR规范的LR课件.ppt

上传人(卖家):三亚风情 文档编号:3044459 上传时间:2022-06-25 格式:PPT 页数:70 大小:1.43MB
下载 相关 举报
LR分析器SLR规范的LR课件.ppt_第1页
第1页 / 共70页
LR分析器SLR规范的LR课件.ppt_第2页
第2页 / 共70页
LR分析器SLR规范的LR课件.ppt_第3页
第3页 / 共70页
LR分析器SLR规范的LR课件.ppt_第4页
第4页 / 共70页
LR分析器SLR规范的LR课件.ppt_第5页
第5页 / 共70页
点击查看更多>>
资源描述

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,

26、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

27、 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/$ I

28、89BbBa栈栈 输入输入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构造E-E+id|id的SLR(1)文法练习v构造下列文法的SLR,规范LR(1)vS-V=EvS-EvV-*EvV-idvE-V

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(LR分析器SLR规范的LR课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|