メンバページ: Go

やさしい Java インタプリタ の作り方


このページでは Java インタプリタを作っていきます。 ゆっくりしたペースになりますので、長い目で見てください。

Java のソースコードをキーボードから読み込んで、直ちに実行する ソースコードインタプリタです。


- 更新記録 -
1日目 Java 言語を解剖する
2日目 字句解析とは?
3日目 字句解析を作る(準備編)
4日目 字句解析を作る
5日目 字句解析を確認する
6日目 Java 言語を拡張する
7日目 構文解析の始め(BNF 記法から)
8日目 構文解析を作る(準備編)
9日目 構文解析と BNF の対応1(代入文)
10日目 逆ポーランド記法
11日目 (閑話)逆ポーランド記法と Lisp の S 式と JavaVM コード
12日目 (閑話)GC の話(1)
13日目 インタプリタ実行の準備1(実行環境)とリファクタリング
14日目 一番簡単なプログラムのインタプリタ実行

1日目 --- Java 言語を解剖する

Java インタプリタを作る前に Java を解剖してみます。

ここでは構文だけを見ていきます。Java は他の一般的な言語と同様に1語先読みを行うだけで 構文が解析できるような、プログラム言語に向いている構文規則を持っています。

語、語句、
トークン
プログラムを構成する最小のプログラム断片。例えば、class, foo, =, (, +, { など。
構文規則 構文だけに関する規則を集めたもの。
例えば、規則の一つに Java プログラムは宣言部とクラス定義から構成されるという規則がある。
意味は与えていないので、別に記述する必要がある。
1語先読み 現在の語(トークン)を構文規則に割り当てるために、次の1語だけ先読みすること。
1語先読みで、Java は構文規則が決定できる。
例えば、foo の次が = であれば、代入文であることが分かり、( であれば メソッド関数定義であることがわかる。

Lisp は構文規則が非常に少ないので実装は簡単でした。この意味で Java は Lisp と比較して面倒です。

次に Java には予約語というものがあります。例えば、class という語句はクラス定義を宣言する予約語の一つです。

これも一般的な言語では予約語の概念はあります。これにより、例えば

class class {}  // クラス class の定義。中身はなし。--> エラー

のようにクラス名 class のクラスを作成することはできません。

プログラマから見れば、これは強い制限です。予約語には class や public など 一般的な語句が多くありますので、それらは名前として使えません。 group や category は使えるのに class が使えないというのは、普通に考えて非常に不自然です。

一方、言語処理系の実装者から考えれば、この予約語の情報を使うことにより、 実装を手抜きすることができます。つまり予約語の概念は実装者のための概念です。

ちなみに Lisp や FORTRAN は予約語の概念はありません。

(defun defun (defun) nil)

上のように関数定義 defun を再定義することも可能です。 ちなみに上記は nil しか実行しませんので、実行すると、二度と関数定義ができなくなります。 このため、上記のようなものは実行できないようにチェックしていることが多いです。

また、String などのクラス名は予約語ではありません。システムで事前に定義されているクラスです。 構文規則的には書き換え可能で実際にも定義できます。例えば以下のように定義してみます。

package java.lang;

public class String {
  public static void main(String args[]) { // String でエラー
  }
} 

この状態ではもちろん、String クラスが実装不足ですので、実行すると以下のエラーが出ます。

C:\java>java String
Exception in thread "main" java.lang.NoClassDefFoundError: String (wrong name: java/lang/String)
        at java.lang.ClassLoader.defineClass0(Native Method)
        at java.lang.ClassLoader.defineClass(ClassLoader.java:502)
        at java.security.SecureClassLoader.defineClass(SecureClassLoader.java:123)
        at java.net.URLClassLoader.defineClass(URLClassLoader.java:250)
        at java.net.URLClassLoader.access$100(URLClassLoader.java:54)
        at java.net.URLClassLoader$1.run(URLClassLoader.java:193)
        at java.security.AccessController.doPrivileged(Native Method)
        at java.net.URLClassLoader.findClass(URLClassLoader.java:186)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:299)
        at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:265)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:255)
        at java.lang.ClassLoader.loadClassInternal(ClassLoader.java:315)

