エスキュービズム ラボ Blog

データ言語やクエリ言語など、自作の言語を作りたいと考える場合もあるかと思います。自作言語を実装するためには、少なくとも文字列を解釈してなんらかの処理を行う必要があります。そういった処理を行うプログラムのことを言語処理系といいます。言語処理系にはテキストファイルを実行可能形式に変換するコンパイラや、テキストファイルを解釈してその場で実行するインタプリタなどがあります。

今回は数式を解釈して実行する、数式インタプリタ（電卓）を作ってみましょう。

そのまえに言語文法の表記法について触れましょう。下の文を見てください。

• 私はりんごを食べた。
• あなたはバナナを買った。
• 私はりんごとバナナを買った。

上記の文には構造的な共通点がありそうです。私、あなたといった主語があり、次にりんご、バナナといった目的語がきます。最後に買った、食べたといった述語が入っています。

このパターンを表現するために、拡張バッカスナウア記法(EBNF(Wikipedia内):http://ja.wikipedia.org/wiki/EBNF)を使うことができます。上記の文をすべて表現できる、EBNFの一例を示すとこのようになります。

*は０回以上の繰り返し、| はいずれかの選択、[]はあってもなくても良いことを示します。

文が主語・述語・目的語などと、それらをつなぐ言葉から構成されることを示しています。主語・述語・目的語はそれぞれ数種類からの選択ができたり、りんごとばなな、のような指定もできるようになっています。

処理系で″私はりんごを食べた。”を処理するとしたら、どうなるでしょうか。

処理は”私”を読み込んで「文」の処理ははじめ、すぐに「主語」の処理に移ります。”私”までで主語を完成できたので、「文」に戻ります。「文」の処理では”私は”までを読み終えたあと、”私はり”以降述語の処理へと移っていきます。

このようにして、「文」の処理が終わるのはすべての部品が処理された後です。小さな部品から先に処理され、組み立てられていく、と考えるとイメージしやすくなるかも？

（注：実際には部品同士の上下関係は循環するので、あまり正確な表現ではないです）

プログラミング的な言葉を使うと、「文」「主語」などを関数に見立てて、複数関数での再帰呼び出しで木探索を行う、といった感じの処理です。

さて、電卓を示すにはどうすればよいでしょう。

たとえば、1+1を処理する際には足し算をする前に数字を先に処理します。1+2*3は掛け算(2*3)が優先的に計算されます。また、(1+2)*3では括弧の中が先に計算されます。

これらの条件を構文で表現するために、優先順位の低い足し算をより大きな部品として、優先順位の高いかっこや数字を小さな部品として扱います。

実際に書くとこのようになります。

数字Numは0か、先頭が0でない0から9の文字列です。

これで文法を定義できました。

実際に動くプログラムにするため、コンパイラコンパイラとよばれる、言語処理系の開発に特化したコンパイラを使用してみましょう。この記事では、Javaによるコンパイラコンパイラ実装であるJavaCCを使います。

JavaCC:https://javacc.dev.java.net/

Downloadsからを取得して適当なフォルダに展開してください。

展開したフォルダのbinフォルダにパスを通せばjavaccコマンドを利用できるようになります。

ところで、上記のEBNF表記上は特に区別されていませんが、一般に、言語処理系は字句解析と構文解析とよばれる処理ににわけてソースコードを解析します。

字句解析は構文解析の準備処理です。まず入力された文字列を空白文字や特定の記号などで区切っていきます。区切られたそれぞれの文字列を「トークン」と呼びます。そして、それぞれのトークンをあらかじめ決めてあるプログラムの構成部品（class,forなどの予約語や変数名、演算子など）の、どれに該当するかを文字列パターンマッチングで決めます。たとえば、Ｃ言語で型名の”int”と変数名”x”などの分類は、この段階で行われます。

というのも、数字や変数名（識別子）などのパターンをいちいち構文解析していては、処理が複雑になります。12345という数字をそれぞれの桁でわけて扱っても意味はありませんよね。そこで、数字や変数名（識別子）などはそのままひとつのトークンとして扱うようにするのが一般的です。

今回の電卓プログラムでは、数字をしめすNum, D, DNZなどの扱いは字句解析に任せることにしましょう。

以上を踏まえて、先ほどの文法定義をJavaCCファイルに書き写してみましょう。

PARSER_BEGIN(Calc)
public class Calc{
	public static void main(String[] arg) throws Exception{
		Calc calc = new Calc(System.in);
		calc.CompilationUnit();
	}
}

PARSER_END(Calc)
SKIP : {
 ” ”
}

TOKEN:{
 <Num:<DNZ>(<D>)* | <ZERO>>
|<#D: ["0"-"9"]>
|<#DNZ:["1"-"9"]>
|<#ZERO:["0"]>
|<NL:”\n” | “\r”>
}

TOKEN:{
 <PLUS:”+”>
|<MINUS:”-”>
|<MULTI:”*”>
|<DIV:”/”>
|<LPAREN:”(”>
|<RPAREN:”)”>
}

void CompilationUnit():{}{
    Exp()<NL>
}

void Exp():{}{
	MulExp()[("+"|"-")MulExp()]
}

void MulExp():{}{
	Primary()[("*"|"/")Primary()]
}

void Primary():{}{
	<Num> | “(” Exp() “)”
}

calc.jj

PARSER_BEGIN~PARSER_ENDまではとりあえず読み飛ばしてください。

SKIP:{}はコンパイラが無視する文字列パターンです。また、トークンの区切りとしても使われます。

TOKEN:{…}で字句解析に使うトークンを指示します。電卓では+,*などの演算子と、数字を定義してあります。書き方は、<トークン名:パターン>です。また、それぞれのトークン定義は、|で区切って羅列します。

続いて、Exp, MulExpなどを定義してあります。構文の書き方は、型名 構文名(引数リスト):{初期化内容…}{構文定義…}です。

どことなく関数定義に似ていますよね。実際、関数と同じように引数・戻り値の受け渡しが可能です。

このファイルをcalc.jjとして保存してコンパイルします。

>javacc calc.jj

生成されるJavaファイルをコンパイル

>javac *.java

実行

>java Calc

>1+2

(表示なし)

>java Calc

>1++2

(エラー表示)

さて、このままではこのプログラムは文法チェック以外なにもできません。次はアクションを追加して、実際に数値を処理してみましょう。

PARSER_BEGIN(Calc)
public class Calc{
	public static void main(String[] arg) throws Exception{
		Calc calc = new Calc(System.in);
		calc.CompilationUnit();
	}
}

PARSER_END(Calc)
SKIP : {
 ” ”
}

TOKEN:{
 <Num:<DNZ>(<D>)* | <ZERO>>
|<#D: ["0"-"9"]>
|<#DNZ:["1"-"9"]>
|<#ZERO:["0"]>
|<NL:”\n” | “\r”>
}

TOKEN:{
 <PLUS:”+”>
|<MINUS:”-”>
|<MULTI:”*”>
|<DIV:”/”>
|<LPAREN:”(”>
|<RPAREN:”)”>
}

void CompilationUnit():{
    int i;
}{
    i=Exp()<NL>
    {
        System.out.println(i);
    }
}

int Exp():{
    boolean plus=true;
    int l=0, r=0;
}{
	l=MulExp()[("+"|"-"{plus=false;})r=MulExp()]
    {
        return plus? l+r : l-r;
    }
}

int MulExp():{
    boolean mul=true;
    int l=1, r=1;
}{
	l=Primary()[("*"|"/"{mul=false;})r=Primary()]
    {
        return mul? l*r : l/r;
    }
}

int Primary():{
    Token t=null;
    int ret;
}{
	(t=<Num>{ret = Integer.parseInt(t.image);} | “(” ret=Exp() “)”)
    {
        return ret;
    }
}

calc.jj(アクション追加版)

JavaCCプログラムにアクションを追加するには、{}の中にJavaで処理内容を記述します。アクションは、構文解析の処理の流れがその位置を通過したとき、実行されます。

Primaryを例にとると、<Num>の右側に{}処理が記述されています。処理の流れが<Num>の側に来たときのみ、ret=Integer.parseInt(t.image);が実行されます。

また、処理実行後の戻り値は=で変数に格納することができます。なお、字句として定義した部分（今回は数字や演算子）は、JavaCC組み込みのToken型オブジェクトとして受け取ることができます。ここでは出現した文字をそのまま受け取るimageフィールドにアクセスしています。Token型オブジェクトの詳細については自動生成されるToken.javaを参照されるとよいでしょう。

先ほどと同様に、コンパイル・実行してみましょう。

>javacc calc.jj

生成されるJavaファイルをコンパイル

>javac *.java

実行

>java Calc

>1+2*3

7

>java Calc

>(1+2)*3

9

長々と書いてまいりましたがようやく完成です！

今回の例では数式-1+1などは表現できません。負の整数を定義していないためです。興味のある方はサンプルソースを変更して、負の整数を定義してみてください。