SLR(1)和LALR(1)和Reduce

Question

我完全糊涂了！

我在我的一份教授笔记中读到了下面的例子。

我们使用SLR(1)语法分析器生成器生成G的语法分析表S，使用LALR(1)语法分析器生成器生成G的语法分析表L。

S->AB
A->dAa
A-> lambda (lambda is a string with length=0)
B->aAb

解决方案:S中具有R (reduce)的元素的数量大于L。

但在一个网站上，我读到：

2)假设T1，T2是用SLR(1)和LALR(1)为文法G创建的。如果G是SLR(1)文法，下列哪一项是正确的？

a) T1和T2没有任何区别。

c) T1中错误条目总数小于T2

解决方案：

LALR(1)算法生成与SLR(1)算法完全相同的状态，但它可以生成不同的操作；它能够解决比SLR(1)算法更多的冲突。然而，如果语法是SLR(1)，两个算法将产生完全相同的机器(a是正确的)。

编辑:事实上，我的问题是为什么对于给定的SLR(1)语法，LALAR(1)和SLR(1)的解析表是完全相同的，(错误和非错误条目相等，reduce的数量相等)，但对于上述语法，S中的reduce的数量多于L。

我在另一本书中看到，一般来说，我们有：

​

​

摘要：

1)对于我在问题1中写的上述语法，为什么reduced的数量不同？

2)如果我们有SLR(1)语法，为什么表是完全相同的？(减少的条目和错误条目的数量相同)

Answer 1

这两种说法都是正确的！

您的问题之一是为什么SLR(1)和LALR(1)解析器具有相同的状态。SLR(1)解析器是通过从LR(0)自动机开始，然后用以下集合中的先行信息扩充每个结果而形成的。在LALR(1)解析器中，我们从LR(1)解析器开始(其中每个产品都具有非常精确的先行信息)，然后将具有相同底层LR(0)状态的任何两个状态组合在一起。这导致具有附加信息的LR(0)自动机，因为每个LR(0)状态对应于至少一个LR(1)状态，并且每个LR(1)状态对应于某个潜在的LR(0)状态。

SLR(1)和LALR(1)解析器都具有相同的状态集，这些状态与LR(0)解析器中的状态相同。解析器的不同之处仅在于它们在每个状态下执行的操作。

在SLR(1)和LALR(1)解析器中，每一项都有一组关联的先行标记。每当解析器进入包含reduce项的状态时，如果下一个输入标记在前视集中，解析器将执行该reduce。在SLR(1)解析器中，前视集是结果左侧的非终结符的跟随集。在LALR(1)解析器中，对于产生式中的非终结符和自动机状态的组合，先行集被适当地称为LA集。

您可以证明LALR(1)解析器中使用的LA集合是SLR(1)解析器中使用的以下集合的子集。这意味着LALR(1)解析器永远不会比SLR(1)解析器有更多的reduce动作，并且在某些情况下，当SLR(1)解析器有shift/reduce冲突时，LALR(1)解析器将选择转换。

希望这能有所帮助！

Answer 2

对Q1的回答：

首先，您需要为SLR(1)和LALR(1)解析器创建DFA。我为它们创建了DFA。

DFAs SLR(1) and LALR(1) DFAs图像链接

对于SLR(1)，我得到了10个状态和10个reduce条目，而对于LALR(1)，我为CLR(1)创建了具有13个状态的DFA，这些状态被最小化为10个状态和7个reduce条目。这就回答了你的第一个问题。

对Q2的回答：

G是SLR(1)文法，那么在SLR(1)表中肯定不存在冲突(或错误) S-R或R-R。LALR(1)比SLR(1)具有更强的能力，因此对于给定的文法G，LALR(1)表中也不存在冲突

(c)：T1和T2中没有错误(错误选项)

(b)：无错误分录是指班次分录和减少分录。应该清楚地注意到，在从一个解析器到另一个解析器的自底向上的解析器中，只有reduce条目的规则改变，而shift条目的规则保持不变。例如，在LR(0)中，在每一列中进行reduce条目，对于SLR(1)，在左侧变量之后进行，而在CLR(1)和LALR(1)中，在先行符号中进行reduce条目。因此，从一个解析器到另一个解析器减少条目的变化，但是移位条目是相同的。

我们也已经在Q1中证明了SLR(1)解析表的reduce条目比LALR(1)的更多。因此证明(b)选项是不正确的。

(a) T1和T2可能是相同的，但并不总是如此。另一件重要的事情是，多项选择题有时会让你选择最合适的选项。因此，对我来说(a)是答案