Ninaチュートリアル

チュートリアルTOP - PREV: Ninaによる実用的なプログラミング - NEXT: Ninaによる実用的なプログラミング

サブオートマトンの使用

漢数字の解析

通常のプログラミング言語がサブルーチンを使用できるのと同様に、 Ninaでもオートマトンをモジュール化してサブオートマトンを使用できます。
サブオートマトンの実例として漢数字をアラビア数字に変換するプログラムを作成しましょう。
プログラムを以下に示します。

#machine DFABuilder
            +------------------------------------------'万'-(MN)
            +------------------------------------------'億'-(OK)
 *S*       @^@      @@@@@@@@@@@@@@@@@@@@@@@@       @@@
 * >-{sen}-> >-'兆'->d3 += (d2 + d1) * CHO;>-{sen}-> >-'億'-(OK)
 ***       @ @      @d2  = d1 = 0;  dx = 1;@       @ @
           @@@      @@@@@@@@@@@@@@@@@@@@@@@@       @v@
                                                    +--'万'-(MN)
 @OK@@@@@@@@@@@@@@@@@@@@@       @@@      @MN@@@@@@@@@@@@@@@@@@@@@       @@@
 @d3 += (d2 + d1) * OKU;>-{sen}-> >-'万'->d3 += (d2 + d1) * MAN;>-{sen}-> @
 @d2  = d1 = 0;  dx = 1;@       @ @      @d2  = d1 = 0;  dx = 1;@       @ @
 @@@@@@@@@@@@@@@@@@@@@@@@       @@@      @@@@@@@@@@@@@@@@@@@@@@@@       @@@
-- sen --
    +--'十'-(T)
    +--'百'-(H)
    +------------'千'--+                        +-'十'-(T)
 *S*^*       @@@      @v@@@@@@@@@@@@@@@@       @^@
 *   >-{one}-> >-'千'->d2 += dx * 1000;>-{one}-> >-'百'-(H)
 *****       @v@      @d1  = 0;        @       @@@
              |       @dx  = 1;        @
              |       @v@@@@@@@@@@@@@@@@|
              +-百-(H) +---------------------------'百'-(H)
              +-十-(T) +---------------------------'十'-(T)
 @H@@@@@@@@@@@@@@@       @@@      @T@@@@@@@@@@@@@@       @@@
 @d2 += dx * 100;>-{one}-> >-'十'->d2 += dx * 10;>-{one}-> @
 @d1  = 0;       @       @@@      @d1  = 0;      @       @@@
 @dx  = 1;       @                @@@@@@@@@@@@@@@@
 @@@@@@@@@@@@@@@@@
-- one --
 *S*        @@@@@@@@@@@@@@@@@@
 * >-+-'一'->{ d1 = dx = 1; }@
 *** |      @@@@@@@@@@@@@@@@@@  @@@@@@@@@@@@@@@@@@
     +-'二'--------------------->{ d1 = dx = 2; }@
     |      @@@@@@@@@@@@@@@@@@  @@@@@@@@@@@@@@@@@@
     +-'三'->{ d1 = dx = 3; }@
     |      @@@@@@@@@@@@@@@@@@  @@@@@@@@@@@@@@@@@@
     +-'四'--------------------->{ d1 = dx = 4; }@
     |      @@@@@@@@@@@@@@@@@@  @@@@@@@@@@@@@@@@@@
     +-'五'->{ d1 = dx = 5; }@
     |      @@@@@@@@@@@@@@@@@@  @@@@@@@@@@@@@@@@@@
     +-'六'--------------------->{ d1 = dx = 6; }@
     |      @@@@@@@@@@@@@@@@@@  @@@@@@@@@@@@@@@@@@
     +-'七'->{ d1 = dx = 7; }@
     |      @@@@@@@@@@@@@@@@@@  @@@@@@@@@@@@@@@@@@
     +-'八'--------------------->{ d1 = dx = 8; }@
     |      @@@@@@@@@@@@@@@@@@  @@@@@@@@@@@@@@@@@@
     +-'九'->{ d1 = dx = 9; }@
            @@@@@@@@@@@@@@@@@@
%%
private static final long CHO = 1000000000000l;
private static final long OKU = 100000000l;
private static final long MAN = 10000l;

private long d1, d2, d3, dx = 1;

public static long parseNumber(String s) {
	KanjiNumber k = new KanjiNumber();
	java.io.StringReader r;

	r = new java.io.StringReader(s);
	try {
		k.parse(r);
		return k.d3 + k.d2 + k.d1;
	} catch(java.io.IOException e) {
		throw new RuntimeException(e);
	}
}

public static void main(String[] args) {
	java.io.Console rd;
	String s;

	rd = System.console();
	while((s = rd.readLine()) != null) {
		System.out.println(parseNumber(s));
	}
}

このプログラムはメインオートマトンとサブオートマトン"sen"と"one"からなります。 サブオートマトンは、サブオートマトン名を-- --でかこった単一の行で開始されます。
サブオートマトンの呼び出しは、サブオートマトン名を{...}で囲うことで呼び出されます。 DFAの場合、サブオートマトンは他の遷移が無いときに呼び出されます。
コンパイルして実行してみましょう。

$ ninat kanjiNumber.nina
$ javacc KanjiNumber.java
$ java KanjiNumber
七十二
72
七百六十五
765
千七百二十九
1729
(Ctrl-C)

再帰的なサブオートマトン呼び出し

サブオートマトンの再帰的な呼び出しも可能です。 サブオートマトンの再帰呼び出しにより、Ninaの言語解析能力は正規言語を超え、 文脈自由言語のサブクラスを解析する能力を持つことになります。
再帰呼び出しの例として、釣り合いの取れたかっこを解析するプログラムを作成しましょう。
ソースを以下に示します(ファイル名はparen.ninaとしてください)。

#machine DFABuilder
 @S@         @@@
 @ >-{paren}-> @
 @@@         @@@
-- paren --
    +---------------------------+
 @S@v@     ***         ***     @^@
 @   >-'('-> >-{paren}-> >-')'-> @
 @@@@@     ***         ***     @@@
%%
public static void main(String[] args) throws Exception {
	parseAll(System.in);
}

左かっこを認識したときはparen.ninaを再帰的に呼び出した後右かっこを認識して受理します。
遷移文字の無い辺は、次の文字を1文字読み込み、遷移した後その文字を読み戻します。 それにより、DFAで擬似的に空遷移(ε遷移)を実現します。
コンパイルして実行してみましょう。

$ ninat paren.nina
$ javac Paren.java
$ java Paren
(())
$ java Paren
(()
Exception in thread "main" Paren$TokenException
	at Paren.parse(Paren.java:304)
	at Paren.parse(Paren.java:338)
	at Paren.parseAll(Paren.java:344)
	at Paren.parseAll(Paren.java:353)
	at Paren.main(Paren.java:37)
$

チュートリアルTOP - PREV: Ninaによる実用的なプログラミング - NEXT: Ninaによる実用的なプログラミング
Yuichiro Moriguchi
yuichiro-moriguchi@nifty.com
SourceForge.JP