20130723

解密:LL与LR解析 2(译,完结)

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

这是第2部分和完结。

3. 解析树的形状


到目前为止,我们使用的算术表达式的那棵树,仍然不是解析树,因为它并未与语法关联。要考查一棵真正的解析树,我们需要语法。不幸的是,为中缀算术表达式写语法不像你期待的那么简单和优雅。对优先级和结合性 (杨注:操作符左结合还是右结合)编码,保证语法没有二义性 (并受LL和LR支持) ,是非常丑陋和不符合直觉的。这也是为什么LL和LR解析器也允许你做指定操作符优先级这样的扩展;比如,参见Bison优先级的相关特性[http://www.gnu.org/software/bison/manual/html_node/Precedence.html#Precedence]。而这篇文章的目的是打算讨论纯的LL和LR。

因此,我们得把那个算术表达式的例子调整为比较容易写的语法的形式。我们将使用JSON (杨注:JSON是javascript的对象表示方法) ,既然它非常简单,而又足够复杂和有趣。

1 object → '{' pairs '}'
2  
3 pairs → pair pairs_tail | ε
4 pair → STRING ':' value
5 pairs_tail → ',' pairs | ε
6  
7 value → STRING | NUMBER | 'true' | 'false' | 'null' | object | array
8 array → '[' elements ']'
9  
10 elements → value elements_tail | ε
11 elements_tail → ',' elements | ε


上面,我用了单引号括起的字符串表示 原文文字标记 (literal tokens),用大写字母,比如STRING,表示那些拼写不确定的tokens (比如,"abc"和""都是有效的STRING tokens)。所有的名字小写字母的,都是语法规则 (也称 非叶节点)。

你可能奇怪,为什么我要用 pairs_tail 和 elements_tail,而不用重复构造 (repetition construct) ,像很多解析器比如ANTLR支持的那样。这样,我们就可以这样写:

elements → value (',' value)*

使用*的这种语法,用起来更方便,语法也更简单,但是同时,它导致解析树概念上更复杂了一点,因为某个给定的语法规则的子树个数不再是确定不变的。并且,LR解析器不支持重复操作符(比如,Bison就不支持),这样,我上面写的语法就既可以用于LL也可以用于LR解析器。因此,我们现在要使用这个有点复杂的语法。

现在,我们有语法了,那么我们来看一个token的流的例子,再来看输出的解析树。

{"message":"Hello, World!"}

上述这段文字的token流是:

{ STRING : STRING }

而它的解析树,按我们的语法,就是:



注意,所有的叶结点 (绿色的)都是tokens,它们的顺序与我们的解析器的输入顺序是完全一致的。 (我做了一点小弊,把ε作为叶结点了,不过正如我们所看到的,这看起来更干净更规则一些)

我前面曾经断言过,LL解析器输出的是先序遍历,而LR解析器输出的是后序遍历。从这一点出发,我们可以知道LL和LR解析器对上述输入分别会给出什么输出:



既然叶节点总是输入的tokens本身,且完全按输入的顺序,所以所有的解析器真正所做的,就是把中间节点 (杨注:语法规则)插入到合适的位置。看这一点的另一个角度就是,一棵解析树,就是一堆结构体,这堆结构体定义在输入的tokens的序列之上。我们稍微重新安排一下之前的这个图示,这一点看起来就更清楚了。
 



我们正集中讨论一个非常简单的模型,用这个模型描述LL和LR解析器如何工作。LL和LR解析器二者都读入一个输入tokens的流,再把相同的流作为输出,并且把规则 (杨注:中间节点)插入到适当的位置,以形成解析树的先序 (LL)或后序 (LR)遍历。




这样,按波兰和逆波兰表示法考虑,这种对解析器输出的认识又带给我们一个好处。它使得我们可以对解析器的输入和输出都按简单的、平坦的流建模。这比把解析器的中间输出状态视为部分地构造树要容易多了,那种思路对于理解输出和对输出的检验都没什么帮助。

4. 超前 (Lookahead)

LL和LR解析器都是"在线的",意味着它们都能在输入正在进行时开始产生输出.  但是在许多情况下,在流的位置之前的tokens没有包含足够的信息,因此解析无法知道是否需要插入规则 (或者,如果需要插入规则,应该插入哪一条).因此,解析器得超前 (lookahead)到流的后面,看看下面的一些tokens是什么,以便做出决定。当你看到像LL(1)或者LR (0)这样的命令的时候,括号里的数字就是要超前的tokens的数量。

值得注意的是,超前是相对于规则将要插入的位置而言的,这个位置 (正如你记得的)对于LL解析器而言是在规则的tokens之前,而在LR解析器的规则tokens之后。这意味着,LL超前从规则的tokens的开头开始计数,LR从末尾开始计数。这带给LR解析器一个巨大的益处,因为在它们做出决定之前,他们能够看到规则的所有tokens (可能再超前一些),而LL解析器只能看到规则最初的几个tokens。



这就是为什么会有LR(0)解析器这种东西,而LL(0)解析器是不可能存在的;那样就根本不会有信息用来帮助决定接下来的tokens应该使用哪条规则。


5. 结果

根据上述对于LL和LR解析的比较的理解,我们能够得到几条重要的结论,有助于理解为什么有些当然的事是那样的。

(1) LR解析器能够处理更多的语法

这一点可由上一节超前 (lookahead)推得。既然LR超前开始于规则的末尾,在做决定的时候,LR(1)就确定地比LL(1)拥有更多的信息。进而,LR(1) 解析器确定地能比LL(1)解析器多解析一些语法 (杨注:原文接下来在括号里是modulo LL-only grammar extensions; see below。我不知道什么意思)。LR解析器可以处理左递归,LL解析器不能。

优势:LR

(2) (杨注:EBNF这一类的)

另一方面,既然LL解析器在开始解析规则的tokens之前就选定了使用哪条规则,并且无论LL解析器什么时候解析一个token的时候,它一定知道其token的上下文。这是一个更困难的任务 (既然它们拥有的能够继续的信息更少),这导致了一些重要的优势。

LL解析器在语法中能支持 像正则表达式 一样的操作符。

知道解析的上下文,这使得利用正则表达式形式的多种多样的操作符成为可能,比如重复 (杨注:*),比如alternation (杨注:|),而且可以用在任何地方,而不仅仅是顶层处。基本上,每条规则都能构成一个DFA状态机。对于自顶向下的解析,这是可能的,因为解析器知道它位于哪条规则之中,在解析进行的过程中可以按规则的状态机进行。我认为这对于自底向上的解析,这是不可能的 (甚至如果你以某种方法令解析表做正确的事,归约那一步也需要归约有固定不变的参数个数。杨注:不懂)。这对于LL真是个好优点,因为有这些丰富的语法扩展(杨注:指类似正则表达式的),语法容易读多了。事实上,这有利于使LL那种严格语法的局面有所缓和,因为许多你需要左递归的地方都可以使用重复 (*)操作符替代。

1 // LR语法: 不允许任何特殊的,alternation 只允许
2 // 在顶层出现
3 //
4 // 允许这一条是因为它等价于
5 // pairs → pair pairs_tail
6 // pairs → ε
7 pairs → pair pairs_tail | ε
8  
9 // 扩展的LL语法; 之所以可能,是因为你可以对把每条规则
10 // 构造成一个DFA
11 pairs → (pair (',' pair)*)?

后一条规则可以构造出像这样的DFA (绿色的状态表示接受状态) :



知道上下文,也使得在规则中间的动作成为可能 (定制代码,这些代码运行在规则里的任意两个元素之间。杨注:如antlr的 semantic action)。Bison支持这一点,是通过在内部重写了语法,这使得所有的可视化 (杨注:可能指语法定义的时候?)都更加复杂了。

优势:LL

(3) LL解析器支持上下文相关的扫描/词法分析

知道上下文,另一个好处是也使得上下文相关的扫描/词法分析成为可能。比如,许多程序设计语言不允许把关键词用于变量名,因为独立的词法分析器 (及自底向上的解析器)不知道出现在这个位置上的token是变量名还是关键字。但是自顶向下的解析器调用词法解析器的时候,可以轻易地把当前的上下文传递给它。

优势:LL

(4) LL解析器支持继承属性

知道上下文,也能够支持基于LL的应用程序在构造树的时候把属性/元数据传递给树 (这有时被称为继承属性。杨注原文:inherited attribute)。 (无论LL还是LR解析器都支持综合属性 (杨注:原文synthesized attributes),是由树向上传递的)。

优势:LL

6. 结论

我描述了一种另类的LL和LR解析器的模型,这种模型与大多数文献中提到的等价,但是更符合直觉 (至少对我而言是这样)。我们可以把解析器视为黑盒子,这个黑盒子输入输出与先序和后序表示法对应的token和规则的流。至目前为止,我们还没有探索这些解析器的内部工作原理;我们只是把它们视作黑盒,我们不清楚它们内部的工作。我们也没有探究它们能处理和不能处理何种语法的问题。我们也没有探索LL和LR的变形 (Strong-LL, SLR, LALR等等)。我希望在接下来的文章中会更完整地讨论它们,再包含上示例代码。

No comments: