当前位置：首页 > news >正文

LR(0)

news 来源：原创 2025/8/29 17:54:31

在这里插入图片描述
LR0就是当我处在自动机为红色这些结束状态的时候，这些红色状态就代表我们识别到了一个句柄，那现在的问题就是识别到了句柄，那要不要对他进行归约？LR0就是我不管当前指针指向的终结符是什么，我都拿它做规约

在这里插入图片描述
这里的二号状态就是，我这个点已经到了最后，那么我这个第二个状态这一行，不管碰到哪个终结符，都用2号产生式规约，而且现在这里还不是LR0文法，因为有一个空有冲突，那能不能消除冲突，那就要加强条件，比如说不能像LR0一样，不管咋样，不管遇到那个终结符我都武断的到了最后就归约。坚强条件让他看看当前的输入，考虑一下能不能做规约。
先看个这个例子，再泛化一下，看能不能实现加强
在这里插入图片描述

按理来说，我们要把T换成E，把T弹出去，E压进来。
在这里插入图片描述
而对于自动机来说，这个过程就是先回到0状态，再压入E，那就走到1状态。这个时候我们就发现问题了。1状态的出边可以是S，可以是+，但是没有星号出边，那就卡在这一步了，因此之前那里就不要做规约。但现在的问题是，我想立马知道不能归约，而不是说我这样操作一下，后面到某一部之后操作不下去，卡住了，才知道不能这么走。
一部分由栈底到栈顶，一部分是当前还未处理的输入流，这两部分一起构成当前的句型，那我们看这个句型。
这个栈顶E，和当前未处理的 *，他们是紧挨着的，我要当前能碰到星号做归约，哪一个必要条件就是星号能跟在E后面。因为你用E换了T，E就是栈顶了，当前面对的是星号。如果我希望做规约的话，那么星号要能紧跟在E后面，这是一个必要条件。必要条件就是要能跟在你要规约的产生式的左部那个非终结符的后面。有没有联想到一个概念，跟在一个非终结符的后面，就是follow集合。
我们现在来算算这个follow集合，没有星号，所以就不要规约在这里插入图片描述

现在抛开例子，我们比较general的来说一下。对于下图这个例子，我们考虑的是，能不能拿这个句柄，在当前看到t的情况下，做规约。如果规约的话，我们看栈的状态
在这里插入图片描述
当前句型由两部分构成，这个句型就要求t能跟在A的后面，这样才能归约
所以我们就得到了这样一个条件。原来对于LR0而言，如果出现这样一个句柄，我不管什么其他条件，我这一行都填s，做规约。而现在我们要这个终结符能跟在非终结符后面才能归约，这样得到的一个语法分析算法叫做Simple SR1，在这样一个条件下我们的分析表就没有冲突了。

在这里插入图片描述
对于这个例子而言，SR1已经没有冲突了，那还没有其他例子能够让他有冲突？也就是有没有非SR1文法

归约/归约冲突就是可以用两个产生式归约。没有移入/移入冲突，当前移入的符号就一个，没有什么可以冲突的。
接下来我们看一个非SLR1文法，我们看看为什么冲突，为什么SLR解决不了，从而在加强条件得到一种更强大的SR1算法
在这里插入图片描述
图上这个文法表示的是c++中的指针用法。我们现在就看二号状态，有一个移入归约冲突。如果当前面对一个等号的话，那就可以移入，从而转移到状态6；那如果选择归约的话呢，那我们就要看当前面对的这个等号是否能跟在规约的这个产生式的左部的后面，也就是是否 =∈FOLLOW®。然后我们发现的确是属于的，那我们按照之前SLR1的要求，也可以做规约，那么这里就产生了移入归约冲突。我们怎么去解决这个移入归约冲突呢？在这里插入图片描述
虽然我们满足这个条件，那应不应该做规约呢，因为我们之前说过他只是一个必要条件，不是充要条件，所以我们要对这个必要条件再加强一下，我们要先分析一下不能做规约的原因，找到这个原因，我们再加强一下，就得到了更强的规约条件。原因的话我们要看到整个自动机才好分析在这里插入图片描述
我们拿它做规约的话。在自动机上的体现就是把R弹出来，从q2回到q0，把R压进去，那就到了q3状态，我们就看到了q3状态，这里有一个等号，会出现什么情况。我们把栈的情况也画出来看看。现在我们其实是说等号属于FOLLOW（R）不够，那我们回想一下这个FOLLOWR我们之前是怎么算的，我们纯粹是看到了文法的静态文本，是静态分析，我们做所有可能的推导，这个结果是很粗糙的，当你真正的去分析一个输入的时候，你肯定不是无缘无故来到q2的，肯定有一个路径让你来到q2，这是一个动态信息，你的静态FOLLOWR是比较粗糙的，你的路径应该能帮你排除一些终结符，从而让你在某些情况下不归约。分析下面这个栈，我们可以知道R下面一定是个0号状态，这个是静态文本体现不出来的，你必须是跑这个自动机才能体现出来，我在把L弹出去之后，进入到q0，这个q0一定是栈底，不可能是站中间的一个部分，他只可能在最开始的时候进入，因为他没有入边，不可能再次来到这个状态，只有当上千的状态都弹出来，这个状态才会暴露出来，所以只会是栈底，只会是栈底就意味着R后面跟着=，这个部分一定是最前面的，一定是以它打头的
在这里插入图片描述
我们从属于FOLLOWR，我们得出的结论是等号可能出现在R后面，这点是从静态文本得出的。经过我们在自动机的分析，我们得到了更多的动态的信息，我们又能进一步加强这个结论，这个结论是说等号在FOLLOWR后面，那么在满足这个条件的句型中，一定是以R=开头的句型。然而在这里插入图片描述
所以直接做归约是不够的，我们希望的是你能获取一些动态信息，我在这个状态上发现的句柄，他能不能做规约，还和他是怎么从初始状态来到这个状态有关，这一路的信息我们都希望能分析一下，帮助我们在魔偶个状态能不能归约做一个判断。下面就来到我们更强的一个语法分析算法，这个语法分析算法最重要的就是下面这一页。我们也只是尽可能精确，无法做到百分百精确，我们现在一路走来都是从一个什么都不加的规约，到考虑一下follow集合，然后我们现在再把它精确一步，我们只是想做尽可能精确。
假设当前面对的是t，我能不能用A->a这条做规约，我们要进一步加强对t的约束
在这里插入图片描述
那么我们就看这个Ij项之前的项集，其实就是把那个点往前移一位，到了Ii，特殊的情况就是直接回到了I0，当然我们在这里考虑一般一点的情况。除了A->a，我们还要找闭包的情况，那这个图有了，那有没有看到对t更强的要求。我们还要and上什么条件？在这里插入图片描述
那么其实我们就要前一个项集的紧跟着A的那个符号的first，我们的t要在这个first里面。但是其实也可以简化一下，我们属于First（γ）的也一定属于FOLLOW（A），这也说明了我们其实是把原来的条件加强了。
在这里插入图片描述
就是在i这个状态求闭包的时候，我们把伽马这个信息丢失了，我们希望在对某个项求闭包的时候把这个伽马的信息给带上，这样的话，可以把所有的项都带上伽马，这样我们在goto其他状态的时候，也有了这个信息，那么我们现在就来改造一下这个文法。
在这里插入图片描述

