Ninaチュートリアル

チュートリアルTOP - PREV: サブオートマトンの使用

Ninaによる実用的なプログラミング

電卓の実装

Ninaによる開発の実例の手始めとして、メモリ機能の付いた電卓を作成してみたいと思います。 ソースが若干長いので、いくつかに分割して説明したいと思います。
最初はこのプログラムがどのようなものかを表すコメントをつけます。

--------------------------
a calculator

@author Author
--------------------------

宣言部です。Javaで記述することとメモリ(今回は英文字から始まる英数字の並びとします)と メモリが代入文であることを先読みするための正規表現を定義します。 ラベルには正規表現を使用することができます。正規表現の先頭に"?="を付加することで 入力を消費せずにマッチを進める「先読み」をすることができます。

#machine DFABuilder
#option targetLanguage=Java
#label VAR=/[A-Za-z][A-Za-z0-9]*/
#label LAHEADVAR=/?=[A-Za-z][A-Za-z0-9]*[ ¥t]*=/

Javaのimport文は%{…%}の中に記述します。

%{
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
%}

プログラムの開始です。開始は文のリスト(stmtlist)を呼び出して受理します。

 @S@@@@@@@@            @@@@@@@@@@@
 @        >-{stmtlist}->         @
 @@@@@@@@@@            @@@@@@@@@@@

文のリストです。文を呼び出してスタックマシン方式の仮想機械にコンパイルされた式を実行します。 実行後は仮想機械をクリアし、改行コードを消費して再び文を呼び出します。

-- stmtlist --
         +--'¥n'----+
 @S@@@@@@v@        @^@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 @        >-{stmt}->exec(); instructions.clear();@
 @v@@@@@@^@        @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  +-'¥n'-+

文です。先読み機能を用いてメモリ変数と等号(=)があるかを調べ、あるときには変数名を記憶して式を呼び出し、 結果をメモリに代入します。状態にデータを保存することができます。 データの定義は状態を囲う"*"または"@"の上の2文字目から "状態名<状態の型>"(ここではV)として記述します。 データを他の状態から参照するには"$状態名"のようにします。 先読みにマッチしないときは式を解析し、表示する命令を追加します。

-- stmt --
                                                           +-[ ¥t]-+
 *S*                ***        *V<String>**************** *^*******v*
 * >-+-${LAHEADVAR}-> >-${VAR}->%% = $buffer.toString();>->         *
 *** |              ***        ************************** *v*********
     |                                 +--------'='--------+
     |        @@@@@@@@@@              *v*********        @@@@@@@@@@@@
     +-{expr}->print();@              *         >-{expr}->asgn($V); @
              @@@@@@@@@@              *v*******^*        @@@@@@@@@@@@
                                       +-[ ¥t]-+

式の先頭です。まず因子を解析し、'+'か'-'を受けます。'+'のときはまた因子を解析し、 スタックに積んだ数を足す命令を追加します。'-'のときも因子を解析し、 スタックに積んだ数を引く命令を追加します。 以下の記述方法はNinaにおいて左結合の演算子を実現するための「イディオム」として現れます。

-- expr --
               +-[ ¥t]-+         +-[ ¥t]-+
 *S*        @A@^@@@@@@@v@       *^*******v*        @@@@@@@@@@
 * >-{fact}->           >-+-'+'->         >-{fact}->add();  >-(A)
 ***        @@@@@@@@@@@@@ |     ***********        @@@@@@@@@@
                          |      +-[ ¥t]-+
                          |     *^*******v*        @@@@@@@@@@
                          +-'-'->         >-{fact}->sub();  >-(A)
                                ***********        @@@@@@@@@@

因子です。まずべき乗を解析し、'*'か'/'を受けます。'*'のときはまたべき乗を解析し、 スタックに積んだ数をかける命令を追加します。 '/'のときも因子を解析し、スタックに積んだ数を割る命令を追加します。

-- fact --
                +-[ ¥t]-+         +-[ ¥t]-+
 *S*         @A@^@@@@@@@v@       *^*******v*         @@@@@@@@@@
 * >-{power}->           >-+-'*'->         >-{power}->mul();  >-(A)
 ***         @@@@@@@@@@@@@ |     ***********         @@@@@@@@@@
                           |      +-[ ¥t]-+
                           |     *^*******v*         @@@@@@@@@@
                           +-'/'->         >-{power}->div();  >-(A)
                                 ***********         @@@@@@@@@@

べき乗です。まず単項演算を解析し、'^'を受けます。'^'のときは自分自身を再帰的に呼び出し、 受理したらべき乗する命令を追加します。 以下の記述方法はNinaにおいて右結合の演算子を実現するための「イディオム」として現れます。

-- power --
              +-[ ¥t]-+
 *S*         @^@@@@@@@v@     ***         @@@@@@@@
 * >-{unary}->         >-'^'-> >-{power}->pow();@
 ***         @@@@@@@@@@@     ***         @@@@@@@@

単項演算です。入力に'-'があるときは要素を消費して符号を反転する命令を追加します。 そうでないときは、単純に符号を反転する命令を追加します。 サブオートマトンを呼び出す処理は入力に対応する編がないときに実行されます。

-- unary --
    +-[ ¥t]-+         +-[ ¥t]-+
 *S*^*******v*       *^*******v*        @@@@@@@@@@@
 *           >-+-'-'->         >-{elem}->uminus();@
 ************* |     ***********        @@@@@@@@@@@
               |
               |        @@@@@@@@@@@
               +-{elem}->         @
                        @@@@@@@@@@@

要素です。浮動小数点数にマッチするときはその結果を定数として命令に追加します。 "{%f}"で浮動小数点数にマッチすることができ、その結果は$numに保存されます。 '('にマッチするときは式の先頭を呼び出し、受理したのちの入力に')'が来れば受理します。 メモリ変数が来たときはメモリ変数を参照する命令を追加します。

