CHAPTER3使用 Java 实现语言解释器大多数程序员都曾经梦想着创造自己的计算机语言。坦率地说，能够创造、控制、增强和修改属于自己的计算机语言，这种想法确实非常具有吸引力。然而，只有极少数程序员认为，实现这个想法是一件非常容易和令人愉悦的事情。开发一个功能齐备的编译器( 例如 Java 编译器)的确是一项艰巨的任务。但是相比之下，创建一个语言解释器却简单得多。尽管解释器和编译器都以应用程序源代码作为输入内容，但是它们对这些源代码的处理过程却截然不同。编译器将程序的源代码转化为可执行代码的形式。通常情况下，这种可执行代码由计算机的 CPU 指令组成，因此可以直接在计算机上执行。例如，C+即采用这种编译方式。还有一种情况，编译器输出一种可移植的中间代码，它们由运行时系统执行。Java 采用的就是这种方式。在 Java 中，称这种中间代码为“字节码 ”。解释器的工作原理则完全不同。它顺序读入程序的源代码，然后依次执行每一条语句。因此，解释器并不真正将源代码转化为目标代码，而是直接执行程序。尽管使用解释器执行程序的速度比将相同的程序编译成目标代码后再执行的速度慢，但是解释器仍然在编程中被广泛使用。原因有以下几个方面：第一，解释器能够提供真正的交互式环境，由解释器执行的程序能够根据用户的指令暂停或者恢复运行。这种交互式环境在机器人技术等方面用途很广。第二，语言解释器的先天特性决定了它们特别适合于交互式的程序调试。第三，解释器最适合于作为第 3 章 使用 Java 实现语言解释器 39“脚本语言” ，比如数据库查询语言等。第四，语言解释器使得同一个程序运行于不同类型的平台成为可能。此时惟一的工作只是为每个新环境实现解释器的运行包。在有些情况下，术语“解释器”的含义与刚才所描述的情况有所不同。例如，最初的 Java 运行时系统被称为“字节码解释器” 。但是这种解释器与本章中介绍的解释器的类型并不完全相同。字节码是一组高度优化的可移植的机器指令，而 Java 运行时系统则为字节码提供一个执行环境。然而 Java 运行时系统并不直接执行源代 码 ， 而 是 执 行可 移 植 的 机 器 代 码 。 这 也 是 Java 运 行 时 系 统 被 称 为 Java 虚 拟 机 的 原 因 。本章将要介绍的解释器代码不仅有趣而且实用。同时，它还充分显示了 Java 语言简单高效的特性。与第 2 章中介绍的解析器相同的是，这个语言解释器也使用“纯代码”编写。同时，解释器也是一个相当复杂的程序，但是使用 Java 语言实现起来却非常简单，这也是 Java 语言功能多样化的一个例证。此外，解析器代码的简洁还显示了 Java语法和库的强大表达能力。3.1 解释何种计算机语言在构造解释器之前，首先必须确定将要解释的语言类型。尽管 Java 似乎是个不错的选择，但是它过于庞大和复杂。即使选取 Java 语言的一个小的子集也显得太大了，因为我们只打算利用一章的篇幅进行讲解。而且，通常情况下也没有必要为一个像 Java那么强大的语言编写解释器；相反地，编写一个解释器处理某种相对简单的计算机语言倒是可行的。因此，更好的做法是选择一种易于解释、较为简单的语言。BASIC 语言的早期版本就非常符合这些标准，因此在此选择了 BASIC 语言的一个子集，将其作为本章中所介绍的解释器的解释语言。在下文中将称这个子集为 Small BASIC。本章选择了这个类 BASIC 语言有 3 方面原因。第一，BASIC 语言最初正是为解释执行而设计的。因此，实现一个 BASIC 解释器相对比较容易。例如，BASIC 语言的早期版本不支持局部变量、递归方法、语句块、类、重载等特征 但是以上所有这些特性都将增加 BASIC 语言的复杂性。虽然缺少了许多功能，但是解释 BASIC 子集的基本原理同样适用于其他语言。理解本章中介绍的解释器代码，能够为开发其他语言解释器打下基础。选择 BASIC 的第二个原因是，可以用相对较小的代码量实现一个较为合理的子集。第三，早期的 BASIC 语言语法简单、容易掌握，几乎不需要用额外的时间来学习。因此，即使一点都不了解传统的 BASIC 语言，也能够毫无困难地使用 Small BASIC。下面给出一个用 Small BASIC 编写的程序，可以看到，使用这种语言是多么的简单。即使从来没有见过传统风格的 BASIC 程序，也能够轻松理解其操作过程。PRINT A Simple Small BASIC Program Java 编 程 艺 术40FOR X = 1 TO 10GOSUB 100NEXTEND100 PRINT XRETURN该程序运行后得到如下的输出结果：A Simple Small BASIC Program1.02.03.04.05.06.07.08.09.010.0尽管在 Small BASIC 语言中关键字的含义几乎一目了然，但是本章仍将详细解释每个关键字。最后，Small BASIC 仿造的是早期的 BASIC 版本，它不同于后来出现的 Visual Basic。事实上， Visual Basic 与原始的 BASIC 几乎没有多少共同点。当然，只要掌握了这个解释器的工作原理，就可以改造它，使之能够解释所需要的任何语言或者变量。3.2 解释器概述在开始之前有必要再次强调：本章介绍的解释器是一个源代码解释器。也就是说，解释器在执行时，每次读入一条语句，并且根据这条语句执行特定的操作；然后再读入下一条语句，依次类推。这与伪代码解释器是有所区别的，例如早期的 Java 运行时系统。两者的区别在于：源代码解释器直接对程序的源代码解释执行；而伪代码解释器先将程序的源代码转化为某种与机器无关的中间代码，然后再执行中间代码。相比之下，源代码解释器更易于创建，并且不需要一个独立的编译过程。Small BASIC 解释器包括两个主要的子系统：一个是表达式解析器，负责处理数字表达式；另一个是解释器，负责程序的实际执行。对于前者，可采用本书第 2 章所介绍的表达式解析器。但是在这里做了某些改进，使得解析器能够解析包含在程序语句中的数字表达式，而不是只能解析孤立的表达式。解释器子系统和解析器子系统包含在同一个解释器类中，该类名为 SBasic。尽管从第 3 章 使用 Java 实现语言解释器 41理论上讲可以使用两个独立的类：一个包含解释器，另一个包含表达式解析器；但是将两者用同一个类来实现的代效率会更高，因为表达式解析器和解释器的代码是密不可分的。例如，两个子系统都操作保存着程序代码的同一个字符数组。如果将它们分别安排在两个类中，将会增加可观的额外开销，并导致性能上的损失和功能上的重复。此外，由于程序解释的任务繁重，而解析表达式只是其中的一部分，因此将整个解释机制包含在单个类中是很有意义的。解释器执行时，每次从程序的源代码中读入一个标识符。如果读入的是关键字，解释器就按照该关键字的要求执行规定的操作。举例来说，当解释器读入一个 PRINT 后，它将打印 PRINT 之后的字符；当读入一个 GOSUB 时，它就执行指定的子程序。在到达程序的结尾之前，这个过程将反复进行。可以看到，解释器只是简单地执行程序指定的动作。3.3 Small BASIC 解释器Small BASIC 解释器的代码相当长 一般情况下不会将这么长的代码放在书的一章之中。但是不要被它的长度所吓倒。抛开其长度不谈，这个解释器的概念其实比较简单，只要掌握了解释器的一般模式，就能轻松理解它的每个部分。接下来给出 Small BASIC 解释器的完整代码。本章剩下的篇幅将详细解释它的工作原理和使用方法。/ A Small BASIC Interpreter.import java.io.*;import java.util.*;/ Exception class for interpreter errors.class InterpreterException extends Exception String errStr; / describes the error public InterpreterException(String str) errStr = str; public String toString() return errStr; / The Small BASIC interpreter.class SBasic final int PROG_SIZE = 10000; / maximum program size Java 编 程 艺 术42/ These are the token types. final int NONE = 0; final int DELIMITER = 1; final int VARIABLE = 2; final int NUMBER = 3; final int COMMAND = 4; final int QUOTEDSTR = 5;/ These are the types of errors. final int SYNTAX = 0; final int UNBALPARENS = 1; final int NOEXP = 2; final int DIVBYZERO = 3; final int EQUALEXPECTED = 4; final int NOTVAR = 5; final int LABELTABLEFULL = 6; final int DUPLABEL = 7; final int UNDEFLABEL = 8; final int THENEXPECTED = 9; final int TOEXPECTED = 10; final int NEXTWITHOUTFOR = 11; final int RETURNWITHOUTGOSUB = 12; final int MISSINGQUOTE = 13;final int FILENOTFOUND = 14; final int FILEIOERROR = 15; final int INPUTIOERROR = 16;/ Internal representation of the Small BASIC keywords.final int UNKNCOM = 0;final int PRINT = 1;final int INPUT = 2;final int IF = 3;final int THEN = 4;final int FOR = 5;final int NEXT = 6;final int TO = 7;final int GOTO = 8;final int GOSUB = 9;final int RETURN = 10;final int END = 11;final int EOL = 12;/ This token indicates end-of-program. final String EOP = 0; / Codes for double-operators, such as , =, 0;/* Create a string containing the relationaloperators in order to make checking forthem more convenient. */String relops = new String(rops);/ Constructor for SBasic.public SBasic(String progName) throws InterpreterException char tempbuf = new charPROG_SIZE;int size;/ Load the program