更强的LR分析方法SLR(1)与LR(1)

SLR(1)分析法

LR0文法比较简单,描述的语言也比较有限,如下面这个文法不属于LR0,先构造LR0项目集规范族可以看出。

image-20201105132720543

注意 I1 I2 I9出现了移进和归约的冲突

消解移进归约冲突是有可能的,可以细分

如,当前输入的单词不在要归约生成的A的FOLLOW集中,那不能采取归约动作。

image-20201105133423541

如,当前单词是+时,那它不在S‘的FOLLOW集合中,不采用归约,而是采用移进。 相当于向后看了一个单词,所以是1不是0

SLR1冲突解决方法

image-20201105145739101

将这个方法一般化后得到

image-20201105150215292

称为 SLR(1)冲突解决方法

SLR分析表构建

文法拓广

  1. 开始符号只有唯一产生式
  2. G’只有唯一的接收状态
  3. 文法开始符号不会出现在产生式右部

image-20201105150607521

最重要的还是第三步——构造ACTION和GOTO表,和LR0分析表构造有差异。

image-20201105150921480

主要注意第二步,如果状态集中存在归约项目,遇到该非终结符的FOLLOW集中的终结符时,进行归约(使用对应该归约项目的产生式)。

与LR0分析表的区别,LR0分析表的归约是不加区分的放在了Ik的所有列,而SLR1先要判断这一列对应的符号在非终结符的FOLLOW集中,减少了冲突

image-20201105151345712

image-20201105151505829

构建示例

对于之前的非LR(0)文法来说

image-20201105151552773

当前已经拓广了文法以及构建了DFA。之后需要消解冲突

注意,(待约项目的)非终结符FOLLOW集中不能有同一项目集中移进项目需要的符号,如下面两个FOLLOW集对于I1,S'的FOLLOW集没有出现+号(+号是归约时需要的符号),对于I2,E的FOLLOW集中没有出现*号。

FOLLOW集怎么求,还不够熟练

image-20201105151906914

image-20201105153608889

注意状态1的状态转换函数,分别检查了待约和移进项目,仅对于指定的符号进行状态转换。

状态2也是,如果采用的是之前LR0分析方法,*这一列会同时出现移进s7和归约r2冲突。

注意第三个状态,虽然只有一个待约项目,但是也进行了FOLLOW集的检测。

LR1分析法

SLR1分析法的局限性

SLR冲突消解方法还是存在一些问题。如在同一个项目集中,归约项目的非终结符的FOLLOW集和移进项目期待的下一个终结符(点后面的终结符)有交集。

但是实际上状态二位于分析栈栈顶,面临输入符号=时,也不能归约,因为所有的规范句型中,不存在R=为前缀的规范句型,只有以*R=为前缀的规范句型(在L0中),之所以=能在R的FOLLOW集中,是因为R前面有*。

所以状态2处于栈顶时,面临输入串=是不能按照I2中的归约项目进行归约的。

FOLLOW集合计算得到的超前符号集合可能大于实际能够出现的超前符号集!!存在局限性 如该表中

*R后面才能加=号

image-20201108001621123

image-20201108001913731

所以我们需要更加精确的预测信息,不能只看FOLLOW集合,来判断下一步操作,所以需要LR1分析方法。

构造LR1分析表

image-20201108004601638

image-20201108002107013

LR1的项目

a1a2ak是终结符,称为向前搜索串(展望串),每个状态除了LR(0)项目,还有和项目相关的展望信息。而不是用FOLLOW集合做展望。

展望串对归约项目具有指导意义。

如能否把α归约为A,还需要看后面的k个终结符。如果是SLR中,只需要后面的一个单词在FOLLOW集合中即可归约,这点它们是不同的。

对于移进项目,展望串没有直接意义,随着点向后移动,展望串最终传递到规约项目。

一般只使用k=1的情况

image-20201108002448371

LR1有效项目

α和β都形成,即将归约的时候,面临的单词应该是a。

image-20201108002929848

之所以是βa的FIRST集,因为β可能是空串。

image-20201108003351049

LR1项目集规范族

image-20201108003735053

image-20201108003834978

通过计算有效项目,构造项目集规范族

第一个项目的展望串是#,因为希望归约到开始符时,所有的串都处理完了,面临句末符。

image-20201108004426046

分析表构造

image-20201108004650350

注意归约项目仅仅放在 a的那一列,(SLR1中放在FOLLOW集合中的列)

第四项指的是归约到A后,对应状态j

image-20201108005059737

image-20201108005115118

使用了更加精确的展望信息。

展望信息哪来的??

image-20201108005309122

image-20201108005429115

构造示例

I0中第三项展望串为a或b的原因,aB归约成B的时候,后面跟着的会是B(第二项),B的开头是a或者b。

注意I2中的展望串变了,因为后面没有东西了(这是第二个B)。

I3中a后面期望的是B,B的开头是a/b

另外注意I6,识别a后剩下的B是在末尾的B,所以展望串是#,因为后面不会再有一个额外的B,和I3不一样。

注意,移进项目的展望串传递到了后面的归约项目

image-20201108010651991

image-20201108011253258

分析示例

image-20201108011942416

LR分析器,总是根据当前栈顶与当前单词查找分析表,只向前检查一个单词,所以称为LR1分析。

文章目录