LL和LR解析有什么区别？

Question

任何人都可以给我一个LL解析与LR解析的简单例子吗？

Answer 1

在高级别,LL解析和LR解析之间的区别在于LL解析器从起始符号开始并尝试应用产生来到达目标字符串,而LR解析器从目标字符串开始并尝试在开始时返回符号.

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

在LL解析期间,解析器会在两个操作之间连续选择:

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解析器中,有两个操作:

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看到属于函数的表达式，从而得到完整的源代码。