第12讲-语法分析-VIII-浅色

1、！温故知新温故知新回顾回顾v活前缀活前缀v活前缀的识别活前缀的识别vLR(0)LR(0)项目集项目集v构建识别活前缀的构建识别活前缀的DFADFA2LR(1)LR(1)分析练习题目分析练习题目3LR(1)LR(1)分析练习解答过程分析练习解答过程v1.1.对原文法进行拓广对原文法进行拓广 ( (添加产生式添加产生式S-S-S S ) )v2.2.拓拓广广文法文法S S 的的LR(0)LR(0)项目集规范族项目集规范族4拓广文法拓广文法G G 的的LR(0)LR(0)项目集规范族项目集规范族5I0:S SS V=ES EV *EV idE VI1:SS I2:SV =EEV I3:SE I4:V

2、* EE V V *EV idI5:Vid I6:SV= EE VV *EV idI7:V*E I8:EV I9:SV=E 识别产生式文法活前缀的识别产生式文法活前缀的DFADFAidS SS V=ES EV *EV idE VV id S V =EE V S S I0I1I2I5S E I3V * EE VV idV * EI4SV*idES V = EE VV *EV idI6=ES V=E E V VVI8idI3*V *E EI7I96本讲纲要本讲纲要vSLR(1)SLR(1) SLR(1)SLR(1)分析表的构造分析表的构造 SLR(1)SLR(1)文法描述能力有限文法描述能力有限v

3、LR(1)LR(1)分析分析vLALRLALRvLRLR文法和文法和LRLR分析方法的特点分析方法的特点73.53.5 LRLR分析器分析器83.53.5 LRLR分析器分析器93.53.5 LRLR分析器分析器10v一般性构造过程一般性构造过程 首先对文法进行拓广首先对文法进行拓广 添加产生式添加产生式S-SS-S 构建识别活前缀的构建识别活前缀的DFADFA 基于基于DFADFA构建分析表构建分析表11121314本讲纲要本讲纲要vSLR(1)SLR(1) SLR(1)SLR(1)分析表的构造分析表的构造 SLR(1)SLR(1)文法描述能力有限文法描述能力有限vLR(1)LR(1)分析分

4、析vLALRLALRvLRLR文法和文法和LRLR分析方法的特点分析方法的特点15SLR(1)SLR(1)文法的弱点文法的弱点vSLR(1)SLR(1)文法描述能力有限文法描述能力有限16每个SLR(1)文法都不是二义的，但是，有许多非二义的文法不是SLR(1)。SLR(1)SLR(1)文法的弱点文法的弱点vSLR(1)SLR(1)文法描述能力有限文法描述能力有限17温故知新温故知新本讲纲要本讲纲要vSLR(1)SLR(1) SLR(1)SLR(1)分析表的构造分析表的构造 SLR(1)SLR(1)文法描述能力有限文法描述能力有限vLR(1)LR(1)分析分析vLALRLALRvLRLR文法和

5、文法和LRLR分析方法的特点分析方法的特点19LR(1)LR(1)文法文法v与与SLR(1)SLR(1)文法的区别文法的区别 项目集的定义发生了改变项目集的定义发生了改变v添加了前向搜索符添加了前向搜索符v项目集改变的目的是增强描述能力项目集改变的目的是增强描述能力2021有效有效22有效有效23LR(1)文法v怎么加前向搜索符？初始项目集I0： SS, $ 将$作为向前的搜索符计算闭包CLOSURE(I) (a) I中的任何项目都属于CLOSURE(I) (b) 若有项目 AB, a在CLOSURE(I)中，而B 是文法中的产生式，b是FIRST(a)中的元素，则B, b也属于CLOSURE

