LL和LR分析之间的区别是什么？ [英] What is the difference between LL and LR parsing?

问题描述

谁能给我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:

1. predict ：基于最左边的非终结符和前瞻令牌一定数量，选择哪些产品应该被应用到更接近输入字符串
2. 匹配：匹配最左边的猜测终端符号的输入的最左边的未使用符号

1. 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.
2. Match: Match the leftmost guessed terminal symbol with the leftmost unconsumed symbol of input.

作为一个例子，考虑到本语法：

As an example, given this grammar:

• 在S＆RARR; Ë
• E＆RARR; T +Ë
• E＆RARR;牛逼
• T＆RARR; INT

• S → E
• 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

请注意，在每个步骤中，我们来看看在我们的生产中最左边的象征。如果它是一个终端，我们匹配它，如果它是一个非终结，我们predict它的将是选择的规则之一。

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:

1. 移：输入的下一个标记添加到缓冲审议
2. 减少：在此缓冲区，减少终端和终结符号的集合找回一些非终结被扭转了生产

1. Shift: Add the next token of input to a buffer for consideration.
2. 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 或野牛。 LL语法分析器也有许多种（包括LL（*），这是由该 ANTLR 工具），但在实践中的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分析之间的区别是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！