为什么这个文法适用于 LALR(1) 但不适用于 LR(1)

Question

从各方面来看，与 LALR(1) 相比，LR(1) 在各个方面都应该更强大，因为 LR(1) 构建了 LR(1) 项的规范集合，而 LALR(1) 只是一个更好的 SLR(1) 解析器。

那为什么当我尝试这个输入时，这个语法在 LALR(1) 解析器中成功运行，但在 LR(1) 解析器中却不行：

int + int

对于这个语法：

S' -> S
S -> Add

Add -> Mul
Add -> Add + Mul

Mul -> Const
Mul -> Mul * Mul

Const -> int
Const -> float

这些是我在此示例中使用的 JavaScript LR(1) 和 JavaScript LALR(1) 解析器： ~~http://jsmachines.sourceforge.net/machines/lr1.html~~

~~http://jsmachines.sourceforge.net/machines/lalr1.html~~

更新

JSmachine 站点错误很多。我改用南佛罗里达大学的 https://zaa.ch/jison/try/usf/index.html 这个网站，但有人建议我使用 Bison 以确保正确性。正如最上面的评论所建议的那样，Mul -> Mul * Mul 非常模棱两可，所以我相应地更新了语法

S' -> S
S -> Add

Add -> Mul
Add -> Add + Mul

Mul -> Const
Mul -> Mul * Const

Const -> int
Const -> float

适应 BNF 格式：

%%
SS : S ;
S  : Add ;

Add : Mul
    | Add '+' Mul
    ;

Mul : Const
    | Mul '*' Const
    ;

Const : int
      | float
      ;

Answer 1

我不确定你问题中的“工作”是什么意思。该在线解析器生成器报告 LR(1) 和 LALR(1) 算法的移位减少冲突，这并不奇怪，因为您的语法包含指数歧义

Mul -> Mul * Mul

显然，该站点的 LR(1) 实现在处理错误时不如其 LALR(1) 实现优雅。我会说这是一个错误。但无论如何，语法不能生成 LALR(1) 或 LR(1) 解析器。

为什么这个文法适用于 LALR(1) 但不适用于 LR(1)

Why does this Grammar work in LALR(1) but not LR(1)

parsing

lalr

lr1

lr