6、(I)通过这个来保证在用B 进行归约后，出现的输入字符b是句柄B中B的后继符号，或者是B归约为A后可能出现的终结符24构建构建LR(1)LR(1)项目集项目集v例：例：25构建构建LR(1)LR(1)项目集项目集v例：例：26构建构建LR(1)LR(1)项目集项目集v例：例：27这一项的加入，这一项的加入，使得闭包中又要使得闭包中又要加入新元素！加入新元素！构建构建LR(1)LR(1)项目集项目集v例：例：28LR(1)LR(1)分析分析v从另一个例子来完整地看一下构建识别活从另一个例子来完整地看一下构建识别活前缀的前缀的DFADFA的过程的过程29构造规范的构造规范的LRLR分析表分析表30

7、构造规范的构造规范的LRLR分析表分析表31构造规范的构造规范的LRLR分析表分析表32S SS BBB bBB aS S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1SS BB, $B bB, $B a, $ I2BB 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构造规范的构造规范的LRLR分析表分析表 如果如果 A A , , a a 在在I Ii i中，且中，且A A S S

8、，那么置那么置actionaction i i, , a a 为为rjrj . .33构造规范的构造规范的LRLR分析表分析表34本讲纲要本讲纲要vLR(1)LR(1)分析分析vLALRLALRvLRLR文法和文法和LRLR分析方法的特点分析方法的特点35LALRLALRv从前面的例子看到，从前面的例子看到，LR(1)LR(1)分析表的状态数目比较分析表的状态数目比较大大vLALRLALR是在是在SLR(1)SLR(1)和和LR(1)LR(1)之间进行了文法描述能力之间进行了文法描述能力与分析表紧凑程度之间做的折衷与分析表紧凑程度之间做的折衷 SLR(1)SLR(1)文法描述能力稍弱，而由于状

9、态数目较小能够文法描述能力稍弱，而由于状态数目较小能够得到高效实现（不必消耗太多内存）得到高效实现（不必消耗太多内存） LR(1)LR(1)文法描述能力较强，但是由于状态数目多，分析文法描述能力较强，但是由于状态数目多，分析表较大表较大 LALRLALR的描述能力与分析表大小介乎的描述能力与分析表大小介乎SLR(1)SLR(1)与与LR(1)LR(1)之间之间36LALRLALRvLALRLALR的做法：的做法：v合并识别 LR(1)文法的活前缀的DFA中的同心项目集v同心的同心的LR(1)LR(1)项目集项目集B B bBbB, $, $ 与与 373.53.5 LRLR分析器分析器383.

10、53.5 LRLR分析器分析器39B bB, b/aB bB, b/aB a, b/a I3B bB, $B bB, $B a, $ I63.53.5 LRLR分析器分析器40LALR41LALR42LALR43LALR44LALR45LALR46LALR47LALR48LALR49构造LR(1)项目集规范族C = I0, I1, , In。寻找LR(1)项目集规范族中同心的项目集，用它们的并集代替它们。按构造规范的LR(1)分析表的方式进行构造。50LR(1)LR(1)分析练习题目分析练习题目51LR(1)LR(1)分析练习解答过程分析练习解答过程v答：答：vStep 1. Step 1.

11、对原文法进行对原文法进行拓广拓广 ( (添加产生式添加产生式S-SS-S) )52拓广文法拓广文法G G 的的LR(0)LR(0)项目集规范族为：项目集规范族为：53I0:S SS V=ES EV *EV idE VI1:SS I2:SV =EEV I3:SE I4:V* EE V V *EV idI5:Vid I6:SV= EE VV *EV idI7:V*E I8:EV I9:SV=E 识别产生式文法活前缀的识别产生式文法活前缀的DFADFAidS SS V=ES EV *EV idE VV id S V =EE V S S I0I1I2I5S E I3V * EE VV idV * EI4SV*idES V = EE VV *EV idI6=ES V=E E V VVI8idI3*V *E EI7I954LR(1)LR(1)分析练习解答过程分析练习解答过程vStep 2: Step 2: 构建识别（拓广）文法活前缀构建识别（拓广）文法活前缀的的DFADFA55作业