LALR(1) 和 SLR(1) 解析器

Question

我从老师那里得到了一个假设，他想让我们去搜索和验证它。我们有 SLR(1) 和 LALR(1) 解析器。假设是：

Suppose we have a language structure called X. If We couldn't provide a LALR(1) grammar for this structure, we couldn't provide a SLR(1) too and maybe a LR(1) grammar could solve problem. but If we could provide a LALR(1) grammar for this structure, we could provide a SLR(1) too.

如果你在网上搜索，你会发现很多网站都说这个语法不是 SLR(1) 而是 LALR(1):

S -> R
S -> L = R
L -> * R
L -> id
R -> L

（"id"，“*”和“=”是终结符，其他是非终结符）
如果我们尝试查找 SLR(1) 项，我们将看到 shift/reduce 冲突。这是真的，但我的假设说的是另外一回事。在我们的假设中，我们谈论的是语法描述的语言而不是语法本身！我们可以去掉"R"，将文法转换为LL(1)，也就是SLR(1)和LALR(1)：

S -> LM
M -> epsilon
M -> = L
L -> * L
L -> id

您可以试试这个文法，您可以看到这个文法描述了与上一个文法相同的语言，并且有 SLR(1) 和 LALR(1) 文法！

所以我的问题不是找到 LALR(1) 而不是 SLR(1) 的语法。互联网上有很多。我想知道是否有 language 有 LALR(1) 语法但没有 SLR(1) 语法？如果我们的假设是正确的，那么就不需要 LALR(1) 和 SLR(1) 可以为我们做所有事情，但是 LALR(1) 更容易使用，也许在未来，语言拒绝这个假设。

抱歉英语不好。
谢谢

Answer 1

每种 LR(k) 语言都有一个 SLR(1) 文法。

this paper from 1976中有证明，提供了构造SLR(1)文法的算法，如果你有LR(k)文法并知道k的值。不幸的是，没有算法可以明确地告诉你一个 CFG 是否是 LR(k)，更不用说提供 k 的值了。（如果你不知何故知道语法是 LR(k)，你可以尝试 k 的连续值，直到找到一个有效的。但是如果文法不是 LR(k).)

，过程将永远不会终止

以上来自this reference question on the Computing Science StackExchange site，比较适合这类问题

Answer 2

LR(1) > LALR(1) > SLR(1)

LR(1) 最强大，LALR(1) 不那么强大，SLR(1) 最不强大。这是事实，因为前瞻集的计算方式。 (1) 表示超前一个标记。这是一个 LR(1) 的语法，但不是 LALR(1) 也绝对不是 SLR(1):

   G : S... <eof>
     ;
   S : c A1 t ';'
     | c A2 n ';'                       
     | r A2 t ';'
     | r A1 n ';'
     ;
  A1 : a 
     ;
  A2 : a 
     ;

此文法不能成为 LALR(1) 或 SLR(1)。或者确定你可以删除 A1 和 A2 和用 a 替换它们，但是你有不同的语法。问题是一个动作可以附加到规则 A1：a 并且不同的动作可以附加到 A2：a。例如：

  A1 : a    => X()
     ;
  A2 : a    => Y()
     ;

SLR(1) 解析器生成器将报告语法中的冲突，但这些冲突并非真正的冲突。我在谈论使用大型语法的现实世界（例如 C11.grm）。

SLR(1) 前瞻计算非常简单，从语法中获取前瞻，而不是由 LALR(1) 解析器生成器创建的 LR(0) 状态机。

这就是为什么 Frank DeRemer 在 1969 年关于 LALR(1) 的论文如此重要的原因。

从语法上看，A1后面可以跟t或者n，所以这是冲突的由 SLR(1) 报告，但有一个 LR(1) 状态机，其中 A1 之后没有冲突。

LALR(1) 和 SLR(1) 解析器

LALR(1) and SLR(1) parser

parsing

lookahead

context-free-grammar