argius note

プログラミング関連

JavaでJVM言語を作ってみる(5) - JavaCCとJJTreeの導入

Java

今回は解析器ジェネレータについて見ていきます。

第1回でも触れましたが、Unix-like環境というかC言語では少し昔からスタンダードなものはyacc+lexというものがあります。他にも字句解析器ジェネレータ＋構文解析器ジェネレータで使われる例は多いようです。
と言ったものの、解析器ジェネレータについてはこれ以上詳しく知らないので、早速JavaCCの話に移ります。

JavaCC

JavaCCは、字句解析器ジェネレータです。拡張子.jjのファイルにEBNF(拡張BNF)を使って文法を記述しておき、これを入力するとJava言語で記述された字句解析器のソースコードが生成されます。
解析器生成の仕様を記述するには、BNF(バッカス・ナウア記法)というメタ言語を用いるのが一般的です。バッカス・ナウア記法は、プログラミング言語に限らず、文脈自由文法を定義することができます。最近ではBNFに正規表現を導入したEBNF(Extended -)が使われています。（Wikipedia参照）


下記ページからダウンロードします。今回使用しているのは、バージョン5.0です。

アーカイブを適当なディレクトリに展開します。ここを${javacc.home}として、"${javacc.home}/bin"にパスを通します。

使い方は、.jjファイルを記述しておき、

$ javacc spec.jj

とします。自動生成するコード以外も.jjファイルに書くので、.jjファイルをを修正→ビルド、をするだけで再構築できます。
JavaCCには、構文解析のためのツリーを構築するための解析器を生成するJJTreeというツールが付属しています。
こちらは、.jjtファイルを入力します。

$ jjtree spec.jjt

.jjファイルの時と同様です。構文解析器を生成します。

"${javacc.home}/examples"にサンプルが多数用意されていますので、入門用に使えそうです。


ここでは、その中のサンプルをいくつか使ってみます。

構文解析

examplesの"JavaGrammars/1.5"には、Java1.5の文法を解析する.jjファイルがあります。

ここに以下の内容のファイルを作っておきます。

  • Dump.java: トークンをダンプする
import java.io.*;

class Dump {
    static void printToken(Token token) {
        System.out.printf("(%02d) %-24s %s%n", token.kind, JavaParserConstants.tokenImage[token.kind], token.image);
    }
    public static void main(String[] args) throws IOException {
        for (final String arg : args) {
            JavaParser parser = new JavaParser(arg);
            while (true) {
                Token token = parser.getNextToken();
                printToken(token);
                if (token.kind == JavaParserConstants.EOF) break;
            }
        }
    }
}

あとはAntでビルドします。
※Windows（7限定？）ではビルドがエラーになります。下記のようにターゲット"generated-files"のjavaccに.batをつけ、オプションを消せば上手くいくようになります。なお、javacc.homeがjavacc.rootとなっていて、設定値は相対パスになっていますのでご注意ください。

  <target name="generated-files" depends="parser-files-init" if="parser.gen">
     <exec failonerror="true" executable="${javacc.root}/bin/javacc.bat" >
           <arg value="Java1.5.jj"/>
     </exec>
  </target>

入力用に、HelloWorld的なJavaファイルを作ります。これはビルド不要です。

class HelloWorld {
    public static void main(String[] args) {
        final int i = 123;
        System.out.println("hello, " + i + 99.9f);
    }
}

これをDumpプログラムに渡せば、トークンに分割して出力されます。

$ java Dump HelloWorld.java 
  20 "class"                  class
  76 <IDENTIFIER>             HelloWorld
  81 "{"                      {
  48 "public"                 public
  51 "static"                 static
  62 "void"                   void
  76 <IDENTIFIER>             main
  79 "("                      (
  76 <IDENTIFIER>             String
  83 "["                      [
  84 "]"                      ]
  76 <IDENTIFIER>             args
  80 ")"                      )
  81 "{"                      {
  30 "final"                  final
  39 "int"                    int
  76 <IDENTIFIER>             i
  89 "="                      =
  65 <INTEGER_LITERAL>        123
  85 ";"                      ;
  76 <IDENTIFIER>             System
  87 "."                      .
  76 <IDENTIFIER>             out
  87 "."                      .
  76 <IDENTIFIER>             println
  79 "("                      (
  75 <STRING_LITERAL>         "hello, "
 103 "+"                      +
  76 <IDENTIFIER>             i
 103 "+"                      +
  69 <FLOATING_POINT_LITERAL> 99.9f
  80 ")"                      )
  85 ";"                      ;
  82 "}"                      }
  82 "}"                      }
   0 <EOF>                    
$

先頭の数値は、トークン種別のIDとして使われるint定数の値です。次が種別の文字列表現、最後がトークン自体の文字列です。予約語、リテラル、識別子、記号、に分類されていることが分かります。
同じソースコードをインデントや改行規則を崩して書いても、同様の結果に沿ってないコードでも同様の結果が得られます。つまり、「フリーフォーマット」として解析できているということになります。

JJTreeで構文木を作る構文解析器を作る

今度は構文解析器をJJTreeを使って生成します。
examplesのJJTreeExamplesを使ってみます。
eg1〜4の例がありますが、eg4はVisitorパターンにより構文木（syntax tree）をたどりながら処理ができるようになっていて、VisitorとしてEg4DumpVisitor.javaがjjtではなく直接Javaファイルとして用意されています。
これを使えば手間が省けそうです。

まずはそのまま動かしてみます。

※Windowsの場合、Antの"javacc.home"がUNIX系のパスになっていますので、書き換える必要があります。

$ ant eg4
（中略）
     [echo] *******
     [echo] ******* Now cd into the eg4 directory and run 'java Eg4' ******
     [echo] *******

BUILD SUCCESSFUL
Total time: 2 seconds
$ cd eg4
$ java Eg4
Reading from standard input...
(3 + 2 + a) * (2 + b) + c;
Start
 Add
  Mult
   Add
    Integer
    Integer
    Identifier: a
   Add
    Integer
    Identifier: b
  Identifier: c
Thank you.
$

式は自分で入力する箇所です。";"で終了です。
Eg4DumpVisitor.javaを見てみると、各visitメソッドで"System.out.println(indentString() + node)"を実行しています。これをnode#childrenAcceptより前に呼び出しているので、ツリーを「降りる」前にprintlnしているということになります。"--indent"の行の後にも"System.out.println(indentString() + node)"を実行して、降りる前と後が分かるようにしてみます。

  • Eg4DumpVisitor.java 改造部分抜粋
  private String indentString() {
    return indentString(false);
  }

  private String indentString(boolean end) {
    StringBuffer sb = new StringBuffer();
    for (int i = 0; i < indent; ++i) {
      sb.append(' ');
    }
    sb.append("[" + (end ? "E" : "S") + "]");
    return sb.toString();
  }

  public Object visit(ASTInteger node, Object data) {
    System.out.println(indentString() + node);
    ++indent;
    data = node.childrenAccept(this, data);
    --indent;
    System.out.println(indentString(true) + node);
    return data;
  }

Reading from standard input...
(3 + 2 ) * 4;
[S]Start
 [S]Mult
  [S]Add
   [S]Integer
   [E]Integer
   [S]Integer
   [E]Integer
  [E]Add
  [S]Integer
  [E]Integer
 [E]Mult
Thank you.

ENDのタイミングで命令コードを出力するようにしておけば、そのままCalcGenとして使えそうです。


ところが、このままだと上手く行かないケースがあります。同じ優先順位の演算子の場合だと、ひとつのノードに3以上の子がぶらさがってしまいます。

Reading from standard input...
1 + 2 - 3 + 4;
[S]Start
 [S]Add
  [S]Integer
  [E]Integer
               # -->iconst_Integer
  [S]Integer
  [E]Integer
               # -->iconst_Integer
  [S]Integer
  [E]Integer
               # -->iconst_Integer
  [S]Integer
  [E]Integer
               # -->iconst_Integer
 [E]Add
               # -->iadd
[E]Start
               # -->invoke static
Thank you.

これは、算術演算のノードが「繰り返し全体」「子要素＝1以上」と定義されているためです。
繰り返し１つにつき１ノードにし、子要素を常に2つ持つようにします。

  • eg4.jjtの抜粋

( MultiplicativeExpression() ( ( "+" | "-" ) MultiplicativeExpression() )* ) #Add(>1)
↓
( MultiplicativeExpression() ( ( "+" | "-" ) MultiplicativeExpression() #Add(2) )* )

Reading from standard input...
1 + 2 + 3;
[S]Start
 [S]Add
  [S]Add
   [S]Integer
   [E]Integer
               # -->iconst_Integer
   [S]Integer
   [E]Integer
               # -->iconst_Integer
  [E]Add
               # -->iadd
  [S]Integer
  [E]Integer
               # -->iconst_Integer
 [E]Add
               # -->iadd
[E]Start
               # -->invoke static
Thank you.

iaddが2回出力されるようになりました。

JJTree版CalcGen

まとめとして、前回作成したCalcGenをJJTreeで再構築してみました。
前回と比べて、

  • スペース区切りでなくてもOK
  • カッコ優先が使える

となっています。

  • calcgen.jjt
options {
  STATIC=false;
  MULTI=true;
  VISITOR=true;
  NODE_DEFAULT_VOID=true;
  NODE_PREFIX="Calc";
}

PARSER_BEGIN(CalcGen)

import java.io.*;

/** Calc Generator. */
public final class CalcGen {

    public static void main(String[] args) throws Exception {
        if (args.length > 0) {
            StringBuilder buffer = new StringBuilder();
            for (final String arg : args) {
                buffer.append(' ');
                buffer.append(arg);
            }
            final String exp = buffer.toString().replace("x", "*");
            CalcGen t = new CalcGen(new StringReader(exp + ";"));
            t.Start().jjtAccept(new CalcGenVisitorImpl(exp), null);
        }
    }

}

PARSER_END(CalcGen)


SKIP : { " " | "\t" | "\n" | "\r" }

TOKEN : { < INTEGER_LITERAL: ( ["1"-"9"] (["0"-"9"])* ) | "0" > }

TOKEN : { < IDENTIFIER: ["a"-"e"] > }

TOKEN : { < ADD: ( "+" | "-" ) > }

TOKEN : { < MUL: ( "*" | "/" | "%" ) > }

CalcStart Start() #Start : {} { Expression() ";" { return jjtThis; } }

void Expression() : {} { AdditiveExpression() }

void AdditiveExpression() : { Token t; }
{ MultiplicativeExpression() ( t=<ADD> MultiplicativeExpression() #Add(2) { jjtn001.jjtSetValue(t.image); } )* } 

void MultiplicativeExpression() : { Token t; }
{ UnaryExpression() ( t=<MUL> UnaryExpression() #Mult(2) { jjtn001.jjtSetValue(t.image); } )* }

void UnaryExpression() : {}
{ "(" Expression() ")" | Identifier() | Integer() }

void Identifier() #Identifier : { Token t; }
{ t=<IDENTIFIER> { jjtThis.jjtSetValue(t.image); } }

void Integer() #Integer : { Token t; }
{ t=<INTEGER_LITERAL> { jjtThis.jjtSetValue(t.image); } }
  • CalcGenVisitorImpl.java
import static org.apache.bcel.Constants.INVOKEVIRTUAL;
import static org.apache.bcel.generic.InstructionConstants.*;

import java.io.*;

import org.apache.bcel.*;
import org.apache.bcel.classfile.*;
import org.apache.bcel.generic.*;

public class CalcGenVisitorImpl implements CalcGenVisitor {

    static final String CLASS_NAME = "Calc";

    final String exp;

    ClassGen cg;
    Method mainMethod;
    MethodGen mg;
    InstructionList il;
    InstructionFactory factory;

    CalcGenVisitorImpl(String exp) {
        this.exp = exp;
    }

    void onBegin() {
        System.out.println("*** CalcGen START ***");
        cg = new ClassGen(getBaseClass());
        cg.setClassName(CLASS_NAME);
        mainMethod = cg.containsMethod("main", "([Ljava/lang/String;)V");
        factory = new InstructionFactory(cg);
        // method: public static void main(String[] args)
        mg = new MethodGen(mainMethod, CLASS_NAME, cg.getConstantPool());
        il = mg.getInstructionList();
        // parse
        try {
            il.delete(il.getEnd());
        } catch (TargetLostException ex) {
            // ignore
        }
        il.append(factory.createGetStatic(System.class.getName(),
                                          "out",
                                          Type.getType(PrintStream.class)));
        il.append(DUP);
        il.append(factory.createConstant("  " + exp + " = "));
        il.append(factory.createInvoke(java.io.PrintStream.class.getName(),
                                       "print",
                                       Type.VOID,
                                       new Type[]{Type.STRING},
                                       INVOKEVIRTUAL));
    }

    void onEnd() {
        il.append(factory.createInvoke(java.io.PrintStream.class.getName(),
                                       "println",
                                       Type.VOID,
                                       new Type[]{Type.INT},
                                       INVOKEVIRTUAL));
        il.append(RETURN);
        // end of instructions
        mg.setMaxStack();
        mg.setMaxLocals();
        cg.replaceMethod(mainMethod, mg.getMethod());
        // generate
        JavaClass c = cg.getJavaClass();
        c.setSourceFileName(CLASS_NAME + ".java");
        try {
            c.dump(CLASS_NAME + ".class");
        } catch (IOException ex) {
            throw new RuntimeException("compile error", ex);
        }
        System.out.println("*** CalcGen END ***");
    }

    @Override
    public Object visit(SimpleNode node, Object data) {
        throw new AssertionError("compile error: unexpected token " + node);
    }

    @Override
    public Object visit(CalcStart node, Object data) {
        onBegin();
        data = node.childrenAccept(this, data);
        onEnd();
        return data;
    }

    @Override
    public Object visit(CalcInteger node, Object data) {
        data = node.childrenAccept(this, data);
        final String value = (String)node.jjtGetValue();
        System.out.printf("  %s --> (constant %s)%n", p(node), value);
        il.append(factory.createConstant(Integer.valueOf(value)));
        return data;
    }

    @Override
    public Object visit(CalcIdentifier node, Object data) {
        data = node.childrenAccept(this, data);
        final int index = " abcde".indexOf((String)node.jjtGetValue());
        System.out.printf("  %s --> iload_%s%n", p(node), index);
        il.append(InstructionFactory.createLoad(Type.INT, index));
        return data;
    }

    @Override
    public Object visit(CalcAdd node, Object data) {
        final String op = String.valueOf(node.jjtGetValue());
        return createBinaryOperation(op, op + "(iadd/isub)", node, data);
    }

    @Override
    public Object visit(CalcMult node, Object data) {
        final String op = String.valueOf(node.jjtGetValue());
        return createBinaryOperation(op, op + "(imul/idiv/irem)", node, data);
    }

    Object createBinaryOperation(String op, String code, SimpleNode node, Object data) {
        data = node.childrenAccept(this, data);
        System.out.printf("  %s --> %s%n", node, code);
        il.append(InstructionFactory.createBinaryOperation(op, Type.INT));
        return data;
    }

    static String p(SimpleNode node) {
        return String.format("%s %s", node, node.value);
    }

    static JavaClass getBaseClass() {
        try {
            return Repository.lookupClass(CalcBase.class);
        } catch (ClassNotFoundException ex) {
            throw new RuntimeException(ex);
        }
    }

}

final class CalcBase {

    @SuppressWarnings("unused")
    public static void main(String[] args) {
        System.out.println("*** Calc ***");
        final int a;
        final int b;
        final int c;
        final int d;
        final int e;
        int[] iargs = new int[5];
        {
            int i = 0;
            for (String arg : args) {
                if (arg.matches("\\d+")) {
                    iargs[i++] = Integer.parseInt(arg);
                }
            }
            i = 0;
            for (final int v : iargs) {
                if (i != 0)
                    System.out.print(',');
                System.out.printf("  %s=%d", (char)('a' + i), v);
                ++i;
            }
            System.out.println();
        }
        a = iargs[0];
        b = iargs[1];
        c = iargs[2];
        d = iargs[3];
        e = iargs[4];
    }

}


動かしてみます。

$ ls
calcgen.jjt  CalcGenVisitorImpl.java
$ jjtree calcgen.jjt 
Java Compiler Compiler Version 5.0 (Tree Builder)
(type "jjtree" with no arguments for help)
Reading from file calcgen.jjt . . .
File "Node.java" does not exist.  Will create one.
File "SimpleNode.java" does not exist.  Will create one.
File "CalcStart.java" does not exist.  Will create one.
File "CalcAdd.java" does not exist.  Will create one.
File "CalcSub.java" does not exist.  Will create one.
File "CalcMult.java" does not exist.  Will create one.
File "CalcDiv.java" does not exist.  Will create one.
File "CalcIdentifier.java" does not exist.  Will create one.
File "CalcInteger.java" does not exist.  Will create one.
File "CalcGenTreeConstants.java" does not exist.  Will create one.
File "CalcGenVisitor.java" does not exist.  Will create one.
File "JJTCalcGenState.java" does not exist.  Will create one.
Annotated grammar generated successfully in .\calcgen.jj
$ javacc calcgen.jj
Java Compiler Compiler Version 5.0 (Parser Generator)
(type "javacc" with no arguments for help)
Reading from file calcgen.jj . . .
File "TokenMgrError.java" does not exist.  Will create one.
File "ParseException.java" does not exist.  Will create one.
File "Token.java" does not exist.  Will create one.
File "SimpleCharStream.java" does not exist.  Will create one.
Parser generated successfully.
$ printenv CLASSPATH  # ※Cygwinです
bin;lib/bcel-5.2.jar;./
$ javac *.java
$ java CalcGen "(1 +2)x3 + a / b"
*** CalcGen START ***
  Integer 1 --> (constant 1)
  Integer 2 --> (constant 2)
  Add --> +(iadd/isub)
  Integer 3 --> (constant 3)
  Mult --> *(imul/idiv/irem)
  Identifier a --> iload_1
  Identifier b --> iload_2
  Mult --> /(imul/idiv/irem)
  Add --> +(iadd/isub)
*** CalcGen END ***
$ java Calc 6 2 0 0 0
*** Calc ***
  a=6,  b=2,  c=0,  d=0,  e=0
   (1 +2)*3 + a / b = 12
$ java CalcGen "a + b + c x d"
*** CalcGen START ***
  Identifier a --> iload_1
  Identifier b --> iload_2
  Add --> +(iadd/isub)
  Identifier c --> iload_3
  Identifier d --> iload_4
  Mult --> *(imul/idiv/irem)
  Add --> +(iadd/isub)
*** CalcGen END ***
$ java Calc 1 2 3 4 5
*** Calc ***
  a=1,  b=2,  c=3,  d=4,  e=5
   a + b + c * d = 15
$ java Calc 4 3 2 1 0
*** Calc ***
  a=4,  b=3,  c=2,  d=1,  e=0
   a + b + c * d = 9
$

ちゃんと計算できていますね。

これでプログラム（と言ってもまだ四則演算機能しかありませんが）からJavaCC(JJTree)+BCELを使ってクラスファイルを生成する仕組みが準備できました。


次回は、もう少しプログラミング言語っぽいものを作っていきます。