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

问题描述

什么是LR，SLR和LALR解析器之间的实际差异？我知道，单反相机和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，单反相机，或LALR？对于LL文法，我们只是要表明，分析表中的任意单元格不应包含多个生产规则。任何类似的规则LALR，单反相机，和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），但不反光（1）？

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

修改（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语法中类似的状态，产生的解析器状态表是完全一样的大小相当于单反相机的语法，这是数量级通常是为了比单纯的LR分析表小。然而，对于LR语法过于复杂是LALR，这些合并后的状态造成解析器冲突，或产生不充分认识到原来的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.

顺便说一句，我提到这个几件事情在我的MLR（K）分析表算法这里。

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

附录

简短的回答是，LALR分析表都较小，但是解析器机制是相同的。一个给定的LALR语法会产生更大的分析表，如果所有的LR状态的产生，有很多冗余的（近乎相同）的状态。

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表是较小的，因为类似的（冗余）的状态合并到一起，有效地扔掉背景/超前信息的独立的国家恩code。其优点是，你得到了相同的语法小得多分析表。

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文法可以连接codeD作为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屋！