この記事は、Akatsuki Advent Calendarの17日目の記事です。
はじめに
こんにちは。
株式会社アカツキの方でエンジニアをやっておりますfff-nと申します。
この年末年始はC#上で動くプログラミング言語を作ってみようと思ったので、今回はプログラミング言語を作る上での考え方、作り方および実装にあたって便利なツールについて書いてみようと思います。
この記事ではツールの紹介と、とりあえず動く物を作る事の2点に注力しています。
本来はこの手の分野の話題には言語処理関係の知識が必要ですが、この記事ではそれらの解説は行いませんし用語も極力使わないようにしています。
解説するにしてもかなりざっくりとしているので、しっかりとした知識が必要な方は専門のサイトや書籍を読むのがいいと思います。
なぜC#で作るのか
Unityに容易に組み込めるからです。
まあ、実際に作った言語をUnityに組み込むみたいな事はやらないと思います。
実装が複数の言語に跨るとそれだけ管理のコストがかかってしまうので。
ですが、今回の内容はプログラミング言語レベルに複雑な物を作るだけでなく、ちょっとした文法に従って文字列を処理するプログラム（HTMLパーサっぽいものとか）を書くためにも使えるのでやろうと思えばいくらでも応用が効くと思います。
今回作るもの
この記事では「スクリプト（式）を文字列として受け取り、それを評価した結果を出力する」プログラムを作ります。
とても単純なインタプリタの一種になります。
インタプリタとは、超ざっくり説明するとスクリプトを読み込んでその場で実行するプログラムです。
rubyとかがそうですね。
今回実装する機能の範囲についてですが、単純に四則演算ができるまでとします。
それではプログラミング言語とは言えませんね。
というのも、今回の記事の主軸は後述の字句解析と構文解析をC#上でどう楽して作るかに寄せているためです（実際、パフォーマンスとか抜きにすると一番大変なのは文字列処理なので）
なので、入力文字列を解析して計算するところまでできたら後はこの記事の範囲外とします。
では早速作っていきましょう。
インタプリタの考え方
まずインタプリタを作るために、インタプリタが何をしているのかを考えます。
今回作るインタプリタは
- 文字列としてスクリプトを受け取り
- スクリプトの評価結果を出力する
という処理をします。
問題はこの1と2の間にどのような処理が必要となるかです。
「評価結果を出力する」ためには、「スクリプトを評価する」必要があります。
「スクリプトを評価する」ためには、「文字列として渡されたスクリプトを評価が可能な形式に変換する」必要があります。
それでは、「文字列として渡されたスクリプトを評価が可能な形式に変換する」ためにはどのような処理が必要なのでしょうか？
式を評価する
まず、評価が可能な形式とは何かについて考えてみます。
今回実行させたいスクリプトを以下のようにするとします。
1+1
1+1*3
1*(1-1)
まずは1+1に着目します。
素直に計算すると結果は2ですが、これを計算するためにはどのようなプログラムが必要になるかを考えます。
System.Console.WriteLine(1 + 1);とかではないです。数字が変わってもいいような形にする必要があります。
まあぶっちゃけるとデザインパターンの1つ、Interpreterパターンを真似ればいいだけなのですが。
Interpreterパターンの解説はDRY原則に則り別のサイトにお任せするとして、これそのままズバリな名前してますよね。
要はこのような処理を実現するのに適したパターンなのです。
まずは基底インターフェースとなるIExpressionを作ります。
public interface IExpression
{
double Evaluate ();
}
唯一のメソッドEvaluate()は評価するという意味を持ち、そのExpressionを評価した結果を返します。
で、次は数字を表すクラスを作ります。
public class NumberExpression : IExpression
{
private double _num;
public NumberExpression (double num)
{
_num = num;
}
public double Evaluate ()
{
return _num;
}
}
シンプルですね。コンストラクタで渡されたnumをEvaluate()でそのまま返しているだけです。
では次は加算記号を表すクラスを作ります。
public class OpAddExpression : IExpression
{
private IExpression _left;
private IExpression _right;
public OpAddExpression (IExpression left, IExpression right)
{
_left = left;
_right = right;
}
public double Evaluate ()
{
return _left.Evaluate() + _right.Evaluate();
}
}
はい。これもシンプルですね。コンストラクタで2つのIExpressionを受け取り、Evaluate()ではそれらをEvaluate()した結果を足し合わせています。
これで加算演算が表せるわけですね。
では、これらのクラスで1+1の計算をしてみます。
var left = new NumberExpression(1);
var right = new NumberExpression(1);
var opAdd = new OpAddExpression(left, right);
System.Console.WriteLine(opAdd.Evaluate()); // => "2"
このaddOpというものが1+1の評価可能な形であり、このインスタンスのEvaluate()を実行することで1+1の結果が計算できます。
では次の式に行ってみましょう。
次は、1+1*3です。
乗算が出てきましたね。乗算を表すクラスはOpMulExpressionとしましょう。実装は省略します。
1+1*3は次のように表せます。
var addLeft = new NumberExpression(1);
var mulLeft = new NumberExpression(1);
var mulRight = new NumberExpression(3);
var addRight = new OpMulExpression(mulLeft, mulRight);
var opAdd = new OpAddExpression(addLeft, addRight);
System.Console.WriteLine(opAdd.Evaluate()); // => "4"
はい。ちょっとややこしくなってきましたが、opAddのrightがOpMulExpressionのインスタンスとなっています。
OpMulExpressionもIExpressionの実装ですので、NumberExpressionと同様OpAddExpressionのコンストラクタに渡すことができます。
そして、OpMulExpressionのEvaluate()はleftとrightを乗算した結果を返すので、opAdd.Evaluate()は1+1*3を計算することになります。
それでは最後の式に行ってみましょう。
最後は1*(1-1)です。
減算のクラスはOpSubExpressionとしましょう。()については新しくクラスを作る必要はありません。
var mulLeft = new NumberExpression(1);
var subLeft = new NumberExpression(1);
var subRight = new NumberExpression(1);
var mulRight = new OpSubExpression(subLeft, subRight);
var opMul = new OpMulExpression(mulLeft, mulRight);
System.Console.WriteLine(opMul.Evaluate()); // => "0"
このように、()はどのような構造でExpressionを作るかによって対応することができます。
これで評価が可能な形式についてはイメージが掴めたと思います。
では、文字列からどのようにしてこの形に変換すればよいのでしょうか？
字句解析と構文解析
IExpressionインターフェースとそれを実装するクラスを使うことで、式をクラスで表現することができました。
次の課題は、文字列をIExpressionに変換する処理をどう実現するかということになります。
これには明確な解決方法があります。
この問題を解決するキーワードは、字句解析と構文解析です。
これらについて、この記事ではざっくりとしたことしか説明しません。
詳しい解説はDRY原則に則り別のサイトにお任せすることにします。
字句解析は文字列をトークン列と呼ばれる物に変換する処理です。
ざっくりとしたイメージとして、1+1という文字列が渡されたらNUM OP_ADD NUMというトークン列（このNUMとOP_ADDがトークン）を返すものと考えてもらってよいです。
構文解析はこのトークンから文法を読み解く処理です。
NUM OP_ADD NUMというトークン列を受け取ったら、「これは加算演算である」と判定するようなものです。
で、構文解析において「これは加算演算である」ということが分かったら、先程の1+1の時のようにOpAddExpressionのインスタンスを作れば、スクリプトを評価可能な形に変換できるというわけですね。
この字句解析と構文解析ですが、1から全部実装しようとすると大変なので、それぞれツールを使って実装します。
どのくらい大変かについてイメージが掴めない方は、この年末年始にでも字句解析と構文解析のアルゴリズムを一通り学んだ上でぜひ一度実装に取り組んでみるといいと思います。
字句解析機生成ツールre2c
字句解析するプログラムはre2cというツールを使って生成します。
インストールはpacman -S re2cとかbrew install re2cとかすればできますが、公式サイトのドキュメントを読んだほうがいいと思います。
re2cは本来C/C++向けのツールなのですが、生成コードの内容を設定で変更できるためC#でも使えます。
re2cが生成するコードはgotoを多用していますが、C#はgotoをサポートしているので問題ありません。
構文解析機生成ツールjay
構文解析するプログラムはjayというツールを使って生成します。
jayはmonoが使っているC#向けの構文解析機生成ツールで、monoのgitリポジトリにjayのプロジェクトも入っているので、リポジトリをcloneしてプロジェクトをビルドすればjayが使えます。
（makeする場合、事前にmono/mcs/build/platforms/にある.makeファイル群から、自分の環境にあったものを.makeにリネームする必要があります）
構文解析機を作る
それではコードを書いていきます。
まずはjayから使います。
jayはパーサを生成します。Parser.jayというファイルを作り次の内容を書き込みます。
%{
using System;
using SampleLanguage.Expression;
namespace SampleLanguage.Interpreter
{
public class Parser
{
private int yacc_verbose_flag = 0;
%}
%token <string> LP
%token <string> RP
%token <string> OP_ADD
%token <string> OP_SUB
%token <string> OP_MUL
%token <string> OP_DIV
%token <string> OP_DIV
%token <double> NUM
%type <IExpression> Formula
%type <IExpression> Term
%type <IExpression> Num
%left LP RP
%left OP_ADD OP_SUB
%left OP_MUL OP_DIV
%start Sentence
%%
Sentence
: Formula
Formula
: Term
{
$$ = $1;
}
| Formula OP_ADD Term
{
$$ = new OpAddExpression($1, $3);
}
| Formula OP_SUB Term
{
$$ = new OpSubExpression($1, $3);
}
Term
: Num
{
$$ = $1;
}
| Term OP_MUL Num
{
$$ = new OpMulExpression($1, $3);
}
| Term OP_DIV Num
{
$$ = new OpDivExpression($1, $3);
}
Num
: NUM
{
$$ = new NumberExpression($1);
}
| LP Formula RP
{
$$ = $2;
}
%%
}
書き方はなんとなく分かると思います。
使われるトークン、演算子の順序を定義してから、BNF記法チックな書き方で文法を書き連ねていきます。
Num
: NUM
{
$$ = new NumberExpression($1);
}
例えば上記のこの部分はNumはNUMであるという定義をしています。
波括弧の中ではNUMからNumへ還元する際の処理をC#で書きます。
還元という言葉の意味が分からない場合は「文法 還元」あたりで検索するといいと思います。
要はNUMをNumへと置き換えることです。
ここでは、NUMは数値ですのでNumberExpressionをnewしています。
$1というのはトークンの実際の値です。文法の左端から$1,$2 ...という風に参照できます。
ここでは$1はNUMのことであり、NUMは型がdoubleなのでdouble型の値が入ります。
$$はNumの実際の値となります。なので、Numは値としてはNumberExpressionのインスタンスを持つことになります。
Term
...
| Term OP_MUL Num
{
$$ = new OpMulExpression($1, $3);
}
ここは乗算処理の文法を定義し、還元の際にはOpMulExpressionを作っています。
StatementもNumもIExpression型なので、そのままOpMulExpressionのコンストラクタに渡せます。
それではこのParser.jayからC#のファイルを生成します。
cloneしてきたmonoから先程ビルドしたjayの実行ファイルと、mono/mcs/jay/skeleton.csをParser.jayと同じディレクトリにコピーし、そのディレクトリ上でターミナルを開きjay -c Parser.jay < skeleton.cs > Parser.csを実行してください。
Parser.csが生成されると思います。これが構文解析を行うコードになります。
字句解析機を作る
次はre2cを使って字句解析機を作ります。
プログラムの実行順は字句解析 => 構文解析ですが、コードを作るのは構文解析機が先になります。
なぜなら、字句解析機のインターフェースと構文解析機が返すべきトークンがParser.csにて定義されるからです。
Lexer.reというファイルを作り内容は次のようにします。
namespace SampleLanguage.Interpreter
{
public class Lexer : yyParser.yyInput
{
private string _script;
private string _value;
private int _index;
private int _token;
private int _cursor;
private int _marker; public Lexer (string script)
{
_script = script;
} public bool advance ()
{
if ( _script.Length <= _index )
{
_token = Token.yyErrorCode;
_value = "";
return false;
}
_token = Lex(_index);
_value = _script.Substring(_index, (_cursor - _index));
_index = _cursor;
return true;
}
public int token ()
{
return _token;
}
public object value ()
{
switch (_token)
{
case Token.NUM:
return double.Parse(_value);
default:
return _value;
}
}
private int YYPEEK ()
{
if (_cursor == _script.Length)
{
return 0;
}
return (int)_script[_cursor];
}
private void YYSKIP ()
{
_cursor++;
}
private void YYBACKUP ()
{
_marker = _cursor;
}
private void YYRESTORE()
{
_cursor = _marker;
}
private int Lex (int startIndex)
{
_cursor = startIndex;
YYBACKUP();
loop:
/*!re2c
re2c:define:YYCTYPE = int;
re2c:yyfill:enable = 0;
WSP = [ \t\v\n\r];
WHITE_SPACE = WSP+;
OP_ADD = "+";
OP_SUB = "-";
OP_MUL = "*";
OP_DIV = "/";
LP = "(";
RP = ")";
DIGIT = [0-9];
DIGITNZ = [1-9];
U_INTEGER = "0" | DIGITNZ DIGIT*;
DOUBLE = U_INTEGER "." DIGIT+;
NUM = U_INTEGER | DOUBLE;
WHITE_SPACE { _index = _cursor; goto loop; }
OP_ADD { return Token.OP_ADD; }
OP_SUB { return Token.OP_SUB; }
OP_MUL { return Token.OP_MUL; }
OP_DIV { return Token.OP_DIV; }
LP { return Token.LP; }
RP { return Token.RP; }
NUM { return Token.NUM; }
*/
}
}
}
キモになるのは/*!re2cから始まるコメントの部分です。
ここで、re2cに作ってもらいたい字句解析機を定義します。
内容としては、単に正規表現の定義と、正規表現にマッチした際に適切なトークンを返す処理をしているくらいです。
YYPEEK()とかYYSKIP()はre2cで生成されるコードのためのメソッドです。
yyParser.yyInputはParser.csで定義されるインターフェースで、jayで生成した構文解析機を動かすのに必要です。
それでは字句解析機のcsファイルも作りましょう。
Lexere.reと同じディレクトリ上でターミナルを開き、re2c -i --input custom Lexer.re -o Lexer.csを実行します。
Lexer.csが生成されます。
これで、構文解析機と字句解析機ができました。
実際に使ってみる
これで四則演算ができるようになりました。
実際にコードを書いて試してみましょう。
なんでもいいのでクラスを作り、次のメソッドを定義します。
ここではSampleInterpreterとでもしましょうか。
public class SampleInterpreter
{
public static void Execute (string script)
{
var lexer = new Lexer(script);
var parser = new Parser();
var expression = (IExpression)parser.yyparse(lexer);
System.Console.WriteLine(expression.Evaluate());
}
}
これが今回の目標としていた「スクリプト（式）を文字列として受け取り、それを評価した結果を出力する」処理を実現するメソッドです。
これをMainメソッドから呼びます。
public static void Main (string[] args)
{
SampleInterpreter.Execute("1+1"); // => "2"
SampleInterpreter.Execute("1+1*3"); // => "4"
SampleInterpreter.Execute("1*(1-1)"); // => "0"
}
実行するとちゃんと計算結果が出力されたと思います。
おわりに
無事文字列を解析して四則演算するプログラムが実装できました。
プログラミング言語を作る上で最大の鬼門であろうスクリプトの解析がこれでできるようになったので、後はいくらでも拡張ができると思います。
次のステップとしては「複数の行に対応」「intやboolなどの型の実装」「関数の実装」「if文の実装」あたりでしょうか。
これらの実装についてはこの記事では扱いません。長くなる上に実現方法はいくらでもあるので。
いかがでしたでしょうか。
皆様もこの機にオレオレ言語を作ってみるのもいいと思います。
それではよい年末を。