てきとうなさいと べぇたばん

明快入門 インタプリタ開発を読んでインタプリタをつくる その1

インタプリタを作る

とある日のこと。本屋でうろうろしていると、「明快入門 インタプリタ開発」を見つけた。PHPのソースコードを追っかけて、インタプリタの仕組みを知りたいと思っていたさなかだった。思わず手にとった。気が付いたら手にとってた。ほしいことが全部書いてあった。

インタプリタのしくみ

  1. 字句解析
  2. 構文解析
  3. コード実行

PHPといった本格的なプログラミング言語の場合は、構文解析で構文木を作って、構文木を仮想コードに変換して、その仮想コードから実行するという手段を取る。これは、最適化をしやすくするといったメリットが有るため。

この本では、簡潔にコード実行してしまう。

インタプリタの理解の方法

写経する。写経した中で、ここはこっちのほうが好きとか良いとか思ったらそっちに切り替える。コードの書き方としては、ひらメソッドのように関数を深掘って行って、一番末端の関数から書き移すような方法でボトムアップ的に書いていく。

実装などの経緯をEvernoteに書いていく。それをここで晒すかな。

日記

まず、実装を行ったのは、字句解析するtokenプログラム。

トークンを変換するプログラム

字句解析をできるようにした。 まず、文字種表の設定。ASCiiコードにそって、リテラルの数値、リテラルの文字列、 識別子、キーワードなどを登録していく。

その文字種表が出来上がると、次は読み込んだソースの一文字を、 トークンに変換する。識別子とリテラルの数値の判断ができた。

以下の文字列を含んだテキストファイルを字句解析してみる。

abc hoge123 123 def dt

そうすると、以下のようになった。 出力している内容は、左からソースの文字列、トークンの種類(20はLetter、21はDigit)、数値リテラルの場合はその数値。

$ ./token_p_letter_only letter_only_test.txt
text kind intVal
abc 20 0
hoge123 20 0
123 21 123
def 20 0
dt 20 0

もっと増やそう。

構文解析を使った電卓

結局、字句解析のプログラムを一つディレクトリを落として、 nextTkn関数などを再利用。とはいえ1文字のトークンを取得するように改造する必要はあったけど。

入力したデータから、1文字ずつ取得して、トークン化。トークンにすることによって、 それが何なのかを調べる。 今は1文字だけ取得したトークン(Token構造体)の内容を出力させるだけ。

これからは、そのトークンから分岐させて計算させるのか、変数として格納するのか、内容を表示させるのかといった、 実際の処理を書いていくことになる。

電卓、一応できる

一応出来た。

構文解析の方式としては、再帰的下向き構文解析にあたる。 構文図の通りに実装でき、構文を追加するのも容易。これ、結構わかりやすいね。

ごちうさ1羽に出てくる阪神算もこの通り。なんでや!

$ ./minicalc
? 334+(33+4)+(3-(3+4))
  367

疑問点が残る。単項演算子の演算方法はどうする?という問題が出てきた。 字句解析部分でやろうかと試したが、そうすると引き算ができなくなる。

やはり構文解析でやるべきだと確信した。 P.169に載ってるので、後で理解しておこう。

電卓、べき乗の実装

minicalc.cppにはべき乗が乗っていない。別にこれくらい追加してもいいんじゃないかと思い、調べてみた。 どうやら、カッコと掛け算割り算の間になる。ということは、termとfactorの間に構文図を追加しないと行けない。

そのため、term -> factorから、term -> power -> factorに追加・変更。math.hのpowを使ってoperate関数で計算。

二項演算子と単項演算子を追加。

二項演算子は、字句解析でトークンにする部分で取り込んでしまい、単項演算子はfactorで行う。

おまけとして、階乗を搭載。3!は6になる。

$ ./minicalc
? 3!
6

また、累乗の演算子を^から**へ。RubyやPythonと同じものに変更。

$ ./minicalc
? 10 ** 2
100
? 2 ** 10
1024

更に、剰余を追加。

$ ./minicalc
? 10 % 2
0
? 9 % 2
1

これで、最低限の電卓として使えるんじゃないかな。ただし、課題が発生。

  • Boolean型がないので、比較演算子の時にTRUEとFALSEを1と0で行わなければならない。めんどい
  • いちいち同じ計算を入れるのめんどい。関数追加したい。
  • 小数がでないので、割り算の結果が0になる。

以下、阪神算をご覧あれ。

$ ./minicalc
? 3-3!+4
1
? 3+3-4
2
? 3 ** 3-4!
3
? 3-3+4
4
? 3*3-4
5
? 3!/3+4
6
? 3!-3+4
7
? 3!+3!-4
8
? 33-4!
9
? 3+3+4
10
? (334+33*4-3*3*4)*(33-4)
12470

続き。インタプリタをつくるよ