インタプリタをつくる

参考図書: 明快入門インタプリタ開発

前回のつづき。今回はインタプリタそのものに入る。

自作インタプリタは、とりあえず写経した後に理論を学ぶ方法で行こうかなと考える。 字句解析の部分はコピー。 構文解析の部分では、再帰的下向き構文解析のコードは最適化せず、そのままコピーで行けるだろう。

前回のminicalcで培った経験として、再帰的下向き構文解析をそのままにすることで、単項演算子への対応などの変化に強くなると考えた。 また、その時のコードは出来る限り使いまわす。これを方針としよう。

インタプリタを作ることへの野望

作り出す前の日記を読むと、以下のように書かれていた。

これを作ることにより、自分がほしい計算結果を素早く取り出すことができるようになる。 少なくとも、それを最適化するインタプリタを開発することができる。

まぁ、そんなところ。

日記

記号表の登録

関数だけ記号表を作成する。この後、内部コードへの変換を行う。

func hoge aaa

func huga aaa

上記のようなコードを書くと、以下のようにグローバルな記号表に登録される。

fncId: 0
search function huga: -1
fncId: 1
search function huga: 1
Gtable: hoge huga

内部コード格納

現在のところ、convert -> convert_restでのコードの変換の部分をcoutさせる。 関数やif文、for文、switch文などのネストが必要な文に関しては、convert -> convert_block_set -> convert_block -> convert_restとなる。 それができた場合、convert_restにfunやif、while、forが入るのはおかしいので、err_exit関数でエラーを出して終了。

記号表登録・検索

グローバルな領域に、グローバル変数と関数があって、両者の名前がかぶっていたときにエラーを出す。 ローカルな領域に、引数とローカル変数があって、両者の名前がかぶっていたときにエラーを出す。

ただし、今現在の実装は、ひとつの構文を読み取ってコード変換しているだけなので、エラーは出ない。 関数でエラーが出るが、これは関数の記号表登録時にチェックしているためで、今回の実装とは関係がない。

まだ内部コードの格納部分の話で、そこからさらにconvert_rest関数の実装、convert関数に戻り、各構文の処理を行う関数の実装に移る。 その時にエラーが出るようになるだろう。

Var構文の追加

Var構文を追加した。var の次に現れる構文はIdentでなければならない。

var $hoge, $huga, $hoge

の場合、$hogeが二重に定義されていることをエラーにしないが、

var $hoge
var $hoge

の場合、以下のようなエラーメッセージで落とす。

line: 25 ERROR 識別子が重複しています: $hoge

条件分岐、ループ

If文とFor、Whileを追加した。 一旦、ブロックの中を処理して、endを探す。

if 1
    print "print"
end

while 1
    print "while"
end

for n = 1 to 5
    print "for"
end

デバッグ実行結果

if: if
convert_block_set: 1
intnum: 1
convert_block: print
blkNest: 1
print: print
string: print
blkNest: 0
loop: while
convert_block_set: 1
intnum: 1
convert_block: print
blkNest: 1
print: while
string: while
blkNest: 0
loopNest: 0
loop: for
convert_block_set: n
ident: n
etc: =
intnum: 1
etc: to
intnum: 5
convert_block: print
blkNest: 1
print: for
string: for
blkNest: 0
loopNest: 0

関数宣言、実行開始行の設定、内部コード変換完了

内部コード変換完了

内部コードの変換を完了した。

関数宣言

関数宣言は、グローバル記号表に同じ名前のものがないかチェックしたあと、 引数を解析して、ブロックを解析する。

この時に、mainという名前の場合にはその関数から実行するフラグを立てる。

実行開始行の設定

とりあえずは1行目から。 main関数が、上記の関数宣言で見つかっている場合にはそれから始める。

構文チェック

まず、内部コードを取得するところから。 関数の場合は内部コードからジャンプするアドレスへ、他はリテラルであればその値、関数呼び出しと変数宣言はその種類を記録、アドレスを設定する。

If,Elif,Else,While,End

構文チェックを開始する。 ブロックにわかれているので、expression->term->factorの構文解析にまわることになる。

ここはminicalcで採用した最適化しないコードをコピペするか。 ちょっと考える。

構文チェックを実際に行う。 option “var”が入るとまだダメなので、以下のコードのシンタックスをチェックできるようにした。

while 1
    print "while"
end

if 1
    print "print"
elif 1
    print "eliff"
else
    print "else"
end

if 1
    print "print"
end
while 1
    print "while"
end

デバッグ時実行

kind: 158   text:   dblVal: 0   jmpAdrs: 3  symNbr: -1
kind: 163   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 159   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
syntaxchk:
kind: 190   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 190   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 152   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 163   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 153   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 163   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 154   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
syntaxchk:
kind: 163   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 159   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
syntaxchk:
kind: 190   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 190   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 152   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 163   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 159   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
syntaxchk:
kind: 190   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 158   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 163   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 159   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
syntaxchk:
kind: 190   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1
kind: 190   text:   dblVal: 0   jmpAdrs: 0  symNbr: -1

構文チェック For

一応できたのだが…変数宣言varを入れないとSegmentation Faultになる。

var s

for s = 0 to 5
    print "for"
end

これでうまく動くのだが…Segmentation Faultはまずいでしょ。 get_topAdrs関数がGtableにアクセスしている。 ところが、varがないと、Gtableにないので不正なアドレスへアクセスしようとしているようだ。

変数宣言のくだり、記号表登録でなんか間違えた？

(あとがき: IfやWhileは比較的カンタンだったのに、Forの時は変数宣言や回数などの定義で手こずった)