-- elem --
    +-[ ¥t]-+
 *S*^*******v*        @@@@@@@@@@@@@@
 *           >-+-{%f}->konst($num);@
 ************* |      @@@@@@@@@@@@@@
               |
               |     ***        ***     @@@
               +-'('-> >-{expr}-> >-')'-> @
               |     ***        ***     @@@
               |
               |        @@@@@@@@@@@@@@@@@@@@@@@@@@@@
               +-${VAR}->refer($buffer.toString());@
                        @@@@@@@@@@@@@@@@@@@@@@@@@@@@

これからは補助プログラム部です。まず、命令とメモリを保持する環境のインターフェースを定義します。

%%
static interface Exec {
	public int exec(Code code, Stack<Double> stack, Env env);
}

static interface Env {
	public void bind(String name, double val);
	public Double find(String name);
}

命令に対応する処理を定義します。 定数、四則演算、べき乗、代入、メモリ参照、表示に対応する命令セットが定義されています。

static enum Inst {
	KONST(new Exec() {
		public int exec(Code code, Stack<Double> stack, Env env) {
			stack.push(code.number);
			return -1;
		}
	}),
	ADD(new Exec() {
		public int exec(Code code, Stack<Double> stack, Env env) {
			double b = stack.pop();
			double a = stack.pop();
			stack.push(a + b);
			return -1;
		}
	}),
	SUB(new Exec() {
		public int exec(Code code, Stack<Double> stack, Env env) {
			double b = stack.pop();
			double a = stack.pop();
			stack.push(a - b);
			return -1;
		}
	}),
	MUL(new Exec() {
		public int exec(Code code, Stack<Double> stack, Env env) {
			double b = stack.pop();
			double a = stack.pop();
			stack.push(a * b);
			return -1;
		}
	}),
	DIV(new Exec() {
		public int exec(Code code, Stack<Double> stack, Env env) {
			double b = stack.pop();
			double a = stack.pop();
			stack.push(a / b);
			return -1;
		}
	}),
	POW(new Exec() {
		public int exec(Code code, Stack<Double> stack, Env env) {
			double b = stack.pop();
			double a = stack.pop();
			stack.push(Math.pow(a, b));
			return -1;
		}
	}),
	ASGN(new Exec() {
		public int exec(Code code, Stack<Double> stack, Env env) {
			env.bind(code.symbol, stack.pop());
			return -1;
		}
	}),
	REFER(new Exec() {
		public int exec(Code code, Stack<Double> stack, Env env) {
			Double val = env.find(code.symbol);
			stack.push(val != null ? val : 0);
			return -1;
		}
	}),
	UMINUS(new Exec() {
		public int exec(Code code, Stack<Double> stack, Env env) {
			double a = stack.pop();
			stack.push(-a);
			return -1;
		}
	}),
	PRINT(new Exec() {
		public int exec(Code code, Stack<Double> stack, Env env) {
			System.out.printf("¥t%f¥n", stack.pop());
			return -1;
		}
	});

	private Exec execCode;
	Inst(Exec e) {
		execCode = e;
	}
	int exec(Code code, Stack<Double> stack, Env env) {
		return execCode.exec(code, stack, env);
	}
}

命令の1インストラクションを表すクラスを定義します。命令セットと数またはメモリ変数名から構成されます。

static class Code {
	Inst inst;
	Double number;
	String symbol;

	Code(Inst inst, Double number) {
		this.inst = inst;
		this.number = number;
	}

	Code(Inst inst, String symbol) {
		this.inst = inst;
		this.symbol = symbol;
	}

	Code(Inst inst) {
		this(inst, 0.0);
	}
}

メモリ変数を保持する環境の実装を定義します。

static class EnvAlter2 implements Env {
	private Map<String, Double> env = new HashMap<String, Double>();

	public void bind(String symbol, double val) {
		env.put(symbol, val);
	}

	public Double find(String symbol) {
		return env.get(symbol);
	}
}

命令とメモリ変数の空間を定義します。

ArrayList<Code> instructions = new ArrayList<Code>();
Env global = new EnvAlter2();

Ninaパーサから呼び出され、命令を登録する処理を定義します。 Ninaパーサにかける内容は少ないので、長い処理は補助プログラム部に記述することを推奨します。

private void konst(Number num) {
	instructions.add(new Code(Inst.KONST, num.doubleValue()));
}

private void add() {
	instructions.add(new Code(Inst.ADD));
}

private void sub() {
	instructions.add(new Code(Inst.SUB));
}

private void mul() {
	instructions.add(new Code(Inst.MUL));
}

private void div() {
	instructions.add(new Code(Inst.DIV));
}

private void pow() {
	instructions.add(new Code(Inst.POW));
}

private void uminus() {
	instructions.add(new Code(Inst.UMINUS));
}

private void asgn(String symbol) {
	instructions.add(new Code(Inst.ASGN, symbol));
}

private void refer(String symbol) {
	instructions.add(new Code(Inst.REFER, symbol));
}

private void print() {
	instructions.add(new Code(Inst.PRINT));
}

命令セットを実行します。

private void exec() {
	Stack<Double> stack = new Stack<Double>();
	int pc = 0;

	while(pc < instructions.size()) {
		Code code = instructions.get(pc);
		int ret = code.inst.exec(code, stack, global);
		pc = ret < 0 ? pc + 1 : ret;
	}
}

メイン処理です。単にパーサを呼び出します。

public static void main(String[] args) throws Exception {
	parseAll(System.in);
}

チュートリアルTOP - PREV: サブオートマトンの使用
Yuichiro Moriguchi
yuichiro-moriguchi@nifty.com
SourceForge.JP