使用Java实现语言解释器.doc

使用Java实现语言解释器大多数程序员都曾经梦想着创造自己的计算机语言。坦率地说，能够创造、控制、增强和修改属于自己的计算机语言，这种想法确实非常具有吸引力。然而，只有极少数程序员认为，实现这个想法是一件非常容易和令人愉悦的事情。开发一个功能齐备的编译器(例如Java编译器)的确是一项艰巨的任务。但是相比之下，创建一个语言解释器却简单得多。尽管解释器和编译器都以应用程序源代码作为输入内容，但是它们对这些源代码的处理过程却截然不同。编译器将程序的源代码转化为可执行代码的形式。通常情况下，这种可执行代码由计算机的CPU指令组成，因此可以直接在计算机上执行。例如，C+即采用这种编译方式。还有一种情况，编译器输出一种可移植的中间代码，它们由运行时系统执行。Java采用的就是这种方式。在Java中，称这种中间代码为“字节码 ”。解释器的工作原理则完全不同。它顺序读入程序的源代码，然后依次执行每一条语句。因此，解释器并不真正将源代码转化为目标代码，而是直接执行程序。尽管使用解释器执行程序的速度比将相同的程序编译成目标代码后再执行的速度慢，但是解释器仍然在编程中被广泛使用。原因有以下几个方面：第一，解释器能够提供真正的交互式环境，由解释器执行的程序能够根据用户的指令暂停或者恢复运行。这种交互式环境在机器人技术等方面用途很广。第二，语言解释器的先天特性决定了它们特别适合于交互式的程序调试。第三，解释器最适合于作为“脚本语言”，比如数据库查询语言等。第四，语言解释器使得同一个程序运行于不同类型的平台成为可能。此时惟一的工作只是为每个新环境实现解释器的运行包。在有些情况下，术语“解释器”的含义与刚才所描述的情况有所不同。例如，最初的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 ProgramFOR 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。尽管从理论上讲可以使用两个独立的类：一个包含解释器，另一个包含表达式解析器；但是将两者用同一个类来实现的代效率会更高，因为表达式解析器和解释器的代码是密不可分的。例如，两个子系统都操作保存着程序代码的同一个字符数组。如果将它们分别安排在两个类中，将会增加可观的额外开销，并导致性能上的损失和功能上的重复。此外，由于程序解释的任务繁重，而解析表达式只是其中的一部分，因此将整个解释机制包含在单个类中是很有意义的。解释器执行时，每次从程序的源代码中读入一个标识符。如果读入的是关键字，解释器就按照该关键字的要求执行规定的操作。举例来说，当解释器读入一个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 / 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 =. final char LE = 1; final char GE = 2; final char NE = 3; / Array for variables. private double vars; / This class links keywords with their keyword tokens. class Keyword String keyword; / string form int keywordTok; / internal representation Keyword(String str, int t) keyword = str; keywordTok = t; /* Table of keywords with their internal representation. All keywords must be entered lowercase. */ Keyword kwTable = new Keyword(print, PRINT), / in this table. new Keyword(input, INPUT), new Keyword(if, IF), new Keyword(then, THEN), new Keyword(goto, GOTO), new Keyword(for, FOR), new Keyword(next, NEXT), new Keyword(to, TO), new Keyword(gosub, GOSUB), new Keyword(return, RETURN), new Keyword(end, END) ; private char prog; / refers to program array private int progIdx; / current index into program private String token; / holds current token private int tokType; / holds tokens type private int kwToken; / internal representation of a keyword / Support for FOR loops. class ForInfo int var; / counter variable double target; / target value int loc; / index in source code to loop to / Stack for FOR loops. private Stack fStack; / Defines label table entries. class Label String name; / label int loc; / index of labels location in source file public Label(String n, int i) name = n; loc = i; / A map for labels. private TreeMap labelTable; / Stack for gosubs. private Stack gStack; / Relational operators. char rops = GE, NE, LE, , =, 0 ; /* Create a string containing the relational operators in order to make checking for them 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 to execute. size = loadProgram(tempbuf, progName); if(size != -1) / Create a properly sized array to hold the program. prog = new charsize; / Copy the program into program array. System.arraycopy(tempbuf, 0, prog, 0, size); / Load a program. private int loadProgram(char p, String fname) throws InterpreterException int size = 0; try FileReader fr = new FileReader(fname); BufferedReader br = new BufferedReader(fr); size = br.read(p, 0, PROG_SIZE); fr.close(); catch(FileNotFoundException exc) handleErr(FILENOTFOUND); catch(IOException exc) handleErr(FILEIOERROR); / If file ends with an EOF mark, back up. if(psize-1 = (char) 26) size-; return size; / return size of program / Execute the program. public void run() throws InterpreterException / Initialize for new program run. vars = new double26; fStack = new Stack(); labelTable = new TreeMap(); gStack = new Stack(); progIdx = 0; scanLabels(); / find the labels in the program sbInterp(); / execute / Entry point for the Small BASIC interpreter. private void sbInterp() throws InterpreterException / This is the interpreters main loop. do getToken(); / Check for assignment statement. if(tokType=VARIABLE) putBack(); / return the var to the input stream assignment(); / handle assignment statement else / is keyword switch(kwToken) case PRINT: print(); break; case GOTO: execGoto(); break; case IF: execIf(); break; case FOR: execFor(); break; case NEXT: next(); break; case INPUT: input(); break; case GOSUB: gosub(); break; case RETURN: greturn(); break; case END: return; while (!token.equals(EOP); / Find all labels. private void scanLabels() throws InterpreterException int i; Object result; / See if the first token in the file is a label. getToken(); if(tokType=NUMBER) labelTable.put(token, new Integer(progIdx); findEOL(); do getToken(); if(tokType=NUMBER) / must be a line number result = labelTable.put(token, new Integer(progIdx); if(result != null) handleErr(DUPLABEL); / If not on a blank line, find next line. if(kwToken != EOL) findEOL(); while(!token.equals(EOP); progIdx = 0; / reset index to start of program / Find the start of the next line. private void findEOL() while(progIdx prog.length & progprogIdx != n) +progIdx; if(progIdx = varsstckvar.var) stckvar.loc = progIdx; fStack.push(stckvar); else / otherwise, skip loop code altogether while(kwToken != NEXT) getToken(); / Execute a NEXT statement. private void next() throws InterpreterException ForInfo stckvar; try / Retrieve info for this For loop. stckvar = (ForInfo) fStack.pop(); varsstckvar.var+; / increment control var / If done, return. if(varsstckvar.var stckvar.target) return; / Otherwise, restore the info. fStack.push(stckvar); progIdx = stckvar.loc; / loop catch(EmptyStackException exc) handleErr(NEXTWITHOUTFOR); / Execute a simple form of INPUT. private void input() throws InterpreterException int var; double val = 0.0; String str; BufferedReader br = new BufferedReader(new InputStreamReader(System.in); getToken(); / see if prompt string is present if(tokType = QUOTEDSTR) / if so, print it and check for comma System.out.print(token); getToken(); if(!token.equals(,) handleErr(SYNTAX); getToken(); else System.out.print(? ); / otherwise, prompt with ? / get the input var var = Character.toUpperCase(token.charAt(0) - A; try str = br.readLine(); val = Double.parseDouble(str); / read the value catch (IOException exc) handleErr(INPUTIOERROR); catch (NumberFormatException exc) /* You might want to handle this error differently than the other interpreter errors. */ System.out.println(Invalid input.); varsvar = val; / store it / Execute a GOSUB. private void gosub() throws InterpreterException Integer loc; getToken(); / Find the label to call. loc = (Integer) labelTable.get(token); if(loc = null) handleErr(UNDEFLABEL); / label not defined else / Save place to return to. gStack.push(new Integer(progIdx); / Start program running at that loc. progIdx = Value(); / Return from GOSUB. private void greturn() throws InterpreterException Integer t; try / Restore program index. t = (Integer) gStack.pop(); progIdx = Value(); catch(EmptyStackException exc) handleErr(RETURNWITHOUTGOSUB); / * Expression Parser * / Parser entry point. private double evaluate() throws InterpreterException double result = 0.0; getToken(); if(token.equals(EOP) handleErr(NOEXP); / no expression present / Parse and evaluate the expression. result = evalExp1(); putBack(); return result; / Process relational operators. private double evalExp1() throws InterpreterException double l_temp, r_temp, result; char op; result = evalExp2(); / If at end of program, return. if(token.equals(EOP) return result; op = token.charAt(0); if(isRelop(op) l_temp = result; getToken(); r_temp = evalExp1(); switch(op) / perform the relational operation case : if(l_temp r_temp) result = 1.0; else result = 0.0; break; case LE: if(l_temp : if(l_temp r_temp) result = 1.0; else result = 0.0; break; case GE: if(l_temp = r_temp