algorithm - LL 和 LR 解析有什么区别？

Question

谁能给我一个 LL 解析与 LR 解析的简单示例？

Answer 1

在高层次上，LL 解析和 LR 解析之间的区别在于 LL 解析器从开始符号开始并尝试应用产生式以到达目标字符串，而 LR 解析器从目标字符串开始并尝试返回在开始符号处。

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

在 LL 解析期间，解析器不断地在两个 Action 之间进行选择:

1. 预测:基于最左边的非终结符和一定数量的前瞻标记，选择应该应用哪个产生式以更接近输入字符串。
2. 匹配:将最左边猜到的终结符号与最左边未使用的输入符号匹配。

举个例子，给定这个语法:

• S → 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 解析器中，有两个 Action :

1. Shift:将下一个输入标记添加到缓冲区以供考虑。
2. Reduce:通过反转产生式将此缓冲区中的终结符和非终结符集合缩减回某些非终结符。

例如，LR(1) 解析器(带有一个先行标记)可能会按如下方式解析相同的字符串:

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 解析器也有多种形式(包括 LL(*)，它被 ANTLR 工具使用)，但实际上 LL(1) 是使用最广泛的。

作为一个无耻的插件，如果你想了解更多关于 LL 和 LR 解析的知识，我刚刚完成了编译器类(class)的教学并且有 some handouts and lecture slides on parsing在类(class)网站上。如果您认为有用，我很乐意详细说明其中的任何一个。