门|门CS 2013 |问题65

考虑下面两组LR（1）项的LR（1）文法。

X -> c.X, c/d
   X -> .cX, c/d
   X -> .d, c/d
   X -> c.X, $
   X -> .cX, $
   X -> .d, $

以下与在相应的LALR解析器中合并两个集合有关的语句中，哪一个是/是错误的？

1. 无法合并，因为look aheads不同。
2. 可以合并，但会导致S-R冲突。
3. 可以合并，但会导致R-R冲突。
4. 无法合并，因为c上的goto将导致两个不同的集合。

（A） 1只 （B） 2只 （C） 仅限1和4 （D） 1、2、3和4 答复: （D） 说明： 给定的两套LR（1）项目为：

X -> c.X, c/d
X -> .cX, c/d
X -> .d, c/d
and
X -> c.X, $
X -> .cX, $
X -> .d, $ 

逗号后的符号/端子是先行符号。

这些是LR（1）（LR（1）也称为CLR（1））项的集合。

LALR（1）解析器组合了那些LR（1）项集合，这些LR（1）项在第一个组件上相同，但在第二个组件上不同。

在LR（1）项目集（a->B，c）的生产规则中，a->B是第一个组件，而前瞻性符号集（此处为c）是第二个组件。

现在我们可以看到，在给定的集合中，相应产生式规则的第一个分量在两个集合中是相同的，它们只在第二个分量（即它们的前瞻符号）上不同，因此我们可以将这些集合组合成一个集合，这将是：

X -> c.X, c/d/$
X -> .cX, c/d/$
X -> .d, c/d/$

这样做是为了减少解析器状态的总数。

现在我们可以检查给出的陈述。

声明1：声明是错误的，因为合并已经完成，因为第二个组件，即展望是不同的。

声明2：在合并的集合中，我们看不到任何Shift-Reduce冲突（因为甚至不可能进行缩减，当存在形式P->q.的产品时，也可以进行缩减）

声明3：在合并的集合中，我们看不到任何Reduce-Reduce冲突（与上面的原因相同，甚至不可能进行Reduce，所以没有发生R-R冲突的机会）

语句4：这个语句也是错误的，因为goto是在非终端符号上进行的，而不是在终端符号上，c是终端符号。

因此，所有的陈述都是错误的，因此选择D。

这个问题的小测验