Question

所谓翻译（编译与解释）无非是将一系列的源代码文本（所对应的计算行为）排列成一个顺序序列，而最终的执行器——无论是机器还是解释器——只是从 这个顺序序列的起始位置 开始处理，一直到结束 9 。正是因为这个缘故，所以 依据什么排序 才会是翻译中的一个关键问题。

语法树是对语法元素进行排序的一个方案。这一方案将语法元素解析为不同类型的树结点，例如操作符结点、操作数结点等。以下面的代码为例：

a, i = 100, v = i + 100;

它可能被解析成如图 15 所示的语法树 10 。

图 15　语法树：对语法元素进行的排序

在该语法树中，所有叶子结点都是标识或直接的值——它们代表数据，而非叶子结点则是操作，亦即逻辑；如果是逻辑，则计算的结果可以作为其他计算所需的数据，例如图中的结点 8 的计算结果是结点 4 操作数。

当如上的语法树形成之后，顺序扫描树中所有结点的方法有两个：深度优先遍历与广度优先遍历——理论上说存在无数种可能的方法，这取决于形成该树时所使用的算法。以使用深度优先遍历算法为例，我们将得到下面这样一个处理顺序：

2,5,6,3,7,9,10,8,4,1

去除掉标识和数据部分，我们看到的是：

_,_,_,3,_,_,__,8,4,1

这几个操作的顺序，即我们对“顺序计算（逻辑）”在语法树上的重现。

那么，以数据排序又会是怎样的一种情形呢？例如，下面的代码：

1 2 3 4

i := 100; y := "hi"; x := 5; i := x*2 + i;

可以产生一个类似的语法树，如图 16 所示。

图 16　生成的语法树（为分析“基于数据的排序”而进行了排版变化）

（除了版式上的不同）这个图与此前的图并没有本质的区别，我们仍然可以按上述遍历规则得到一个执行顺序——如果你将这个图理解为 基于运算的排序 的话。但是，我们这里要讨论的是 基于数据的排序 ，即：运算影响到哪些数据，以及其影响先后的问题。基于此前的讨论，我们可以将“数据”理解为运算所需的参考——上下文环境，然后

• 将图 6 中树的每一个运算放到它所需的上下文环境中，并
• 将这些环境用框图及其层次表达出来 11 。

如图 17 所示。 12

图 17　基于数据的排序：将“数据”理解为运算所需的参考

可见，本质上来说，我们要正确处理此前的代码文本，则意味着我们将对上下文环境的相关性进行排序：内层是被依赖的，因此排序优先级更高；同层不存在数据/上下文环境依赖，因此优先级相等（例如 1 与 3，以及 2 与 4） 13 。

比较两种方案：以数据为顺序时，标识符的作用域（亦即是上下文环境）问题将会绑定在语法树上；而以逻辑为顺序时，作用域问题与语法树是无关的。

1. 对于“数”的支持，在动态或静态语言中并没有根本的不同，但其中的匿名函数在静态语言中实现起来要困难很多——不过这并非无法实现，例如 Delphi 2009 以后的版本。 ↩
2. 与上述“匿名 XX”相对应的，我们称之为“具名”。 ↩
3. 注意这里没有强调值与标识的绑定，这是因为存在变量的缘故。对于 Erlang 这类语言来说，所有 “作为系统计算的前设”的值 都必须是常量性质的，即：不可写且类型确定。 ↩
4. 动态/静态绑定这个概念被用在很多的地方，我们这里只明确地阐述其中的一种形式。即一个无类型、无值的变量，可以动态绑定一个值来赋予它类型的概念，即后文的动态类型。除此之外，我们并没有讨论在静态语言中存在的一个有类型变量，在执行期进行绑定（赋值）的情况。 ↩
5. 重写一个具名函数看起来是一个动态特性，但它其实并没有改变标识上的数据类型，所以不作为这里的动态重写来讨论。从另一个角度来说，具名函数的重写与 i++ 的性质是一样的。 ↩
6. Undefined 在 JavaScript 中也是一个类型，但这是概念完备性的一种表现，并非我们这里讨论的数据结构。 ↩
7. 也许有人会说“元素更少，则更易理解”，但并不全然如此。抽象概念过少的时候，我们的表达是倾向于重叠指代的，例如“船”，既是名词也作动词。在编程语言中，这通过 ship 与 ship() 来表达，便已经具备了两个符号（与其组合）——这使得我们在抽象概念上，至少已经分出了数据与行为。 ↩
8. 在《数据结构》中，这被称为“检索”，它与下一小节要讨论的“排序”是两个非常关键的“（计算）行为”。 ↩
9. 这种结束有两种可能，其一是序列完全计算完毕，我们通常理解为“退出”；其二是序列进入一个无休止的循环过程，我们通常理解为“等待—就绪”。对于执行器来说，这个顺序的代码序列（静态文本的翻译结果）所代表的执行逻辑（动态的处理）既可能是操作系统所调度的 CPU 执行权限的入口，也可能是一个解释器的执行片段的起始——不幸的是两种情况都被称为 process，只是前者通常译为进程，后者则译为处理。 ↩
10. 本例是 JavaScript 解释器引擎的一个实际解析结果。需要留意的是：不同的语言以及其翻译器在解析细节上可能会有不同，因而可能产生别的结果。 ↩
11. 内层的环境是外层的环境的一个参考，或称之为历史环境的一个映像。 ↩
12. 其一，图中的 1~4 为代码行号。其二，为方便绘制，图中省去了直接值结点，只留下表示数据依赖关系的标识。 ↩
13. 注意由于优先级相等表明了不存在同层相互间的依赖，也就意味着同层的代码文本是可以并行执行的；当以类似闭包（scope）这样的方式来解析代码并表达它们的层次关系时，是原生支持并行语言的。 ↩