ForとEnd構文のミス

For文の構文チェックの際に見つけた、変数宣言のSegfaultは解消。 varがなく、なおかつoption “var”構文がないときに、自動的に変数が宣言されるという仕様のはずだった。

しかし、bbi_parse.cppで 「変数の検索をして、なかった時に変数宣言」が、 「変数の検索をして、あった時に変数宣言」となっていたことを発見した。

これでFor文の構文チェックが終わる…と思いきや、 複数の構文が発生した時に、出るはずのない「不正な記述です」のEofLineエラーが発生した。 これは一体何なんだろうと思ったら、bbi_parse.cppのEofLineを内部コードにするのを忘れていたというのが顛末だった。

また、この修正を行ったところ、endの次の行にいきなり構文を入れると「不正なEndです」というエラーが発生した。 これは、bbi_parse.cppのEofLineを内部コードにした時に、次のトークンを指定するのを忘れていたというのが顛末だった。

今回では初めて本格的にバグと格闘した。 その時の心境は非常にドス黒く、恐ろしく重い。 具体的には、過去に対する怒りとか。

こうした感情になったのは久々だった。 調子が戻ったとみるべきか、はたまたプログラミングがこんなに疲れるものだったのかはよくわからない。

構文チェック、完了

残りの構文をチェック終わり。syntaxChk関数がすべて終わる。これからexecute関数へと向かう。

構文の実行

Print, Println文の実行

まぁ、こんな感じ。最初にprint文から入ったほうが、後々デバッグしやすいと考えたため。

 $ cat test_print.bbi
 print "print"
 println "str"
 $ ./bbi_cli test_print.bbi
 printstr

変数

変数を宣言して、3をプリントすることに成功。次は演算子、その次に条件分岐とループ。その後に関数実行。

print "print"
println "str"

var hoge
hoge = 3
print hoge

演算子、組み込み関数

単項演算子、二項演算子の実装と、組み込み関数の実装。

print "print"
println "str"

var hoge
hoge = 3 + 7
print hoge

println 9 - 3
println 9 * 3
println 9 / 3
println 9 % 3
println 9 < 3
println 9 <= 3
println 9 > 3
println 9 >= 3
println 9 == 3
println 9 != 3
println 9 && 3
println 9 || 3

var a
a = input()

println a

println a/5
println toint(a/5)

実行結果。input関数で34と入力。toint関数で小数点以下切り捨て。

$ ./bbi_cli test_print.bbi
printstr
106
27
3
0
0
0
1
1
0
1
1
1
34
34
6.8
6

If文

if文を見つけたら、その式が真の場合にはブロックを実行して終了。偽の場合はElifが見つかって式が真であればブロックを実行して終了。Else文が見つかったらElseを実行する。文を実行したあと、アドレスをジャンプ先へ変更する。

var a
a = input()

println a

println a/5
println toint(a/5)

if a
    println "if-hoge"
elif 0
    println "elif-hoge"
else
    println "else-hoge"
end

実行結果

$ ./bbi_cli test_print.bbi
3
3
0.6
0
if-hoge
$ ./bbi_cli test_print.bbi
0
0
0
0
else-hoge

While, For, Break, Exit, 関数実行で、完成

完成。あとはコードを作ってみて、おかしかったら修正。あと機能追加をしてみたいかな。

While

If文と同じように処理できた。

For

まず、変数登録を行い、Stepで一回のループでどのくらい増やす・減らすのかを定義。なければ1.0。ループごとにtop_lineへ回してblockを実行させる。

関数実行

引数の変数を取得した後、実行中のアドレスを覚えておいてブロック実行。実行終了後、アドレスを元に戻してreturn

Break

Returnと同じく、?があれば真の時にbreakする。

Exit

Exitの次のコードを取得したあと、exit_Flgをtrueにしてexecute関数を終了させる。

結果。

ソースコードが諸事情で公開できないので、以下のコードの結果を載せます。

FizzBuzz

bb_fizzbuzz.bbi

func main()
    for i = 0 to 100
        print i, " "

        if i % 3 == 0
            print "Fizz"
        end
        if i % 5 == 0
            print "Buzz"
        end
        println ""
    end
end

実行結果

$ ./bbi_cli bb_fizzbuzz.bbi
0 FizzBuzz
1 
2 
3 Fizz
4 
5 Buzz
6 Fizz
7 
8 
9 Fizz
10 Buzz
11 
12 Fizz
13 
14 
15 FizzBuzz
16 
17 
18 Fizz
19 
20 Buzz
21 Fizz
22 
23 
24 Fizz
25 Buzz
26 
27 Fizz
28 
29 
30 FizzBuzz
31 
32 
33 Fizz
34 
35 Buzz
36 Fizz
37 
38 
39 Fizz
40 Buzz
41 
42 Fizz
43 
44 
45 FizzBuzz
46 
47 
48 Fizz
49 
50 Buzz
51 Fizz
52 
53 
54 Fizz
55 Buzz
56 
57 Fizz
58 
59 
60 FizzBuzz
61 
62 
63 Fizz
64 
65 Buzz
66 Fizz
67 
68 
69 Fizz
70 Buzz
71 
72 Fizz
73 
74 
75 FizzBuzz
76 
77 
78 Fizz
79 
80 Buzz
81 Fizz
82 
83 
84 Fizz
85 Buzz
86 
87 Fizz
88 
89 
90 FizzBuzz
91 
92 
93 Fizz
94 
95 Buzz
96 Fizz
97 
98 
99 Fizz
100 Buzz

2015/06/23 15:26