シルバーウィーク
この週末は非常に実りの多い休みとなりました。盛岡行ってプリン食べつつ俺言語説明したり、仙台で俺言語作ったり、家で俺言語の作り方書いたりと、俺言語しかしてませんけど（笑）。俺言語だけしかしてないというのがすばらしいなぁっと。
特に、片平さんに話を聞いてもらえたのがよかったです。おかげで何が難しくて理解しずらいのかが再確認できました。ボスを手に入れたってかんじです。しかも、話を継続的に聞いてもらえそう＆場所も貸してもらえそう。といいことずくめです。お返しに片平さんの作るソフトウェアの手伝いをすることにはなっていますが、それもまた楽しいし。言語作りは自分のライフワークで、その話を身近で聞いてくれる人がいるというのは非常にありがたいことです。特に今は言語作り未経験者を対象とした文章を書こうとしているので、まだ分かっていないけど、興味を持っていてくれる片平さんは非常にありがたい存在です。できれば、いつまでもわかりそうだけどわからない人であって欲しいみたいなかんじです。毎回教えると覚えるが、すぐに忘れてもらえると最高という。。。それは無理だと思うけど。
とりあえず、今日書いていたバージョンのRubyで作る簡単なインタプリタ(1)をおいておきます。でも、あとで書き換えます。この文章が綺麗にまとまらない限り、次のステップに進めないので早く完成させたいのですけど、いつになることやら。。。
インストール
ここでは、Rubyのインストールの方法を簡単に説明します。そんなの、いらねーよっていう人は次の章に進んでしまってください。
ダウンロード
Rubyのホームページはこちらです。
http://www.ruby-lang.org/ja/
Rubyのダウンロードはここから
http://www.ruby-lang.org/ja/downloads/
筆者の環境は Windows XP なので Windows 版の ruby-1.9.2-preview1-i386-mswin32.zip をダウンロードしました。（そう！1.8ではなく高速な1.9です。）
解凍とPATH設定
ダウンロードが終わったら C:\ruby フォルダを作成します。（必ずC:\rubyである必要はないので環境によって読み替えてください。） C:\ruby にダウンロードしたファイルを解凍します。C:\ruby\binにPATHを通します。Ruby用のプログラムのフォルダをC:\ruby\prgに作ります。（これは好きなところで構いません。）
字句解析
まずは、数字や変数名、記号などに分割する字句解析のプログラムを作ってみましょう。
def lex case $src when /^[\r\n\t ]*([0-9]+)(.*$)/ when /^[\r\n\t ]*([+*\-\/()])(.*$)/ when /^[\r\n\t ]*(.*)(.*$)/ return nil end $src = $2 $1 end $src = "1+2*3" tokens = [] while (token = lex) != nil tokens.push(token) end p tokens
今回は（字句解析は英語でlex,tokinizer,scanner等というので）lexという関数名で字句解析器を作ります。このプログラムではソースの文字列を正規表現で、空白を除去し、数、記号、それ以外を読み込みます。
/^[\r\n\t ]*([0-9]+)(.*$)/
以上の正規表現は数に対応していて[\r\n\t ]*で改行やタブ、スペースの０回以上の連続を取り除き、([0-9]+)で0〜9の文字の１つ以上の連続を$1として取り出し、(.*$)で残りの文字列すべてを$2の文字列として取り出すという意味になっています。case文が終わったあとに$srcに$2を入れることで空白と数が削除され次のトークンを読み出す準備をします。$1は数の文字列になります。
/^[\r\n\t ]*([+*\-\/()]+)(.*$)/
上の正規表現は([+*\-\/()])が先ほどの数を表す([0-9]+)を置き換えたものになっています。これは +, *, -, /, (, ) のいずれか１つという意味で、四則演算に使われる記号を取り出す正規表現になっています。
/^[\r\n\t ]*(.*)(.*$)/
最後の正規表現はその他すべてにマッチするのでプログラムの終わりを示します。きちんとした処理をする場合はここにきた場合に空白以外の文字列が残っていればエラー処理する必要がありますが今回は飛ばします。次にオブジェクトとして実装した字句解析器を示します。
class Lexer def initialize src @src = src end def lex case @src when /^[\r\n\t ]*([0-9]+)(.*$)/ when /^[\r\n\t ]*([+*\-\/()])(.*$)/ when /^[\r\n\t ]*(.*)(.*$)/ return nil end @src = $2 $1 end def tokens ts = [] while (token = lex) != nil ts.push(token) end ts end end lexer = Lexer.new("1+2*3") tokens = lexer.tokens p tokens
Lexerクラスが字句解析クラスで、コンストラクタにプログラムソースを指定し、tokensメソッドでトークン配列を取り出します。最初の例でもオブジェクト指向版でも、結果として以下の結果が得られます。
["1", "+", "2", "*", "3"]
構文解析
次は構文解析器(Parser)を作ります。今回作るのは優先順位無しの構文解析器です。構文解析器いうと堅苦しいのでパーサと呼ぶことにします。以下にパーサのプログラムを示します。
class Parser def parse(src) @lexer = Lexer.new(src) tokens = @lexer.tokens exp = tokens.shift.to_i while tokens.first == "+" || tokens.first == "-" || tokens.first == "*" || tokens.first == "/" op = tokens.shift num = tokens.shift.to_i exp = [op, exp, num] end exp end end
パーサクラスにあるのは parse メソッドだけです。parse メソッドではソースプログラムを読み込み、字句解析器 (Lexer) を作成してトークン配列を取得します。トークン配列には数、記号、数、記号、数と入っているので最初に数を読み込み to_i で文字列を数値に変換します。次は記号のはずなので、記号を読み込みます。記号じゃなかったらループを抜けます。でopに記号を読み込み、いままで持っていた式と今読み込んだ記号と数字を１つの２分木として１つにまとめます。 1+2*3 の場合は [+,1,2] が最初できあがります。次にもう一度ループして [*,[+,1,2],3] となって終了します。よくあるプログラミング言語の場合は掛け算を優先的に結合するので [+,1,[*,2,3]] となるのですが、今回は初めてなので優先順位は持たせていません。優先順位をつけたプログラムは次回以降に説明します。
意味解析
最後に、意味解析を行うクラスを作ります。
class Calc def initialize @parser = Parser.new end def evalute src exp = @parser.parse(src) execute(exp) end def execute exp if exp.instance_of?(Array) case exp[0] when "+" execute(exp[1]) + execute(exp[2]) when "-" execute(exp[1]) - execute(exp[2]) when "*" execute(exp[1]) * execute(exp[2]) when "/" execute(exp[1]) / execute(exp[2]) end else exp end end end
Calc クラスが意味解析を行うクラスです。メソッドは３つあります。
コンストラクタではパーサを作成しています。
evalute メソッドはプログラムソースを評価します。まずパーサで構文木を作成します。次に execute メソッドに構文木を渡して計算を行い結果を返します。
evalute メソッドと excete メソッドが別れている理由は計算するときに再帰呼び出しを行うからです。 execute メソッドを見てください。配列でない場合はそのまま値を返しますが、配列だった場合は配列の最初（記号が入っている）で分岐してその葉となる1つめと2つめの要素はさらに execute メソッドを呼び出しています。この計算過程は以下のように進みます。
execute([*,[+,1,2],3]) execute([+,1,2]) * execute(3) (execute(1)+execute(2)) * execute(3) (1+execute(2)) * execute(3) (1+2) * execute(3) 3 * execute(3) 3 * 3 9
このようにして、意味解析を行うことができます。以上で今回のRubyによる計算機の作成はおしまいです。
次回はパーサをデータによって動的に変更できるようにしてみたいと思います。
