変数を使った四則演算ができる簡単なlispインタプリタを書きました。
トークン解析と構文解析
lispは下記のように書きます。
(- 3 2) ;6 (- 3 (* 2 3)) ;-3 (setq a 3)
プログラムはリストで記述されます。
リストとは'('と')'で囲まれた部分です。「(- 3 2)」
リストの中にリストを入れる事もできます。「(- 3 (* 2 3))」
トークン解析では文字列として読み込んだリストを、トークンに分けて配列に格納します。
例えば「(- 3 2)」を読み込んだ場合「'(','-','3','2',')'」の配列に分けます。
これを行なうスクリプトが下記のようなものになりました。
sub get_tokens { my $in_str = shift; my @chars = split(//,$in_str); my $token_buf = ''; my @tokens = (); my $in_double_quote = 0; foreach my $c (@chars) { if ($c eq '"') { if ($in_double_quote) { $in_double_quote = 0; } else { $in_double_quote = 1; } } if ($c eq '(' || $c eq ')') { if ($token_buf) { push @tokens, $token_buf; $token_buf = ''; } push @tokens, $c; } elsif (!$in_double_quote && is_ignore_char($c)) { if ($token_buf) { push @tokens, $token_buf; $token_buf = ''; } } else { $token_buf .= $c; $token_buf .= $c; } } return @tokens; } sub is_ignore_char { my $c = shift; if ($c =~ /^(\t|\r|\n| |)$/) { return 1; } else { return 0; } }
構文解析では、一つのリストを一つの配列に対応させます。
リストの中のリスト、という構造も表現するようにします。
['-','3','2'] # (- 3 2) ['-','3',['*','2','3']] # (- 3 (* 2 3))
構文解析では、トークンの配列を受け取って解析を行なっています。
sub slisp_parse { my @tokens = @_; my @stack = (); foreach my $token (@tokens) { if ($token eq '(') { push @stack, []; } elsif ($token eq ')') { my $cur_stack = pop @stack; my $up_stack = pop @stack; if ($up_stack) { push @stack, [@$up_stack,$cur_stack]; } else { push @stack, $cur_stack; } } elsif (is_primitive($token)) { my $cur_stack = pop @stack; push @stack, [@$cur_stack,$token]; } elsif (check_type($token) =~ /^(string|number|symbol)/) { my $cur_stack = pop @stack; push @stack, [@$cur_stack,$token]; } else { my $cur_stack = pop @stack; push @stack, [@$cur_stack,$token]; } } @stack = ('progn',@stack); return [@stack]; } sub is_primitive { my $token = shift; my @primitive_list = qw#list setq let defun if cond lambda apply progn quote print + - * / = > < not or and#; foreach my $p (@primitive_list) { if ($token eq $p) { return 1; } } return 0; }
最終的に「[ 'progn',[ '+','3','2' ] ]」という形になります。
評価
構文解析したものを受け取って、実行していきます。
構文分析したものに従って実行する事を「評価」と呼びます。
評価は、外側のリストから行なわれます。
例えば「['progn',['+','3',['*','2','3'] ] ]」の場合、「['progn'...]」を評価します。
配列を受け取り、評価する関数は下記のようになります。
sub slisp_eval { my $exp = shift; if (is_self($exp)) { return $exp; } elsif (is_variable($exp)) { return lookup_variable_value($exp, \%env); } elsif (slisp_make_primitive($exp,'setq')) { return eval_assignment($exp, \%env); } elsif (slisp_make_primitive($exp,'progn')) { eval_sequence(progn_actions($exp)); } elsif (is_arithmetic($exp)) { calc($exp); } elsif (slisp_make_primitive($exp,'print')) { slisp_print($exp); } else { die "Unknown expression type.". Data::Dumper->Dump([$exp]); } }
各種類のリストに対して評価を行います。
計算リスト(['+','2','3'])
計算リストに対しては、calc関数が処理します。
sub calc { my $exp = shift; my $op = $exp->[0]; my $first = slisp_eval($exp->[1]); my $second = slisp_eval($exp->[2]); if ($op eq '+') { return $first + $second; } if ($op eq '-') { return $first - $second; } if ($op eq '*') { return $first * $second; } if ($op eq '/') { return $first / $second; } }
演算子の各引数に対して評価してから計算します。例えば「['+','3',['+','3','1']]」といったリストに対応しています。
変数の代入と参照(['setq','a','1'])(['+','a','1'])
setqに対しては、eval_assignment関数が処理します。
sub eval_assignment { my ($exp, $env) = @_; my @e = @$exp; my %copy_env = %$env; my $variable = $e[1]; my $value = slisp_eval($e[2],\%copy_env); $env->{$variable} = $value; }
シンボルテーブルの役割をしている$envというハッシュ変数に、変数名と値を格納しています。
参照に関しては、lookup_variable_value関数が処理します。
sub lookup_variable_value { my ($exp, $env) = @_; return $env->{$exp}; }
progn
prognは、引数であるリストを順に評価していきます。
progn_actions関数で、prognに渡されている引数のリストを取ってきます。
そして、eval_sequence関数で、引数のリストを順番に評価していきます。
sub eval_sequence { my $actions = shift; foreach my $action (@$actions) { my $value = slisp_eval($action); } }
テスト
下記のスクリプトをプログラムに読み込ませます。
(progn (setq a (- 3 (* 2 3))) (setq a (- a 100)) (print a))
$ perl slisp.pl test.lisp
計算結果である「-103」が表示されます。
TODO
- ifを使えるようにする
- 関数定義(defun)ができるようにする
参考
Software Design (ソフトウェア デザイン) 2010年 05月号 [雑誌]
- 出版社/メーカー: 技術評論社
- 発売日: 2010/04/17
- メディア: 雑誌
- 購入: 1人 クリック: 50回
- この商品を含むブログ (17件) を見る
- Emacsのトラノマキ第13回「俺流Lispインタプリタ」
- http://github.com/sodeyama/slisp