对于某些语法，LR(1) 解析 table 大小是否与 LALR(1) 解析 table 相同？

Question

我知道 LALR(1) 文法是 LR(1) 文法的一个子集，大多数时候 LALR(1) 解析 table 比 LLR(1) 解析 table 对于相同的语法。但是我无法在 Internet 上找到答案，因此是否存在它们具有相同解析 table 大小的语法。这听起来是可能的，因为 LALR 本质上是 "collapsing" 兼容状态，合并那些不冲突的状态，但是 LR(1) 和 LALR(1) 是否存在具有相同解析 table 大小的语法？

Answer 1

我在这里找到了答案（和实际示例）：https://www.youtube.com/watch?v=Nxj0g1mk5Ak&list=PLEbnTDJUr_IcPtUXFy2b1sGRPsLFMghhS&index=15。 LR和LALR 可以不仅有相同大小的table，它们还可以有完全相同的table.

Answer 2

直观地，LALR(1) 解析器是通过从 LR(1) 解析器开始并在这些状态除了前瞻之外相同时重复合并在一起而形成的。因此，只要没有任何此类状态要合并在一起，语法的 LR(1) 和 LALR(1) 解析器将是相同的。

在那种情况下，两个解析器的解析表将完全相同。 GOTO 表将是相同的，因为两个解析器具有相同的状态和相同的转换，而 ACTION 表将是相同的，因为每个状态中的 shift 和 reduce 项是相同的。

我认为 LALR(1) 和 LR(1) 自动机必须保持相同的特定要求是文法的 LR(0) 和 LR(1) 解析器必须相同另一个，忽略前瞻。具体来说：

如果 LR(0) 和 LR(1) 解析器是相同的忽略前瞻，则在 LR(1) 解析器中没有状态可以组合在一起，因此 LR(1) 解析器与LALR(1) 解析器。
如果 LALR(1) 解析器和 LR(1) 解析器相同，则 LR(1) 解析器中的任何状态都不会组合在一起。由于语法的 LALR(1) 解析器中的状态数始终与 LR(0) 状态数相同，这意味着 LR(1) 和 LR(0) 解析器具有相同的状态数。这意味着它们唯一不同的地方就是前瞻。

所以换句话说，是的，这是可能的。更准确地说：

Theorem: A grammar G has identical LALR(1) and LR(1) parsers if and only if it has identical LR(0) and LR(1) parsers, ignoring lookaheads.

这意味着任何具有此属性的文法都必须是 LR(0)，在这种情况下您不想使用 LALR(1) 解析器。然而，并不是所有的 LR(0) 文法都有这个属性。例如，考虑这个语法：

S -> aTbT
T -> c

这是 LR(1) 解析器：

(1)
S' -> .S    [$]
S  -> .aTbT [$]

(2)
S  -> a.TbT [$]
T  -> .c    [b]

(3)
T ->  c.    [b]

(4)
S -> aT.bT  [$]

(5)
S -> aTb.T  [$]
T -> .c     [$]

(6)
T ->  c.    [$]

(7)
S -> aTbT.  [$]

(8)
S' -> S     [$]

此处，状态 (3) 和 (6) 将在 LALR(1) 解析器中组合在一起，因此 LR(1) 和 LALR(1) 解析器不相同。但是，你可以检查这个语法确实是 LR(0)，表明只有 LR(0) 语法的一个子集有这个属性.

对于某些语法，LR(1) 解析 table 大小是否与 LALR(1) 解析 table 相同？

Can LR(1) parsing table size be the same as LALR(1) parsing table for some grammar?

parsing

compilation

compiler-construction

lr

lalr