问题描述
谁能给我一个 LL 解析与 LR 解析的简单示例?
Can anyone give me a simple example of LL parsing versus LR parsing?
推荐答案
在高层次上，LL 解析和 LR 解析的区别在于 LL 解析器从开始符号开始，并尝试应用产生式到达目标字符串，而 LR 解析器从目标字符串开始并尝试返回开始符号.
At a high level, the difference between LL parsing and LR parsing is that LL parsers begin at the start symbol and try to apply productions to arrive at the target string, whereas LR parsers begin at the target string and try to arrive back at the start symbol.
LL 解析是从左到右、最左边的推导.也就是说，我们从左到右考虑输入符号并尝试构造最左推导.这是通过从开始符号开始并重复扩展最左边的非终结符来完成的，直到我们到达目标字符串.LR 解析是从左到右的最右推导，这意味着我们从左到右扫描并尝试构造最右推导.解析器不断地选择输入的子字符串并尝试将其反转回非终结符.
An LL parse is a left-to-right, leftmost derivation. That is, we consider the input symbols from the left to the right and attempt to construct a leftmost derivation. This is done by beginning at the start symbol and repeatedly expanding out the leftmost nonterminal until we arrive at the target string. An LR parse is a left-to-right, rightmost derivation, meaning that we scan from the left to right and attempt to construct a rightmost derivation. The parser continuously picks a substring of the input and attempts to reverse it back to a nonterminal.
在 LL 解析期间，解析器不断在两个动作之间进行选择:
During an LL parse, the parser continuously chooses between two actions:
- 预测:根据最左边的非终结符和一些前瞻标记，选择应该应用哪个产生式以更接近输入字符串.
- 匹配:将最左边猜测的终端符号与最左边未使用的输入符号匹配.
- Predict: Based on the leftmost nonterminal and some number of lookahead tokens, choose which production ought to be applied to get closer to the input string.
- Match: Match the leftmost guessed terminal symbol with the leftmost unconsumed symbol of input.
举个例子，给定这个语法:
As an example, given this grammar:
- S →埃
- E →T + E
- E →T
- T →
int
然后给定字符串 int + int + int，LL(2) 解析器(它使用两个前瞻标记)将按如下方式解析字符串:
Then given the string int + int + int, an LL(2) parser (which uses two tokens of lookahead) would parse the string as follows:
Production Input Action
---------------------------------------------------------
S int + int + int Predict S -> E
E int + int + int Predict E -> T + E
T + E int + int + int Predict T -> int
int + E int + int + int Match int
+ E + int + int Match +
E int + int Predict E -> T + E
T + E int + int Predict T -> int
int + E int + int Match int
+ E + int Match +
E int Predict E -> T
T int Predict T -> int
int int Match int
Accept
请注意，在每一步中，我们都会查看生产中最左边的符号.如果是终结符，我们匹配它，如果它是非终结符，我们通过选择其中一个规则来预测它将是什么.
Notice that in each step we look at the leftmost symbol in our production. If it's a terminal, we match it, and if it's a nonterminal, we predict what it's going to be by choosing one of the rules.
在 LR 解析器中，有两个动作:
In an LR parser, there are two actions:
- Shift:将输入的下一个标记添加到缓冲区以供考虑.
- 减少:通过反转产生式，将此缓冲区中的终端和非终端集合减少到某个非终端.
- Shift: Add the next token of input to a buffer for consideration.
- Reduce: Reduce a collection of terminals and nonterminals in this buffer back to some nonterminal by reversing a production.
例如，LR(1) 解析器(带有一个前瞻标记)可能会解析相同的字符串，如下所示:
As an example, an LR(1) parser (with one token of lookahead) might parse that same string as follows:
Workspace Input Action
---------------------------------------------------------
int + int + int Shift
int + int + int Reduce T -> int
T + int + int Shift
T + int + int Shift
T + int + int Reduce T -> int
T + T + int Shift
T + T + int Shift
T + T + int Reduce T -> int
T + T + T Reduce E -> T
T + T + E Reduce E -> T + E
T + E Reduce E -> T + E
E Reduce S -> E
S Accept
您提到的两种解析算法(LL 和 LR)已知具有不同的特性.LL 解析器往往更容易手动编写，但它们不如 LR 解析器强大，并且接受的语法集比 LR 解析器小得多.LR 解析器有多种形式(LR(0)、SLR(1)、LALR(1)、LR(1)、IELR(1)、GLR(0) 等)，并且功能更强大.它们也往往更复杂，并且几乎总是由 yacc 或 bison 等工具生成.LL 解析器也有多种形式(包括 ANTLR 工具使用的 LL(*))，尽管在实践中 LL(1) 是最广泛使用的.
The two parsing algorithms you mentioned (LL and LR) are known to have different characteristics. LL parsers tend to be easier to write by hand, but they are less powerful than LR parsers and accept a much smaller set of grammars than LR parsers do. LR parsers come in many flavors (LR(0), SLR(1), LALR(1), LR(1), IELR(1), GLR(0), etc.) and are far more powerful. They also tend to have much more complex and are almost always generated by tools like yacc or bison. LL parsers also come in many flavors (including LL(*), which is used by the ANTLR tool), though in practice LL(1) is the most-widely used.
作为一个无耻的插件，如果你想了解更多关于 LL 和 LR 解析的知识，我刚刚教完编译器课程，并且有 课程网站上的一些关于解析的讲义和讲座幻灯片.如果您认为有用，我很乐意详细说明其中的任何一个.
As a shameless plug, if you'd like to learn more about LL and LR parsing, I just finished teaching a compilers course and have some handouts and lecture slides on parsing on the course website. I'd be glad to elaborate on any of them if you think it would be useful.
这篇关于LL和LR解析有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！