LISP級マクロ付きのインタプリタをPHPで書いてみました。
作る順番は、だいたい決まってきて、必要ない機能はある程度削られてますけど、
一番本質的な部分はつかめると思います。
以下ソースです。
<?php
class Symbol {
var $str;
private function __construct($str) {
$this->str = $str;
}
static function intern($str) {
static $arr = array();
if(isset($arr[$str])) return $arr[$str];
return $arr[$str] = new Symbol($str);
}
public function __toString() {
return "'".$this->str;
}
}
class Lexer {
function __construct($src) {
$src = str_replace("\r\n", "\v", $src);
$src = str_replace("\r", "\v", $src);
$src = str_replace("\n", "\v", $src);
$this->src = $src;
}
function lex() {
$m = array();
if (preg_match("/^[\\v\\t ]*([0-9]+)(.*$)/", $this->src, $m)>0) {
$this->src = $m[2];
return $m[1]+0;
}
if (preg_match("/^[\\v\\t ]*[\\v][\\v\\t ]*([(\\[{])(.*$)/", $this->src, $m)>0) {
$this->src = $m[2];
return "n" . $m[1];
}
if (preg_match("/^[\\v\\t ]*'([a-zA-Z_][a-zA-Z_0-9]*)(.*$)/", $this->src, $m)>0) {
$this->src = $m[2];
return Symbol::intern($m[1]);
}
if (preg_match("/^[\\v\\t ]*([()\\[\\]{},;]|[+*\\-\\/=<>]+|[a-zA-Z_][a-zA-Z_0-9]*)(.*$)/", $this->src, $m)>0) {
$this->src = $m[2];
return $m[1];
}
return false;
}
function tokens() {
$ts = array();
while (($token = $this->lex()) !== false) {
$ts[] = $token;
}
return $ts;
}
}
class Parser {
function __construct() {
$this->opLs = array(">"=>190, "<"=>190, "+" => 10, "-" => 10, "*" => 20, "/" => 20, "," => 2, "else" => 1);
$this->opRs = array("=" => 5);
$this->opPs = array("(" => ")", "[" => "]", "{" => "}", "n(" => ")", "n[" => "]", "n{"=>"}");
$this->opMs = array("(" => 200, "[" => 200, "{" => 200);
$this->opSs = array("fun" => "(", "if" => "(", "mac" => "(");
$this->opBs = array("++"=> 30, ";" => 1);
}
function parse($src) {
$lexer = new Lexer($src);
$this->tokens = $lexer->tokens();
$t = $this->expn(0);
while (count($this->tokens) > 0) {
$t = array("@", $t, $this->expn(0));
}
return $t;
}
function expn($p) {
if (in_array($this->tokens[0], $this->opPs, true)) {
return "vid";
}
$t = array_shift($this->tokens);
if (isset($this->opBs[$this->tokens[0]]) && ($tagp = $this->opBs[$this->tokens[0]]) >= $p) {
$op = array_shift($this->tokens);
$t = array("B". $op, $t);
$p = $tagp;
} elseif ($t instanceof Symbol) {
} elseif (isset($this->opSs[$t]) && $this->opSs[$t] == $this->tokens[0]) {
$op = array_shift($this->tokens);
if ($op[0] == "n") $op = substr($op, 1);
$e = $this->expn(0);
if (($op2 = array_shift($this->tokens)) != $this->opPs[$op]) {
throw new Exception("error $op2 ". $this->opPs[$op]);
}
$t = array("S" . $t . $op . $op2, $e, $this->expn(0));
} elseif (isset($this->opPs[$t])) {
if ($t[0] == "n") $t = substr($t, 1);
$t2 = $this->expn(0);
if(($t3 = array_shift($this->tokens)) != $this->opPs[$t]) {
throw "error";
}
$t = array("P" . $t . $t3, $t2);
}
while (true) {
if (isset($this->opMs[$this->tokens[0]]) && ($tagp = $this->opMs[$this->tokens[0]]) >= $p) {
$op = array_shift($this->tokens);
$e = $this->expn(0);
if(($op2 = array_shift($this->tokens)) != $this->opPs[$op]) {
throw new Exception("error");
}
$t = array("M" . $op . $op2, $t, $e);
} elseif(isset($this->opLs[$this->tokens[0]]) && ($tagp = $this->opLs[$this->tokens[0]]) > $p) {
$op = array_shift($this->tokens);
$t = array("L".$op, $t, $this->expn($tagp));
} elseif(isset($this->opRs[$this->tokens[0]]) && ($tagp = $this->opRs[$this->tokens[0]]) >= $p) {
$op = array_shift($this->tokens);
$t = array("R".$op, $t, $this->expn($tagp));
} else {
return $t;
}
}
}
}
class Env {
var $env;
function __construct($parent = null) {
$this->env = array();
if($parent != null) $this->env["parent"] = $parent;
}
function __isset($name) {
return isset($this->env[$name]);
}
function __get($name) {
if(isset($this->env[$name])) return $this->env[$name];
if(isset($this->env["parent"])) return $this->env["parent"]->$name;
return "nil";
}
function __set($name, $value) {
$rc = $this->put($this->env, $name, $value);
if ($rc === false) {
$this->env[$name] = $value;
return $value;
} else {
return $rc;
}
}
function put(&$env, $name, $value) {
if (isset($env[$name])) {
$env[$name] = $value;
return $value;
} elseif (isset($env["parent"])) {
return $this->put($env["parent"]->env, $name, $value);
} else {
return false;
}
}
}
class Calc {
function __construct() {
$this->parser = new Parser();
}
function evalute($src) {
$exp = $this->parser->parse($src);
var_export($exp); echo "\n";
$this->env = new Env();
$this->env->macros = array();
$exp = $this->macroExpand($exp, $this->env->macros);
var_export($exp); echo "\n";
return $this->execute($exp);
}
function macroExpand($a, &$e) {
foreach($e as &$obj) {
$this->env = new Env($this->env);
$rc = $this->macroMatch($obj[1], $a);
if ($rc) {
$r = $this->execute($obj[2]);
$this->env = $this->env->parent;
return $r;
}
$this->env = $this->env->parent;
}
if (is_array($a)) {
if ($a[0] == "Smac()") {
$e[] = $a;
return "nil";
} elseif ($a[0] == "M()" && $a[1] == "add" && is_array($a[2]) && $a[2][0] == "L,") {
return array("L+", $this->macroExpand($a[2][1], $e), $this->macroExpand($a[2][2], $e));
} else {
return array($a[0], $this->macroExpand($a[1], $e), $this->macroExpand($a[2], $e));
}
} else {
return $a;
}
}
function macroMatch ($a, $b) {
if(is_array($a)) {
return $a[0]==$b[0] && $this->macroMatch($a[1],$b[1]) && $this->macroMatch($a[2], $b[2]);
} elseif ($a instanceof Symbol) {
$name = $a->str;
$this->env->$name = $b;
return true;
} else {
return $a == $b;
}
}
function execute($exp) {
// var_dump($exp);
if (is_array($exp)) {
switch ($exp[0]) {
case "L+": return $this->execute($exp[1]) + $this->execute($exp[2]);
case "L-": return $this->execute($exp[1]) - $this->execute($exp[2]);
case "L*": return $this->execute($exp[1]) * $this->execute($exp[2]);
case "L/": return $this->execute($exp[1]) / $this->execute($exp[2]);
case "L<": return $this->execute($exp[1]) < $this->execute($exp[2]);
case "L>": return $this->execute($exp[1]) > $this->execute($exp[2]);
case "B;": return $this->execute($exp[1]);
case "B++": $name = $exp[1]; $dt = $this->env->$name; $this->env->$name = $dt + 1; return $dt;
case "R=": $name = $exp[1]; return $this->env->$name = $this->execute($exp[2]);
case "@": $this->execute($exp[1]); return $this->execute($exp[2]);
case "P()": return $this->execute($exp[1]);
case "P{}": return $this->execute($exp[1]);
case "P[]": return $this->execute($exp[1]);
case "Sfun()": return array("fun", $exp[1], $exp[2], $this->env);
case "fun"; return $exp;
case "Sif()":
$l1 = $this->execute($exp[1]);
if (is_array($exp[2]) && $exp[2][0] == "Lelse") {
if ($l1 != 0) {
return $this->execute($exp[2][1]);
} else {
return $this->execute($exp[2][2]);
}
} else {
if (l1 != 0) {
return $this->execute($exp[2]);
} else {
return "nil";
}
}
case "M()":
switch ($exp[1]) {
case "p": $rc = $this->execute($exp[2]); var_dump($rc); return $rc;
default:
$name = $exp[1];
if (!isset($this->env->$name)) {
var_dump($this->env);
throw new Exception("error ".$exp[1]);
}
$fun = $this->env->$name;
$back = $this->env;
$this->env = new Env();
$this->bind($fun[1], $exp[2]);
$this->env->parent = $fun[3];
$a = $this->execute($fun[2]);
$this->env = $back;
return $a;
}
default:
return $this->execute($exp[1]);
}
} elseif(is_string($exp)) {
return $this->env->$exp;
} else {
return $exp;
}
}
function bind($p, $l) {
if(is_string($p)) {
$this->env->$p = $l;
} elseif(is_array($p)) {
if(count($p) != 3) throw new Exception("error");
if(count($l) != 3) throw new Exception("error");
if($p[0] != "L,") throw new Exception("error");
if($l[0] != "L,") throw new Exception("error");
$this->bind($p[1], $l[1]);
$this->bind($p[2], $l[2]);
} else {
throw new Exception("error");
}
}
}
$calc = new Calc();
echo $calc->evalute("mac(mul('a,'b))a*b\nmul(2,3)");
この週末は非常に実りの多い休みとなりました。盛岡行ってプリン食べつつ俺言語説明したり、仙台で俺言語作ったり、家で俺言語の作り方書いたりと、俺言語しかしてませんけど（笑）。俺言語だけしかしてないというのがすばらしいなぁっと。
特に、片平さんに話を聞いてもらえたのがよかったです。おかげで何が難しくて理解しずらいのかが再確認できました。ボスを手に入れたってかんじです。しかも、話を継続的に聞いてもらえそう＆場所も貸してもらえそう。といいことずくめです。お返しに片平さんの作るソフトウェアの手伝いをすることにはなっていますが、それもまた楽しいし。言語作りは自分のライフワークで、その話を身近で聞いてくれる人がいるというのは非常にありがたいことです。特に今は言語作り未経験者を対象とした文章を書こうとしているので、まだ分かっていないけど、興味を持っていてくれる片平さんは非常にありがたい存在です。できれば、いつまでもわかりそうだけどわからない人であって欲しいみたいなかんじです。毎回教えると覚えるが、すぐに忘れてもらえると最高という。。。それは無理だと思うけど。
とりあえず、今日書いていたバージョンのRubyで作る簡単なインタプリタ(1)をおいておきます。でも、あとで書き換えます。この文章が綺麗にまとまらない限り、次のステップに進めないので早く完成させたいのですけど、いつになることやら。。。
今回はRubyでプログラミング言語を作ります。プログラミング言語といってもいろいろありますが、今回作る言語は式をベースとしたJavaScriptのようなインタプリタ言語です。第一回目は簡単な計算機を作ります。
対象はある程度プログラミング言語の知識がある中級者以上の人向けです。Rubyは使ったことがなくても構いません。しかし「ちょっと調べればRubyなんて楽勝よ！」という人向けです。
ここでは、Rubyのインストールの方法を簡単に説明します。そんなの、いらねーよっていう人は次の章に進んでしまってください。
http://www.ruby-lang.org/ja/downloads/
筆者の環境は Windows XP なので Windows 版の ruby-1.9.2-preview1-i386-mswin32.zip をダウンロードしました。（そう！1.8ではなく高速な1.9です。）
ダウンロードが終わったら C:\ruby フォルダを作成します。（必ずC:\rubyである必要はないので環境によって読み替えてください。） C:\ruby にダウンロードしたファイルを解凍します。C:\ruby\binにPATHを通します。Ruby用のプログラムのフォルダをC:\ruby\prgに作ります。（これは好きなところで構いません。）
次に楽にコマンドプロンプトを開けるようにします。スタート＞すべてのプログラム＞アクセサリ＞コマンドプロンプトを右クリックしてコピーします。コピーしたコマンドプロンプトを C:\ruby\prg に貼り付けます。C:\ruby\prg\コマンドプロンプトを右クリックしてプロパティを開きます。ショートカットの作業フォルダの欄を空白にして、OKボタンを押します。コマンドプロンプトをダブルクリックして C:\ruby\prg で作業ができるようになっていれば成功です。
コマンドプロンプト上でruby -vと入力してリターンを押します。
C:\ruby\prg>ruby -v ruby 1.9.2dev (2009-07-18) [i386-mswin32]
C:\ruby\prg\hello.rbを作成し以下のようなプログラムを書きます。
#hello.rb print("hello world")
C:\ruby\prg>ruby hello.rb
すると以下のように表示されれば確認終了です。
hello world
さて準備は整いました！
計算機といってもすぐに計算できるわけではありません。大きく分けて次の３つの段階に別れています。
１．数字や、変数名、記号等に分割する。（字句解析）
プログラムの文字列は、字句解析で数字や変数名、記号等のトークンに分解されます。分解されたトークン列は構文解析で木構造を持つ構文木に変換されます。構文木は意味解析で実際に評価され計算されます。コンパイラの場合はこのあと中間コードに変換され、最適化、コード生成と続きますが今回はコンパイラは作らないので扱いません。
まずは、数字や変数名、記号などに分割する字句解析のプログラムを作ってみましょう。
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による計算機の作成はおしまいです。
次回はパーサをデータによって動的に変更できるようにしてみたいと思います。
宮城県仙台でフリープログラマしてます。sumi compact言語を作ってます。
構文木を配列で表現するのは面白いですね。
Cの感覚だと構造体作ってという感じで考えちゃうので専用クラス作ってしまいそうです。
実はこんなのとかやってまして、
http://funladder.itosoft.com/
2パスアセンブラの要領で力技でやってますが、こういう所をちゃんと抑えてればもっと楽に作れるのかなとか思いました。