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

Question

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

Answer 1

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

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

在 LL 解析期间，解析器不断在两个动作之间进行选择：

1. 预测：根据最左边的非终结符和一些前瞻标记，选择应该应用哪个产生式以更接近输入字符串。
2. Match：将最左边的猜测终端符号与最左边未使用的输入符号匹配。

例如，给定以下语法：

• S → E
• E → T + E
• E → T
• →int

然后给定 string 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. Shift：将下一个输入标记添加到缓冲区以供考虑。
2. 减少：通过反转生产，将此缓冲区中的终端和非终端集合减少回某个非终端。

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

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

Answer 2

Josh Haberman 在他的文章LL 和 LR Parsing Demystified中声称 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 的文章。

Answer 3

与 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 完全一样，直到 ';' 或遇到“{”。

LL 解析器不能同时处理两个规则，因此它必须选择 FunctionDef 或 FunctionDecl。但是要知道哪个是正确的，它必须向前看一个';' 或者 '{'。在语法分析时，前瞻 (k) 似乎是无限的。在解析时它是有限的，但可能很大。

LR 解析器不必超前，因为它可以同时处理两个规则。所以 LALR(1) 解析器生成器可以轻松处理这种语法。

给定输入代码：

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

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

}

LR 解析器可以解析

int main (int na, char** arg)

不关心什么规则被识别，直到它遇到一个';' 或“{”。

LL 解析器在“int”处挂断，因为它需要知道正在识别哪个规则。因此它必须向前看一个';' 或者 '{'。

LL 解析器的另一个噩梦是语法中的左递归。左递归在语法中是很正常的事情，LR解析器生成器没有问题，但LL无法处理。

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

Answer 4

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

如果您解析编程语言：

• LL 看到一个源代码，其中包含函数，其中包含表达式。
• LR 看到属于函数的表达式，从而得到完整的源代码。