SLR(1)和LALR(1)，关于Parse表和缩减状态

Question

几天前，我问了一个问题，我和一些教授进行了大量的搜索和联系，但我不能概括地说，第二个问题的解决是正确的还是错误的。在两个不同的年份，我们有两个入学考试的问题。

两个问题是多重选择。2010年的问题是：

1)我们有一个SLR(1)语法G如下。我们使用SLR(1)解析器生成器并为G生成一个解析表S。我们使用LALR(1)解析器生成器，并为G生成一个解析表L。

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

问题设计器将解决方案选择为：

Solution: the number of elements with R (reduce) in S is more than L.

两年之后，问题设计者问：

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

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

( b) T1中的非错误条目总数低于T2。

( c) T1中的错误条目总数低于T2

解决方案：

(a) is selected by the question designer. 

我的问题是：

any one could describe for me why the solution of 1st question is contradict to 2nd question? 

有人在前一篇文章中回答说，有两种解决方案是正确的，但没有很好地描述它。

不管怎么说，我都在等一个专家帮我摆脱困惑！

Answer 1

对Q1的回答：

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

SLR(1)和LALR(1) DFAs

对于SLR(1)，我得到了10个状态和10个约简条目，而对于LALR(1)，我为CLR(1)创建了DFA，其中13个状态被最小化为10个州和7个减少项。这回答了你的第一个问题。

对Q2的回答：

G是SLR(1)文法，那么SLR(1)表中肯定没有冲突(或错误)SLR或R。LALR(1)比SLR(1)具有更大的功率，因此对于给定的语法G，LALR(1)表也没有冲突。

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

(b)：非错误条目是指移位条目和减少条目。应该清楚地指出，在从解析器到解析器的自下而上解析器中，只有减少条目更改的规则，而shift条目的规则保持不变。例如，在LR(0)中，对于SLR(1)，在LR(0)中，对SLR(1)，它是在左手边变量后面进行的，而在CLR(1)和LALR(1)中，减少条目是在前瞻性符号中进行的。因此，减少从解析器到解析器的条目更改，但是shift条目是相同的。

我们还在Q1中证明了SLR(1)解析表的约简项比LALR(1)多。因此，证明(b)选项是不正确的。

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