为什么有LR（0）解析器而不是LL（0）解析器？ [英] Why are there LR(0) parsers but not LL(0) parsers?

问题描述

我一直在维基百科上阅读，并注意到虽然LR（0）解析器存在，没有LL（0）解析器。

I've been reading on both in Wikipedia, and noticed that although LR(0) parsers exist, there's no such thing as LL(0) parser.

从我读到的，我理解LL（k）/ LR（k）中的k表示解析器可以看到超过当前正在处理的当前字符的字符数。

From what I read, I understand that the k in LL(k)/LR(k) means how many characters the parser can see beyond the current character that it's currently working on.

所以我的问题是，为什么即使LR（0）存在也没有LL（0）解析器这样的东西？

So my question is, why is there no such thing as LL(0) parser even though LR(0) exists?

推荐答案

区别在于LR（k）对LL（k）的k是什么意思。

The difference has to do with what the k means in LR(k) versus LL(k).

），解析器维护关于自上而下的从左到右的解析的信息，该解析描绘出最左侧的导出。解析器通过重复查看当前非终端符号来工作，然后检查输入流的下一k个令牌以确定应该使用哪个生产。因此，如果您有一个LL（0）解析器，解析器将不得不预测纯粹基于当前非终结符使用的生产。这是唯一可能的，如果每个非终端只有一个生产与它相关联，这意味着语法产生正好一个字符串或没有字符串（通过进入一个循环）。因此，虽然它在数学上被很好地定义，但在实践中从不使用LL（0）解析。

In LL(k), the parser maintains information about a top-down, left-to-right parse that traces out a leftmost derivation. The parser works by repeatedly looking at the current nonterminal symbol, then inspecting the next k tokens of the input stream to determine which production should be used. As a result, if you have an LL(0) parser, the parser would have to predict which production to use based purely on the current nonterminal. This is only possible if each nonterminal has just one production associated with it, which means that the grammar either produces exactly one string or no strings at all (by going into a loop). Therefore, while it is mathematically well-defined, LL(0) parsing is never used in practice.

在LR（k）中，解析器从下到上工作。它保持一个符号堆栈以及当前的状态，然后连续决定是否执行一个 shift （推栈顶部的另一个符号）或 reduce （从堆栈弹出一些符号并应用反向生产）。 LL（k）和LR（k）解析器之间的一个关键差异是LR（k）解析器如何决定要执行哪个动作。在LR（k）解析器中，基于前瞻的下一k个令牌和解析器的当前状态，决定下一步做什么。结果，LR（0）解析器仍然可以做出关于执行哪个动作的有些智能的决定，即使它看不到任何前瞻性令牌，因为解析器的当前状态可以编码关于解析器在生产中的哪里以及它可以实际期望什么的大量信息（即使解析器不能直接查看这些标记）。

In LR(k), the parser works bottom-up. It maintains a stack of symbols, along with a current "state," and then continuously decides whether to perform a shift (pushing another symbol on top of the stack) or a reduce (popping some number of symbols from the stack and applying a production in reverse). One key difference between an LL(k) and LR(k) parser is how the LR(k) parser decides which action to perform. In the LR(k) parser, the decision of what to do next s based on both the next k tokens of lookahead and on the current state of the parser. As a result, an LR(0) parser can still make somewhat intelligent decisions about which action to perform even if it can't see any lookahead tokens, because the parser's current state can encode a huge amount of information about where in a production the parser is and what it can realistically expect to see as the next tokens of input (even if the parser can't directly look at those tokens).

简而言之，LL（0）非常弱，因为解析器必须纯粹根据当前的非终端做出决定，这意味着它不能采取基于可能使用哪种生产的许多不同的行动之一。 LR（0）解析器是非常强大的，因为解析器的选择基于其内部状态，通常足够详细，让解析器做出明智的决定下一步做什么。

In short, LL(0) is extremely weak because the parser has to purely base its decision on the current nonterminal, meaning that it can't take one of many different actions based on which production might be used. An LR(0) parser is decently powerful because the parser bases its choice on its internal state, which is usually sufficiently detailed to let the parser make informed decisions about what to do next.

还有一个原因，LL（0）是弱的，而LR（0）是相当强大的。在LL（0）解析器中，解析器必须立即决定应该执行哪些生成，这意味着解析器必须完全盲目地猜测生成。在LR（0）解析器中，解析器可以在决定是时候减少之前移位多个符号。因此，没有任何前瞻的解析器可以推迟做出关于使用哪个缩减的决定，直到它已经看到足够的输入的令牌以得到对字符串的结构的感觉。这是更一般的事实的一个特殊情况，任何LL（k）语法是自动LR（k）。

There is one other reason LL(0) is weak while LR(0) is reasonably powerful. In an LL(0) parser, the parser has to immediately decide which productions ought to be performed, which means that the parser has to guess productions completely blindly. In an LR(0) parser, the parser can shift multiple symbols before deciding that it is time to reduce. Consequently, the parser, without any lookahead, can defer making its decision about which reduction to use until after it has seen enough tokens of input to get a sense for the structure of the string. This is a special case of the more general fact that any LL(k) grammar is automatically LR(k).

希望这有助于！

这篇关于为什么有LR（0）解析器而不是LL（0）解析器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！