LR，SLR和LALR解析器之间有什么区别？ [英] What is the difference between LR, SLR, and LALR parsers?

问题描述

LR，SLR和LALR解析器之间的实际区别是什么？我知道SLR和LALR是LR解析器的类型，但对于它们的解析表，它们的实际差别是什么？

What is the actual difference between LR, SLR, and LALR parsers? I know that SLR and LALR are types of LR parsers, but what is the actual difference as far as their parsing tables are concerned?

如何显示语法是否LR，SLR或LALR？对于LL语法，我们只需要显示解析表的任何单元格都不应该包含多个生产规则。 LALR，SLR和LR的任何类似规则？

And how to show whether a grammar is LR, SLR, or LALR? For an LL grammar we just have to show that any cell of the parsing table should not contain multiple production rules. Any similar rules for LALR, SLR, and LR?

例如，我们如何显示语法

For example, how can we show that the grammar

S --> Aa | bAc | dc | bda
A --> d

是LALR（1），但不是SLR（1）？

is LALR(1) but not SLR(1)?

EDIT（ybungalobill）：我没有得到满意的答案，LALR和LR之间的区别。因此，LALR的表的大小较小，但它只能识别LR语法的一个子集。有人可以详细说明LALR和LR之间的区别吗？ LALR（1）和LR（1）将足以得到答案。两者都使用1个令牌先行和都是表驱动！它们是如何不同的？

EDIT (ybungalobill): I didn't get a satisfactory answer for what's the difference between LALR and LR. So LALR's tables are smaller in size but it can recognize only a subset of LR grammars. Can someone elaborate more on the difference between LALR and LR please? LALR(1) and LR(1) will be sufficient for an answer. Both of them use 1 token look-ahead and both are table driven! How they are different?

推荐答案

LALR解析器在LR语法中合并类似的状态以产生完全相同大小的解析器状态表作为等效的SLR语法，其通常比纯LR解析表小一个数量级。然而，对于太复杂而不是LALR的LR语法，这些合并状态导致解析器冲突，或产生不能完全识别原始LR语法的解析器。

LALR parsers merge similar states within an LR grammar to produce parser state tables that are exactly the same size as the equivalent SLR grammar, which are usually an order of magnitude smaller than pure LR parsing tables. However, for LR grammars that are too complex to be LALR, these merged states result in parser conflicts, or produce a parser that does not fully recognize the original LR grammar.

BTW，我在我的MLR（k）解析表算法这里中提到了一些事情。

BTW, I mention a few things about this in my MLR(k) parsing table algorithm here.

附录

简短的答案是LALR解析表较小，是一样的。如果生成所有LR状态，并且有很多冗余（接近相同）状态，则给定的LALR语法将产生大得多的解析表。

The short answer is that the LALR parsing tables are smaller, but the parser machinery is the same. A given LALR grammar will produce much larger parsing tables if all of the LR states are generated, with a lot of redundant (near-identical) states.

LALR表更小，因为相似（冗余）状态被合并在一起，有效地丢弃了单独状态编码的上下文/前瞻信息。其优点是，对于同一个语法，你可以得到更小的解析表。

The LALR tables are smaller because the similar (redundant) states are merged together, effectively throwing away context/lookahead info that the separate states encode. The advantage is that you get much smaller parsing tables for the same grammar.

缺点是不是所有的LR语法都可以编码为LALR表，因为更复杂的语法有更多复杂的前瞻，导致两个或多个状态而不是单个合并状态。

The drawback is that not all LR grammars can be encoded as LALR tables because more complex grammars have more complicated lookaheads, resulting in two or more states instead of a single merged state.

主要的区别是生成LR表的算法在转换之间携带更多的信息状态到状态，而LALR算法不。因此，LALR算法不能判断给定的合并状态是否应该被确定为两个或更多个单独的状态。

The main difference is that the algorithm to produce LR tables carries more info around between the transitions from state to state while the LALR algorithm does not. So the LALR algorithm cannot tell if a given merged state should really be left as two or more separate states.

这篇关于LR，SLR和LALR解析器之间有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！