Java インタプリタを作成するときに上記のエラーも含めて、実行できるようにする必要があります。

Java のトークンを見てみますと、これは C などと同じ一般的な規則になっています。 例えば、 x=x+y++ のような記述が可能です。Lisp はそうではなく、シンボルに + や = の記号を入れることができますので、上記は一つのシンボルになります。

明日からは Java インタプリタを作っていきます。最初は字句解析から始めます。

See you again !!

このページトップへ

2日目 --- 字句解析とは?

字句解析部を作る前に、字句解析の概略を紹介します。

字句解析では、Java プログラムをトークン Token、または語句と呼ぶプログラムの 最小単位を取り出すための解析を行います。例えば

public class Test {
  static void main(String args[]) {

が与えれたときには、public, class, Test, {, static, void, main, (, String, args, [, ], ), { を取り出すことです。

このときに、同じ名前が出てくれば同じ名前として認識も行います。システム定義の名前が 出現したときにはシステム定義であることを認識します。また記号が出てきたときには、記号と して認識します。文字列や数値なども文字列、数値として認識します。

例えば、

x = x + 123

が与えられたときは、"x" という名前、"=" という記号、 前に出現した同じ名前である "x"、"+" という記号、"123" の値を持つ数値というように 認識する必要があります。

これをわかりやすくするために、記号を使って表現してみましょう。 例えば、以下のようにします。

(name x *1) (symbol '=') (name x *1) (symbol '+') (integer 123)

*1 は同じ名前 "x" であることを示しています。もちろん、入力として、

x=x+123

が与えられたときも、同じ結果になります。

記号 + なども、名前として同列に扱うことも可能ですが、上記のように文字と異なり、区切り記号としても働きますので、別個として管理します。

予約語とそれ以外の名前に分けて管理する方法もあり、ここではこのようにします。 それ以外の名前には、システムで事前に定義されているクラスの名前、例えば、String なども含まれます。これは1日目で書きましたように、再定義可能なものです。

以下に例を示します。

public class Test {
-->
(system public) (system class) (name Test) (symbol '{')

そこで Java の字句解析を作る観点で見ていきます。例えば、空白やタブ、改行などホワイトスペースの挿入は、トークンの間ではどこに入れて も問題ありません。

System    .   out    . 
       println   (  "Test"   )  ;

はもちろん、正しい Java プログラムです。やや見にくいですが。

次にコメントですが、Java には、主にプログラムコメントを記述する "//" から行末までのコメントと、主にドキュメンテーションコメントを記述する "/*" と "*/" で囲む方式のコメントがあります。コメントはプログラムの実行に影響を与えませんので、安全に削除できます。しかし最近の処理系ではデバッグの容易さなどから、実行時にも削除しないものが多いようです。しかし、ここでは簡単化のために、削除するようにします。

// ここから行末までは、プログラムコメントを記述します
/* 主にドキュメンテーションコメントを記述します 
   複数行に記述できます */

Java には、"++", "||", "+=" などの記号列も特別な意味を持って使用されます。 ここで特別と言ったのは、'a' などの通常の文字と、セパレータになるなど、扱いが異なるということです。

今日は字句解析の概要と Java に特化しての字句解析について紹介してきました。 明日は字句解析のための準備となるプログラムを作っていきます。

See you again !!

このページトップへ

3日目 --- 字句解析を作る(準備編)

今日は字句解析を行うための準備を行います。 まず、最初に字句解析した結果を蓄えるためのデータ構造を定義します。

2日目のところにも書きましたが、字句解析の結果として、数値、文字、 文字列、名前などに分類します。 名前は予約語とそれ以外の名前に分類し、同じ名前かどうかの判断 (唯一性の保障)もします。

実装として、各々、別のクラスとして作成する方法もありますが、 ここでは、それらを1個のクラスだけで表現するクラス「トークン」 クラスを導入します。

トークンクラスには、タイプを示すタグと実際のオブジェクトを格納する 部分から構成されます。以下にトークンクラスの定義を示します。

package javaInterpreter.lexicalAnalysis;

/**
 * Token Class --- Number, Symbol, List, String, Character
 * @author Go
 */
public class Token {
  Object value;
  int tag;
		  
  // コンストラクタ群
  // Integer
  Token(Integer i){
    value = i;
    tag = Tag.tagInteger;
  }
  // String
  Token(String str){
    value = str;
    tag = Tag.tagString;
  }
  // Character
  Token(Character c){
    value = c;
    tag = Tag.tagCharacter;
  }
  // Symbol
  Token(int type, char c){
    value = new Character(c);
    tag = type;
  }
  // Name
  Token(int type, String str){	
    value = str;
    tag = type;
  }
  // only Type
  Token(int type){
    value = null;
    tag = type;
  }

  // Getter
  public int getTag(){
    return tag;
  }
  public Object getValue(){
    return value;
  }
}

Integer, String, Character などのデータは Java の同名クラスの インスタンスオブジェクトにします。今回は Java インタプリタですので、 そのもののデータとなります。名前や記号は別個に管理しています。 現在の実装では1文字の記号、例えば、'+', '-' と2文字の記号列、例えば "==", "++" は別の管理をしています。後者は普通のシステム定義の予約語 と同じ扱いをしていますが、前者はと特別に管理しています。

以下にデバッグ用に作成したトークンを印字するためのメソッドを 紹介します。

/**
 * Printer
 * for Debug
 */
public void print() {
  System.out.print("Tag = " + tag + ", value = " + value);
}
/**
 * toString
 * for Debug
 */
public String toString(){
  if (tag == Tag.tagName || tag == Tag.tagSystem) {
     return "(" + toName(tag) +  " " + value.toString() + 
            " " + Integer.toHexString(this.hashCode()) + ")";
  }
  if (tag == Tag.tagSymbol) {
     return "(" + toName(tag) +  " '" + value.toString() + "')";
  }
  if (value != null) 
     return "(" + toName(tag) + " " + value.toString() + ")";
  else
     return "(" + toName(tag) + ")";
}
/**
 * tag int --> String
 * for Debug
 */
String toName(int tag) {
  switch (tag) {
    case Tag.tagInteger: return "Integer";
    case Tag.tagName: return "Name";
    case Tag.tagSymbol: return "Symbol";
    case Tag.tagSystem: return "System";
    case Tag.tagString: return "String";
    case Tag.tagCharacter: return "Character";
    case Tag.tagEnd: return "Program End";
    default: return String.valueOf(tag);
  }
}				

パッケージの構成ですが、全体のパッケージを "javaInterpreter" にします。字句解析の部分のパッケージを別にしてサブパッケージに します。ここでは、"javaInterpreter.lexicalAnalysis" にします。 以下にパッケージの関係図を示します。次の構文解析部である "parser" も示しています。

javaInterpreter -+- Main クラスを置く
                 |
                 +--- lexicalAnalysis --- 字句解析関連クラスを置く
                 |
                 +--- parser --- 構文解析関連クラスを置く
                 |

このパッケージで共通的に使用する定数にトークンクラスのタグがあります。 そこでこれを独立したクラスとして定義します。このクラスを以下に示します。 Token クラスと明日、紹介予定の Reader クラスから使用します。

package javaInterpreter.lexicalAnalysis;

/**
 * TAG Constant
 * @author Go
 */
public abstract class Tag {
  public final static int tagInteger = 0;     // 整数
  public final static int tagString = 1;      // 文字列
  public final static int tagCharacter = 2;   // 文字
  public final static int tagName = 3;        // 名前
  public final static int tagSymbol = 4;      // 記号
  public final static int tagSystem = 5;      // システム記号
  public final static int tagEnd = 10;	      // 終了マーク
}

名前の唯一性を確保するために、ハッシュテーブルを使用します。 ここではハッシュテーブルのサブクラスとして、名前クラスを定義します。

package javaInterpreter.lexicalAnalysis;

import java.util.*;
/**
 * Name
 * @author Go
 */
public class Name extends Hashtable  {
  public Name() { super(); }

  /**
  * 名前を入力にして、ハッシュテーブルにセットする
  */
  public Token put (String name) {
    Token token = get(name);
    if (token != null) return token;
    token = new Token(Tag.tagName, name);
    super.put(name, token);
    return token;
  }

  /**
  * 名前を入力にして、ハッシュテーブルにセットする
  */
  public Token put (int tag, String name) {
    Token token = new Token(tag, name);
    super.put(name, token);
    return token;
  }

  /**
  * シンボルを取り出す get(String)
  */
  public Token get (String name) {
    Token ret = (Token)super.get(name);
    return ret;
  }
}

今回は継承を使っていますが、委譲モデルでも作成できます。 次に予約語の登録をこの名前クラスに対して、行います。

package javaInterpreter.lexicalAnalysis;

/**
 * Resisits Reserved Word by Java System
 * @author Go
 */
public abstract class RegistReservedWord {
  static final String[] reservedWords 
    = {
       "++", "+=", "--", "-=", "**", "*=", "/=", "==", "!=", 
       "&&", "||", "&=", "|=",
       "abstract", 
       "boolean", "break", "byte",
       "case", "catch", "char", "class", "continue", 
       "default", "do",
       "else", "extends",
       "false", "final", "float", "for",
       "implements", "import", "int", "interface",
       "new", "null",
       "package", "private", "protected", "public", 
       "return", 
       "short", "static", "super", "switch", "synchronized",
       "this", "throws", "try", "true",
       "void",
       "while",
      };
  public static void init(Name env) {
    for (int i = 0, size = reservedWords.length; i < size; i++) {
      env.put(Tag.tagSystem, reservedWords[i]);
    }
  }
}

これでやっと準備が終わりました。明日は字句解析の中心部を作っていきます。

See you again !!

このページトップへ

4日目 --- 字句解析を作る

今日は字句解析の本体を作成しましょう。前回のときの Lisp 処理系のリーダ 部分を流用します。

ファイル名も Reader.java と同じです。最初の部分を以下に示します。 Lisp のときとほとんど同じコードになります。

// 2003 Copyright (C) GOMI Hiroshi
package javaInterpreter.lexicalAnalysis;

import java.io.*;
import java.util.*;

/**
* 字句解析リーダ Reader
* @author Go
*/ 
public class Reader {
  final int CharBuffSize = 256;		// 文字処理バッファのサイズ
  private char[] charBuff = null;	// 文字処理バッファ
  private char ch;			// 1文字バッファ
  private String line;			// 1行入力バッファ
  private int indexOfLine = 0;		// 1行内の位置
  private int lineLength = 0;		// 1行の文字数
  BufferedReader br = null;		// リーダ
  private ArrayList tokens = new ArrayList(); // トークンリスト
  public Name env = new Name();		// 名前環境

  /**
  * 字句解析リーダ
  * コンストラクタ
  */
  public Reader() {
    charBuff = new char[CharBuffSize];
    br = new BufferedReader(new InputStreamReader(System.in));
  }

字句解析の結果を ArrayList tokens に蓄えるようにします。 tokens は昨日、紹介したものです。これは字句解析した結果を 入れるクラスで、タグ部と値部からなります。

次にリーダ部ですが、複数行の入力を可能にしています。 今は入力の終りをユーザが明示的に '!' を最後に入れることで 対応するようにしました。

  /**
  * トークンリーダ (字句解析)
  */
  public ArrayList read() throws IOException {
    System.out.print("Java>");
    getTokenPrepare();
    while (getToken()) {
    	System.out.print("    >");
    	getTokenPrepare();
    }
    return tokens;
  }

getToken() は先ほどの tokens へ字句解析の結果を入れる サイドエフェクトを行うメソッド関数です。 プロンプトを出すようにもしています。

文字列からの入力も作成します。次に getToken() の準備のための メソッド関数を定義します。

  /**
  * トークンリーダ from 文字列
  */
  public ArrayList readFromString(String input) throws IOException {
    getTokenPrepareString(input);
    while(getToken()){
    	getTokenPrepareString(input);
    }
    return tokens;
  }

  /**
  * getToken の準備 getTokenPrepare
  */
  void getTokenPrepare() throws IOException {
    line = br.readLine();              // 1行読み込み
    gSP();
  }
  // getToken の内部関数
  void gSP() {
    indexOfLine = 0;
    lineLength = line.length();
    // 効率化のために charArray へ格納する
    line.getChars(0, lineLength, charBuff, 0); 
    charBuff[lineLength] = '\0';       // 終了マーク
    getChar();
  }

  /**
  * 文字列からの読み込みの準備 getTokenPrepare
  */
  void getTokenPrepareString(String input) {
    line = input;
    gSP();
  }

Lisp のときと同じように、現在の文字を読む getChar() と 次の文字を読む nextChar() を定義します。前のときと同じように getChar() はサイドエフェクトを行うメソッド関数です。

  /**
  * 配列から1文字読み込み ch に値をセットし、indexOfLine を進める
  */
  void getChar() { ch = charBuff[indexOfLine++]; }

  /**
  * 配列から現在の1文字を返す (indexOfLine は進めない)
  */
  char nextChar() {
    return charBuff[indexOfLine];
  }

さて、いよいよ getToken() です。

  /**
  * トークンの読み込み getToken
  *   ch は読み込んでいる状態で、このメソッドを呼び出すこと
  */
  boolean getToken() throws IOException {
    for (; 
         indexOfLine <= lineLength; 
         getChar()) {
      if (Character.isWhitespace(ch)) continue;
      if (Character.isDigit(ch)) {					// 数値
      	 tokens.add(makeNumber());
      	 continue;
      }
      if (ch == '/') if (makeComment()) break; else continue;
      if (ch == '"') tokens.add(makeString());		// 文字列
      else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' ||
      			ch == '|' || ch == '&' || ch == '!' || ch == '>' ||
      			ch == '<') 
      		   tokens.add(makeSymbol(ch));			// ++, +=, --, -=, ...
      else if (isSymbol(ch)) tokens.add(new Token(Tag.tagSymbol, ch));// 記号       
      else tokens.add(makeSymbol());				// 名前
    } // end of for
    if (charBuff[indexOfLine - 2] == '!') return false;	// 終了チェック
    return true;
  } 

  /**
  *  記号の判定 
  */
  boolean isSymbol(char ch) {
  	if (ch < 'A') return true; 
  	if (ch == '{' || ch == '}' || ch == '[' || ch == ']') return true;
  	return false;
  }

ここで1文字づつ読み込んで、文字により、処理メソッドを呼び出します。

以下のプログラムで、2種類の形式のコメントを読み飛ばすようにしています。

  /**
   * コメント
   */
  boolean makeComment(){
    char nch = nextChar();
    if (nch == '/') return skipLF();
    if (nch == '*') return skipComment();
    return false;
  }

  /**
   * Skip LineFeed
   */
  boolean skipLF(){
    getChar();
    while (ch != '\n' && ch != '\0') {getChar();}
    return indexOfLine >= lineLength + 2;	// 2 is postAdd + '\0'	
  }
  
  /**
   * Skip ComentEnd
   */
  boolean skipComment(){
    getChar();		// skip '*' 
    getChar();
    while (true) {
      char nch = nextChar();
      if (ch == '*' && nch == '/') break;
      getChar();
    }
    getChar();		// skip '/'
    return indexOfLine >= lineLength + 2;		
  }

次に、トークンの種類による、専用の処理ルーチンです。 ここも Lisp のときとほぼ同じルーチンになっています。

  /**
  * 数の読み込み makeNumber
  */
  Token makeNumber() throws IOException {
    StringBuffer str = new StringBuffer();
    for (; 
         indexOfLine <= lineLength; 
         getChar()) {
      if (!Character.isDigit(nextChar())) break;
      str.append(ch);
    }
    Token token = new Token(new Integer(Integer.parseInt("" + str + ch)));
    return token;
  }

  /**
  * シンボルの読み込み makeSymbol(preSymbolChar)
  */
  Token makeSymbol(char preChar) {
    char nch = nextChar();  
    if (preChar == nch || nch == '=') {   // ++, +=, --, -=, **, *=, //, /=, 
      getChar();                          // &&, &=, ||, |=, !!, !=, >>, <<
      return env.put("" + preChar + nch); // <=, >=
    }
    return new Token(Tag.tagSymbol, preChar);
  }

  /**
  * シンボルの読み込み makeSymbol
  */
  Token makeSymbol() throws IOException {
    StringBuffer str = new StringBuffer().append(ch);
    return makeSymbolInternal(str);
  }

  /**
  * 途中の文字列を渡してのシンボルの読み込み
  *   MakeSymbolInternal(StringBuffer)
  */
  Token makeSymbolInternal(StringBuffer str) throws IOException {
    while (indexOfLine < lineLength) {
	  if (!Character.isLetter(nextChar())) break;
      getChar();
      str.append(ch);
    }
    String symStr = "" + str;
    
    Token symbol = env.put(symStr);
	return symbol;
  }

  /**
  * 文字列の読み込み makeString
  */
  Token makeString() throws IOException {
    StringBuffer str = new StringBuffer();
    while (indexOfLine < lineLength) {
	  if (nextChar() == '"') break;
      getChar();
      str.append(ch);
    }
    getChar();					// " の読み飛ばし
    String strStr = "" + str;
	return new Token(strStr);
  }
  
  /**
   * ArrayList tokens
   */
  public void clearTokens() {
  	tokens.clear();
  }
}

以上で、字句解析部分の作成は完了しました。 今日の部分はほとんど Lisp のリーダを流用しています。

明日はこの文字認識の動作の確認をします。

See you again !!

このページトップへ

5日目 --- 字句解析を確認する

今日は字句解析部の動作確認をするためのクラスを作成して、 実際に動作を確認してみましょう。

実際には、このメソッドを先に作るようにしています。 パッケージは将来のメインメソッドにする予定ですので、 上のパッケージ、javaInterpreter にします。 そこから、 javaInterpreter.lexicalAnalysis.* のクラスを使用するようにします。

package javaInterpreter;

import javaInterpreter.lexicalAnalysis.*;
import java.util.*;

/**
 * Java Interpreter Main
 * @author Go
 */
public class Javai {

  public static void main(String[] args) {
    Reader read = new Reader();
    RegistReservedWord.init(read.env);
    while (true) {
      try {
        ArrayList pass1 = read.read();
        print(pass1);
        read.clearTokens();
      }catch (Exception e) {
        e.printStackTrace();
      }
    }
  }
	
  static void print(ArrayList al){
    for (int i = 0, size = al.size(); i < size; i++)
      System.out.print(" " + al.get(i).toString());
    System.out.println("...");
  } 
		
}

read.read() が字句解析部の呼び出しメソッドです。 そこで ArrayLIst tokens を pass1 で受け取っています。

次に実際に動作させてみた結果を紹介します。

Java>public class Test {
    >  void static main (String args[]) {
    >    System.out.println("Test!");
    >  }
    >}!
 (System public 1f1fba0) (System class 1befab0) (Name Test 13c5982) 
 (Symbol '{') (System void 1186fab) (System static 14b7453)
 (Name main c21495) (Symbol '(') (Name String 1d5550d) (Name args a0dcd9)
 (Symbol '[') (Symbol ']') (Symbol ')') (Symbol '{') (Name System 1034bb5)
 (Symbol '.') (Name out 15f5897) (Symbol '.') (Name println b162d5)
 (Symbol '(') (String Test!) (Symbol ')') (Symbol ';') (Symbol '}')
 (Symbol '}') (Symbol '!')...

今度は分かりやすくするために、対象を小さくしてみます。

Java>x = x + 1!
 (Name x 1cfb549) (Symbol '=') (Name x 1cfb549) (Symbol '+') (Integer 1)
 (Symbol '!')...

String と int でクラス宣言してみます。

Java>String str = "abc" + str2;!
 (Name String 1d5550d) (Name str 186d4c1) (Symbol '=') (String abc)
 (Symbol '+') (Name str 186d4c1) (Integer 2) (Symbol ';') (Symbol '!')...
Java>int x = x +1!
 (System int f9f9d8) (Name x 1cfb549) (Symbol '=') (Name x 1cfb549) 
 (Symbol '+') (Integer 1) (Symbol '!')...

以上で、字句解析の動作確認の紹介をしました。 明日からは、この字句解析の結果を使用して、与えられた Java プログラム が構文的に正しいかどうかを判断するようにします。

See you again !!

このページトップへ





Copyright (c) 2003 OKI Software Co., Ltd.