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

Question

我从我们的老师那里得到了一个假设，他希望我们去寻找并验证它。我们有SLR(1)和LALR(1)解析器。假设是：

假设我们有一个名为X的语言结构，如果我们不能为这个结构提供一个LALR(1)语法，我们也不能提供一个SLR(1)，也许LR(1)语法可以解决问题。但是如果我们能为这个结构提供一个LALR(1)文法，我们也可以提供一个SLR(1)。

如果你在互联网上搜索，你会发现很多网站说这种语法不是SLR(1)，而是LALR(1)：

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

("id“、"*”和"=“是终端，其他为非终端)

如果我们试图找到单反(1)项目，我们将看到移位/减少冲突。这是真的，但我的假设说了些别的话。在我们的假设中，我们讨论的是由语法而不是语法本身描述的语言！我们可以删除"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)。在网上有很多这样的人。我想知道是否有语言有LALR(1)语法，但没有SLR(1)语法？如果我们的假设是正确的，那么就不需要LALR(1)和SLR(1)可以为我们做任何事情，但是LALR(1)更容易使用，而且将来可能会被语言拒绝。

英语不好我很抱歉。

谢谢。

Answer 1

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

在本文来源于1976年。中有一个证明，它提供了一个构造SLR(1)语法的算法，如果您有一个LR(k)文法，并且知道k的值。不幸的是，没有任何算法可以确切地告诉您CFG是否是LR( k )，更不用说提供k的值了。(如果您知道语法是LR(k)，则可以尝试连续的k值，直到找到起作用的值为止。但如果语法不是LR(K)，则该过程永远不会终止。

上面的内容来自于这个参考问题 on 计算科学StackExchange站点，这是一个更好的解决这类问题的地方。

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)状态机。

这就是为什么弗兰克·德雷默1969年发表的关于LALR(1)的论文如此重要的原因。

通过查看语法，A1后面可以是t或n，因此这是SLR(1)报告的冲突，但是有一个LR(1)状态机，其中没有A1后面的冲突。