那么这个项表示什么呢？我们画一个栈来表示一下，看小数点的位置，在alpha的后面，说明我们当前的栈顶元素是alpha，然后剩下的输入（我们期望的）是β和alpha
在这里插入图片描述

太神奇了，我其实感觉听老师的就是讲的每一小部分内容都听明白了，但是还是没有串起来，已经开始晕了，结果问了一下ai一下就懂了，谁懂啊。

您说得对，我没有完全理解您的问题。您是在问为什么要限制FIRST(γ)，而不直接使用FOLLOW(A)。分析您的问题:
在LR(0)自动机中，如果项集Ij中包含[A → α·]，而在之前的项集Ii中包含[B → β·Aγ]与[A →
·α]，按照图中红框标注的内容，归约条件是"只有当α ∈ FIRST(γ)时，才可以进行A → α归约"。
您的疑问是为什么不直接使用FOLLOW(A)集合作为归约条件。
这是一个很好的问题。理论上，FOLLOW(A)确实表示可能在A之后出现的所有终结符，但在这个特定的上下文中：

FIRST(γ)提供了更精确的信息 - 它专门指出在这个特定的产生式[B → β·Aγ]中，A后面实际跟随的是γ，而不是任何可能跟在A后面的符号。(最重要的就是这条了，这里的意思就
是保存了一路走来的路径信息，因为我们找的是上一个项集的[B → β·Aγ]，而不是那个静态的文本)
使用FIRST(γ)而不是FOLLOW(A)可以减少冲突 - FOLLOW(A)可能包含很多在其他上下文中跟随A的符号，但在当前文法位置不适用。
这种限制确保了归约操作只在γ可能开始的情况下进行，使分析更加精确。您的直觉是对的，在构造LR(1)或LALR(1)分析器时，我们确实会使用FOLLOW集合信息。但在图中描述的特定情景中，使用FIRST(γ)能提供更精确的上下文相关信息，减少不必要的归约行为。

注意是之前的某个项集

为什么一定要first 伽马，再提醒自己一边，看上图，因为我们在求闭包的时候，丢失了伽马的信息。LR0在做闭包，我们goto的时候伽马的信息也没有带过来。所以接下来我们要改造一下LR0，使其能让我们对某个项求闭包的时候能把伽马这个信息给带上，到其他项集的时候这个信息也一路带过去。
首先改造LR0，我们就把LR0的项的定义先改一下，原来我们只有前面的部分，现在我们搞个逗号，加一个a，这个a就是我们向前看的符号，其实就可以理解成first伽马。这里其实first伽马是一个集合，那其实有多个这样子的项，我们只是把它拆开了

在这里插入图片描述
我们还是先来从自动机入手，构造LR1自动机有两个关键的操作，一个是：一个状态内部我们要做闭包操作，经过前面的分析我们知道这是一个关键点
在求绿色这行的，也就是上面这一行的闭包的时候，我们要把β的信息带下来，这是做闭包的一个关键点。在这里插入图片描述

有上面这样一个项，我们现在要对他求闭包，产生式是B->gama，前面的部分放小数点跟LR0是一样的，b是什么呢？可能是一个集合。对于任何满足first这个条件的，我们都写一个项把它放进去。满足b∈βa，这里就是把β和a钉在一起，这是为什么？因为对于扇面这个产生式而言，他的意思是alpha后面可能会出现Bβ，那现在我们要去追踪大B了在这里插入图片描述

相关文章：