0

几天前我问了一个问题 SLR(1) 和 LALR(1) 和 Reduce，我做了很多搜索并联系了一些教授，但我无法总结第二个问题的解决方案是对还是错。我们有 2 个不同年份的入学考试题。

两题是选择题。在 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?

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

无论如何，我在等待一位专家让我摆脱困惑！

4

1 回答 1

1

回答 Q1：

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

SLR(1) 和 LALR(1) DFA

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

回答 Q2：

G 是 SLR(1) 语法，那么 SL​​R(1) 表中肯定没有冲突（或错误）SR 或 RR。LALR(1) 比 SLR(1) 更强大，因此对于给定的语法 G，LALR(1) 表中也没有冲突。让我们逐个查看选项

(c) : T1 和 T2 没有错误（错误选项）

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

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

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

于 2015-01-18T15:30:42.870 回答