20130723

解密:LL与LR解析 1

解密:LL与LR解析

作者:Josh Haberman翻译:杨贵福

由于GFW,我无法联系到作者,所以没有授权,瞎翻译的。原文在这里[http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html]。

2013年7月22日

我最初解析理论的经历来自大学时自学程序设计语言的时候。当我学到像LL,LR还有它们的变型 (比如Strong-LL, SLR, LALR等等)的时候,我迷惑了。我觉得正注视着的是艰深而强大的咒语,它的重要意义我尚不能领会,但是我确信,总有一天,像"从左至右导出""最右导出"这些术语会融汇贯通,于是我继续努力期待明白的一天。


现在我可以说,经过10年的时间再加上看了一整架解析类的书以后,我把这些算法理解得不错了。但是我看待它们的角度和我看过的文献都非常不同。我更多地从实现的角度,而不是数学的角度,数学的角度也起了一些作用 (杨注:瞎翻译的)。无论如何,我想解释一下我是如何看待这些算法的,希望有人也像我一样觉得这个角度更直观。

这篇文章只涉及到把解析器视为黑盒子这一角度:即解析器的输入/输出,及解析器的限制。后续的文章将打开黑盒子,把这些算法内部工作的更多的细节展示出来。

1. 解析 与 波兰表式法

如果你在大学学习计算机科学,或者甚至你要是有个惠普的计算器 (杨注:我从来没见过逆波兰的HP计算器,而且,空格在那上面如何表示啊?) ,你就见过波兰和逆波兰表示法。它们能不用符号,也不用四则运算顺序规则,就能写出数学运算表达式。我们习惯于把表达式写作中缀形式,在这种形式下,操作符置于操作数二者之间:

1 + 2 * 3

在这种形式下,你如何知道计算的优先级呢?你不得不按约定的规则 (四则混合运算的法则)。你如何想按不同的次邓,就必须用括号了,像这样:

1 (1 + 2) * 3

在波兰和逆波兰表示法中,你不必关心四则运算的优先级,也不必加括号,同样可以避免二义性。这是通过把操作符放在操作数之前(波兰表示法)或之后 (逆波兰表示法)实现的。它们也分别被称为前缀和后缀表示法。

// 第一个例子: 1 + 2 * 3 // 中缀+ 1 * 2 3 // 波兰表示法 (前缀) 1 2 3 * + // 逆波兰表示法 (后缀)
 
// 第二个例子: (1 + 2) * 3 // 中缀* + 1 2 3 // 波兰表示法 (前缀) 1 2 + 3 * // 逆波兰表示法 (后缀)


除了不需要括号,也不需要运算次序的约定以外,波兰和逆波兰表示法在写运算器 (求值)的时候也容易很多 (也许HP计算器的设计师用逆波兰表示法,就是为了能去巴哈马群岛度一周假) 。下面是一个Python实现的逆波兰的简单求值器。

1 # 函数定义了操作符,及如何依据操作符求值
2 # 本例假设操作符都是二值的,不过容易扩展为多值。
3 ops = {
4   "+": (lambda a, b: a + b),
5   "-": (lambda a, b: a - b)
6 }
7  
8 def eval(tokens):
9   stack = []
10  
11   for token in tokens:
12     if token in ops:
13       arg2 = stack.pop()
14       arg1 = stack.pop()
15       result = ops[token](arg1, arg2)
16       stack.append(result)
17     else:
18       stack.append(int(token))
19  
20   return stack.pop()
21  
22 print "Result:",  eval("7 2 3 + -".split())

波兰和逆波兰表示法,确实如通常所说的,需要事先知道所有操作符的参数数量。这里的参数数量,指的是操作符所作用的操作数的数量。这意味着,单值操作符负号和二值操作符减法,是两个不同的操作符。否则,我们在遇到操作符的时候,就不知道从栈中弹出多少个操作数。

一种避免了这个问题的类似表达方法,是Lisp语言的s-表达式。s-表达式 (还有类似的编码形式,比如XML)避免了固定操作符参数个数的需要,实现这一效果的方法是明确标记每个表达式的开始和结束之处。

1 ; Lisp风格的前缀表达式;
2 ; 同一个操作符可以有不同的参数数量
3 (+ 1 2)
4 (+ 1 2 3 4 5)
5
6 ; 我们前两个例子在Lisp中的等价表达方式
7 ; 前缀: + 1 * 2 3
8 (+ 1 (* 2 3))
9
10 ; 前缀: * + 1 2 3
11 (* (+ 1 2) 3)

Lisp这一表达法有不同于前述方法的妥协 (前面的方法中要使用固定数量的参数,Lisp需要括号),但是它们底层的解析/处理算法是非常类似的,因此通常我们把它们视为略有不同的前缀表达式。

