LL和LR解析之间的区别是什么?

谁能给我一个LL解析和LR解析的简单例子?

88772 次浏览
小开

在较高的级别上，LL解析和LR解析之间的区别在于LL解析器从开始符号开始，并尝试应用结果来到达目标字符串，而LR解析器从目标字符串开始，并尝试返回开始符号。

LL解析是一个从左到右、最左的推导。也就是说，我们从左到右考虑输入符号，并试图构造最左边的推导。这是从开始符号开始，反复展开最左边的非终结符，直到到达目标字符串。LR解析是一个从左到右、最右的推导，这意味着我们从左到右扫描，并试图构造最右的推导。解析器不断地选择输入的子字符串，并尝试将其反转回非终结符。

在LL解析过程中，解析器会连续在两个操作之间进行选择:

  1. 预测:根据最左边的非终结符和一些前置令牌的数量，选择应该应用哪个结果以更接近输入字符串。
  2. 匹配:将最左边的猜到的终端符号与最左边的未使用的输入符号匹配。

举个例子，给定下面的语法:

  • 年代→E
  • E →T + e
  • E →T
  • T →int

然后给定字符串int + int + int, LL(2)解析器(使用两个超前标记)将解析字符串，如下所示:

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

请注意，在每一步中，我们都要查看产品中最左边的符号。如果它是终结符，我们就匹配它，如果它是非终结符，我们通过选择一个规则来预测它会是什么。

在LR解析器中，有两个动作:

  1. 转变:将下一个输入标记添加到缓冲区中以供考虑。
  2. 减少:通过反转结果，将该缓冲区中的终结符和非终结符集合还原为某个非终结符。

例如，LR(1)解析器(带有一个lookahead标记)可能会解析相同的字符串，如下所示:

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)是使用最广泛的。

作为一个无耻的插件，如果你想了解更多关于LL和LR解析的知识，我刚刚教完一门编译器课程，并在课程网站上有一些关于解析的讲义和幻灯片。如果你认为有用的话，我很乐意详细说明其中的任何一个。

小开

Josh Haberman在他的文章LL和LR解析去神秘化中声称LL解析直接对应于波兰表示法，而LR对应于波兰语反向表示法。PN和RPN的区别在于遍历方程二叉树的顺序:

一个方程的二叉树

+ 1 * 2 3  // Polish (prefix) expression; pre-order traversal.
1 2 3 * +  // Reverse Polish (postfix) expression; post-order traversal.

根据Haberman的说法，这说明了LL和LR解析器之间的主要区别:

LL和LR解析器操作方式的主要区别在于LL解析器输出解析树的前序遍历，LR解析器输出后序遍历。

对于深入的解释，示例和结论检查Haberman的文章。

小开

LL使用自顶向下的方法，而LR使用自底向上的方法。

如果你解析一种编程语言:

  • LL看到一个源代码，其中包含函数，其中包含表达式。
  • LR看到表达式，它属于函数，结果是完整的源。
小开

与LR相比，LL解析是不利的。这里有一个语法 这对于LL解析器生成器来说是一个噩梦:

Goal           -> (FunctionDef | FunctionDecl)* <eof>


FunctionDef    -> TypeSpec FuncName '(' [Arg/','+] ')' '{' '}'


FunctionDecl   -> TypeSpec FuncName '(' [Arg/','+] ')' ';'


TypeSpec       -> int
-> char '*' '*'
-> long
-> short


FuncName       -> IDENTIFIER


Arg            -> TypeSpec ArgName


ArgName        -> IDENTIFIER
一个FunctionDef看起来完全像一个FunctionDecl，直到';'或'{' 遇到。< / p > LL解析器不能同时处理两条规则，所以它必须这样做 选择FunctionDef或FunctionDecl。但要知道哪个才是 正确，它必须提前查找';'或'{'。在语法分析时，前瞻(k)似乎是无限大的。在解析时，它是有限的，但是 可能很大。< / p > LR解析器不需要向前看，因为它可以处理两个 同时还要遵守规则。因此LALR(1)解析器生成器可以处理这种语法 轻松。< / p >

给定输入代码:

int main (int na, char** arg);


int main (int na, char** arg)
{


}

LR解析器可以解析

int main (int na, char** arg)

不关心识别的是什么规则，直到它遇到';'或'{'。

LL解析器被挂在'int'上，因为它需要知道是哪个 规则正在被认可。因此，它必须在前面寻找一个';'或 “{”。< / p > LL解析器的另一个噩梦是语法中的左递归。左递归在语法中很正常，对于LR来说没有问题 解析器生成器，但是LL不能处理它。< / p >

所以你必须用不自然的方式写你的语法。


提交答案