« 「更新系」はどこへ? | トップページ | ソフトウエア工学とは何ぞや »

2009年2月21日 (土)

JJTree 構文木を作るツール

コンパイラ・コンパイラが、構文木まで作ってくれれば良いのに、と前々から思っていたのですが。そういうツールが、ちゃんと存在しているのですね。

JJTree is a preprocessor for JavaCC (tm) that inserts parse tree building actions at various places in the JavaCC source. The output of JJTree is run through JavaCC to create the parser.

JavaCC (tm): JJTree Reference Documentation

おなじみの「電卓」の例は、こんな感じです。

>java Calc
1+2*3-4/5
CalcExpr
 AddExpr:+,-
  Literal:1
  MulExpr:*
   Literal:2
   Literal:3
  MulExpr:/
   Literal:4
   Literal:5

構文生成規則は、以下のように入力します。

/* Calc.jjt */
options {
  STATIC=false;
  MULTI=true;
}

PARSER_BEGIN(Calc)
public class Calc {
  public static void main(String args[])
    throws ParseException {

    while (true) {
      Calc parser = new Calc(System.in);
      if (parser.CalcExpr() == 1) {
        ((SimpleNode)parser.jjtree.rootNode()).dump("");
      }
    }
  }
}
PARSER_END(Calc)

SKIP:
{
  " "|"\r"
}

TOKEN :
{
    < ADDOP  : "+" >
   |< SUBOP  : "-" >
   |< MULOP  : "*" >
   |< DIVOP  : "/" >
   |< LP     : "(" >
   |< RP     : ")" >
   |< LITERAL: (["0"-"9"])+ >
   |< NL     : "\n" >
}

int CalcExpr() :
{ }
{
      AddExpr() <NL>
        { return 1; }
     | <NL>
        { return 0; }
     | <EOF>
        { return -1; }
}

void AddExpr() #void :
{ Token t;
  int i = 0;
}
{
    (
      MulExpr() (
        (t=<ADDOP>|t=<SUBOP>)
          { jjtThis.addValue(t.image); }
        MulExpr())*
    ) #AddExpr(>1)
}

void MulExpr() #void :
{ Token t;
  int i = 0;
}
{
    (
      PrmExpr() (
        (t=<MULOP>|t=<DIVOP>)
          { jjtThis.addValue(t.image); }
        PrmExpr() )*
    ) #MulExpr(>1)
}

void PrmExpr() #void :
{ }
{
      Literal()
    | <LP> AddExpr() <RP>
}

void Literal() :
{ Token t; }
{
    t=<LITERAL>
      { jjtThis.addValue(t.image); }
}

Ant ビルドファイル build.xml は、以下のとおり。

<?xml version='1.0' encoding='utf-8' ?>

<project name="calc" default="build" basedir=".">

  <property name="javacc.home" value="/path/to/javacc"/>

<target name="clean">
  <delete>
    <fileset dir="src">
      <include name="ASTAddExpr.java"/>
      <include name="ASTCalcExpr.java"/>
      <include name="ASTLiteral.java"/>
      <include name="ASTMulExpr.java"/>
      <include name="Calc.java"/>
      <include name="Calc.jj"/>
      <include name="CalcConstants.java"/>
      <include name="CalcTokenManager.java"/>
      <include name="CalcTreeConstants.java"/>
      <include name="JJTCalcState.java"/>
      <include name="Node.java"/>
      <include name="ParseException.java"/>
      <include name="SimpleCharStream.java"/>
      <include name="SimpleNode.java"/>
      <include name="Token.java"/>
      <include name="TokenMgrError.java"/>
    </fileset>
  </delete>
</target>

  <target name="jjtree-gen">
    <exec dir="."
      failonerror="true" executable="cmd" >
      <arg value="/C" />
      <arg value="jjtree -OUTPUT_DIRECTORY:src -NODE_CLASS:CalcNode src/Calc.jjt" />
    </exec>
  </target>

  <target name="javacc-gen">
    <javacc target="src/Calc.jj" outputdirectory="src"
      javacchome="${javacc.home}"/>
  </target>

  <target name="compile">
    <delete dir="bin"/>
    <mkdir dir="bin"/>
    <javac srcdir="src" destdir="bin">
    </javac>
  </target>

  <target name="build" depends="clean,jjtree-gen,javacc-gen,compile">
  </target>

</project>

JJTree のオプションで、 -NODE_CLASS:CalcNode として、構文木のノードを指定しています。

/* CalcNode.java */
import java.util.ArrayList;

public class CalcNode extends SimpleNode {

  ArrayList<Object> valueList = new ArrayList<Object>();

  public CalcNode(int i) {
    super(i);
  }

  public CalcNode(Calc p, int i) {
    super(p, i);
  }

  public void addValue(Object value) {
    valueList.add(value);
  }

  public String toString() {
    StringBuilder sb = new StringBuilder(super.toString());
    int i = 0;
    for (Object value : valueList) {
      if (i == 0) {
        sb.append(':');
      } else {
        sb.append(',');
      }
      sb.append(value);
      i++;
    }
    return sb.toString();
  }
}

|

« 「更新系」はどこへ? | トップページ | ソフトウエア工学とは何ぞや »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/80472/28276775

この記事へのトラックバック一覧です: JJTree 構文木を作るツール:

« 「更新系」はどこへ? | トップページ | ソフトウエア工学とは何ぞや »