看起来我好像有点跑题了,不过,其实我一直在偷偷地讨论LL和LR。按我的观点,LL和LR解析正分别与波兰和逆波兰表示法直接相关。不过为了完整地探索这个想法,我们需要先描述一下我们需要解析器输出什么。

作为一个有趣的练习,请尝试实现一个算法,用于把波兰表达式转化为逆波兰表达式。看看你是否可以不需要先把整个表式式转化为为一棵树;你可以只用一个栈实现这个效果。现在,比如你又要实现相反的过程 (从逆波兰到波兰)--你只需在输入上运行同一个算法,这回转换的方向就相反了。当然,你也可以构造一棵中间的树,但是这导致 O(输入长度) 的空间,而单使用一个栈的解决方案只需要 O(树的深度) 的空间。如何从中缀到后缀呢?有一个非常聪明和高效的算法,称为 调度场算法[http://en.wikipedia.org/wiki/Shunting-yard_algorithm]。

2. 解析器及输出

我们一致认可解析器的输入是token的一个流 (这个流极可能来自一个词法分析器,不过我们可以以后再讨论这一部分)。不过解析器的输出是什么?你可能倾向于说"一棵解析树"。当然你可以用解析器构造出一棵解析树,不过也可能不是这样,而是一种完全不构造解析树的输出。比如,这个Bison的例子[http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html#Infix-Calc] ,在解析的同时求值了算术表达式。每次当子表达式被识别出来,它立即被求值,直到最终的结果是一个单独的数。从来没有解析树显式地构造出来。

因此,说解析器的输出是一棵解析树不具有足够的一般性。相反地,我断言:解析器的输出,至少我们今天讨论的LL和LR的输出,是解析树的 *遍历*。


如果触动了哪位真理洁癖的神经,我在此道歉。我可以听到有人抗议道,树的遍历是一种算法,是你施加于一棵树上的操作。我怎么能说解析器输出了一棵树的遍历呢?答案在于,请回想一下刚才的波兰和逆波兰表式法。它们通常只是一种数学算式的表示法,不过我们也可以更一般性地把它们视为 对树的遍历的扁平和线性的 (序列化的)编码方式。


回想 下我们的第一个例子 1 + 2 * 3。下面是这个表达式的树形的写法:

    +
   / \
  1   *
     / \
    2   3



有三种方法遍历这个二叉树,如在维基百科上所给出的:中序遍历 (in-order) ,先序遍历 (pre-order) ,后序遍历 (post-order)。它们的不同只在于你访问父节点的时机,是在访问子节点之前 (先序),之后 (后序),或者左右子树之间(中序)。这三者正与中缀、波兰、逆波兰表示法对应。

1 + 2 * 3 // 中缀表达式,中序遍历+ 1 * 2 3 // 波兰 (前缀)表达式,先序遍历1 2 3 * + // 逆波兰 (后缀)表达式,后序遍历

所以,波兰和逆波兰表示法 完全地编码了一棵树结构,并且规定了你遍历它的步骤。在这些编码方法与一棵实际的解析树之间的主要区别,在于 波兰和逆波兰表示法 编码的访问并非随机的。对于一棵真实的树 (杨注:计算机里的真实,不是现实的真实,哈哈,所谓真实),你可以跟随一个内部节点到它的右子树,或者它的左子树,或者甚至 (对于许多树而言)它的父节点。在这些线性的编码方案中,就没有这种灵活性:你只能采用它已经这样编码了的那种遍历方法。

但是,好的一方面是,它使用解析树的输出是一个流,这个流是在解析行为发生的时候产生的。这也是Bison的那个例子,它如何在没有实现构造一棵树的情况下,就能够求值算术表达式。如果真的需要一棵不是扁平编码的树的话,从线性的树遍历中很容易就能构造出一棵来。不过,当不需要这棵真的树的话,构造它的代价就完全可以避免。

这就引出了关键点:

LL和LR解析器操作之主要不同在于,LL解析器输出解析树的先序遍历,而LR解析器输出后序遍历。

这等价于那些更传统,但是 (按我的观点)更易令人迷惑和不那么直观的关于区别的解释:

* "LL解析器产生一个最左导出,而LR解析器产生一个逆转最右导出。"

* "LL解析器自顶向下把树构造出来,而LR解析器自底向上构造。"

* LL解析器通常称为"带预测的解析器"(杨注:原文predictive parsers,这是不是有约定的翻译啊),而LR解析器称为归约解析器 (杨注:原文shift-reduce )。

今天先翻译到这里,原文后面还有。

No comments: