C++でbasicインタプリタを作る  

プログラムを書き始める前に、ソフトのイメージを想像してみる

■Windows,Linux両対応にする
Windows:VC6 Linux:g++
でコンパイルできるようにする
つまり、WindowsのAPIやLinuxのAPIを直接使わないようにする

■basicコードのファイル名は引数で入力する

実行ファイル名.exe basicコード.txt

■変数というか、インタプリタのメモリは、マップデータ構造を使う                

map[変数名] = 値

すなわち、変数宣言自体が必要なくなる

■計算ロジック
バリアント型を作成して、
すべての計算はバリアント型で行い、結果を変数に格納する

double型とSTL Stringクラスを内封するバリアントクラスを作り、逆ポーランド法に従い計算する

文字列は""に囲まれたものとする
文字列演算や数値演算を気にせずに出来るようにする
比較演算 == <= >= < > <> 論理演算 && || も計算できるようにする
比較演算や論理演算の結果は 、TRUEは1としてFALSEは0とする


バリアント型は前回 "C++でBASICライクなプログラムを書いてみる"で作成した
クラスを再利用する
計算機能は前回 "C++でBASICライクなプログラムを書いてみる" で作ったプログラムを
再利用する

■input文
キーボードからの入力を受け付け、変数に格納する

■print文
print文は print 演算 → print=演算 に文字列変換して計算ロジックに引き渡すことにより
変数名 print に演算結果が代入される
その後、変数 ptint の内容を画面に出力する

■if文
if文は if 演算 → if=演算 に文字列変換して計算ロジックに引き渡すことにより
変数名 if に演算結果が代入される
その後、変数 if の内容(0 or 1)により then もしくは else 以降の命令を実行させる

■コメント
'で始まる文をコメントとする
ファイル読み込み時に'をNULLに置換する事により、無視する。

■goto文

goto ラベル:

ラベルを先頭から検索してその行にジャンプする。
命令以外の文字列がプログラムの行の先頭から書かれており、文字列の最後が:である場合ラベルとみなす


▲上記仕様にしたがってプログラムを作成しました
作成したプログラムはこのページの最後でダウンロード可能です

Windowsで実行するには、VisualC++ で目的のディレクトリのプロジェクトファイルを開いて
ビルド でコンパイルできます。
実行するにはコマンドプロンプトを開き実行ファイルの有るディレクトリに移動して

>basic ../sample.txt

のように打ち込んでください。

Linuxで実行するには、ファイルの解凍後のディレクトリに移動して make を実行すると
コンパイルされます。実行するには

$./basic ./sample.txt

と打ち込んでください



■動作確認用のbasicプログラム

input a                                   'aを入力
b="test"                                  'bに文字列を代入
test:                                     'ラベル
a = a + 1                                 'aに対して1を足す 数値演算
b=b+a                                     'bに対してaを足す 文字列演算
print a                                   '数値    a  を出力
print b                                   '文字列  b  を出力
if a==10 then goto test2: else goto test: 'aが10ならば、goto test2を実行、それ以外では、goto testを実行
test2:                                    'ラベル
print "\\--  end  --\\"                   '文字列を出力
end                                       '終了を表す命令 [省略可能]

▲上記プログラムをsample.txtとして保存して実行させてみました


$ ./basic sample.txt
? 1
2
test2
3
test23
4
test234
5
test2345
6
test23456
7
test234567
8
test2345678
9
test23456789
10
test2345678910
\--  end  --\


ちゃんと動作しています。

■for next 文の追加 ----------------------------------------------------------

よくよく命令を見てみるとfor文が無い!!!
でfor文を追加してみたいと思います

for a=1 to 100 step 1

next a


▼for文の動作の設計

for a=1 は変数 a に 1 を代入する

▼next aはプログラムカウンタをさかのぼり for a= を探し、条件式を判定、
@変数を加算する
  stepがあればその数を加算、なければ1を加算
A条件式を判断
  結果が 1 の場合は、プログラムカウンタをfor文の次の行に設定する
  結果が 0 の場合は、現在のプログラムカウンタを進める

ガリガリとプログラムを書いて命令に追加しました

■動作確認用のbasicプログラム

for aa=0 to 20 step 5
for a= 1  to  2
  print "a="+a
  print "aa="+aa
next a
next aa

▲上記プログラムをcheck5.txtとして保存して実行させてみました

$ ./basic check5.txt
a=1
aa=0
a=2
aa=0
a=1
aa=5
a=2
aa=5
a=1
aa=10
a=2
aa=10
a=1
aa=15
a=2
aa=15
a=1
aa=20
a=2
aa=20

ちゃんと動作しています


■配列を追加 ----------------------------------------------------------

本来なら、配列はメモリに並んで確保されるはずですが
強引な配列の考え方として・・・・

現状では以下の三つの配列は別々の変数名として解釈される
a=2

arry[2]
arry[a]
arry[1+1]

プログラム実行時の最初に[ ]に囲まれた文字列を抜き出し、
ANS=1+1 のように変形して計算ロジックにより計算させる
計算された結果を元のプログラムの[]の中に戻す。
以上によりプログラム中の[ ]に囲まれた中の値が計算結果となり、
arry[no] が一つの変数名として扱われるため
配列のように動作させることが出来ると考えられる

うまい事に多次元配列まで実現できてしまうというおまけつきで

ガリガリとプログラムを書いて命令に追加しました

■動作確認用のbasicプログラム

a=3

a[a]=10+1
a[a+1]=a[a]+1
a[1][2]=a[a+1]+1
a[3]=a[1][2]+1


print a[a]
if a[3]=14 then print "OK" else "ERR"
if a[1+2]=14 then print "OK" else "ERR"
if a[a]=14 then print "OK" else "ERR"

▲上記プログラムをcheck6.txtとして保存して実行させてみました

$ ./basic check6.txt
14
OK
OK
OK

いい感じです

■エスケープシーケンス文の追加 ----------------------------------------------------------


ターミナルを制御(カーソル位置や色など)する制御文字をあらわし、
ESC : 8進数で033 から始まる文字列を出力できるようにします

画面クリア cls とカーソル位置移動 location x,y を追加しました

windowsだとエスケープシーケンスに対応したターミナルを使わないと
動きませんね




■自作basic版、ライフゲームを作ってみる ----------------------------------------------------------

作成した言語のデバックを兼ねて、自作basic版ライフゲームを書いてみようと思います
画面描画はエスケープシーケンスを使用したいと思います


▼ライフゲームのルール

@死んでいるセルの周囲に3つの生きているセルがあれば次の世代では生きる。
A生きているセルの周囲に2つか3つの生きているセルがあれば次の世代でも生き残る。
B上以外の場合には次の世代では死ぬ。


ライフゲームのプログラムを自作BASICで作成して
グライダー・ガンの初期値を与えました

  1 2 3 4 5 6 7 8 9 101112131415161718192021222324252627282930313233343536
1 □□□□□□□□□□□□□□□□□□□□□□□□■□□□□□□□□□□□
2 □□□□□□□□□□□□□□□□□□□□□□■□■□□□□□□□□□□□
3 □□□□□□□□□□□□■■□□□□□□■■□□□□□□□□□□□□■■
4 □□□□□□□□□□□■□□□■□□□□■■□□□□□□□□□□□□■■
5 ■■□□□□□□□□■□□□□□■□□□■■□□□□□□□□□□□□□□
6 ■■□□□□□□□□■□□□■□■■□□□□■□■□□□□□□□□□□□
7 □□□□□□□□□□■□□□□□■□□□□□□□■□□□□□□□□□□□
8 □□□□□□□□□□□■□□□■□□□□□□□□□□□□□□□□□□□□
9 □□□□□□□□□□□□■■□□□□□□□□□□□□□□□□□□□□□□


scr[25][ 1]="#"
scr[23][ 2]="#"
scr[25][ 2]="#"
scr[13][ 3]="#"
scr[14][ 3]="#"
scr[21][ 3]="#"
scr[22][ 3]="#"
scr[35][ 3]="#"
scr[36][ 3]="#"
scr[12][ 4]="#"
scr[16][ 4]="#"
scr[21][ 4]="#"
scr[22][ 4]="#"
scr[35][ 4]="#"
scr[36][ 4]="#"
scr[1 ][ 5]="#"
scr[2 ][ 5]="#"
scr[11][ 5]="#"
scr[17][ 5]="#"
scr[21][ 5]="#"
scr[22][ 5]="#"
scr[1 ][ 6]="#"
scr[2 ][ 6]="#"
scr[11][ 6]="#"
scr[15][ 6]="#"
scr[17][ 6]="#"
scr[18][ 6]="#"
scr[23][ 6]="#"
scr[25][ 6]="#"
scr[11][ 7]="#"
scr[17][ 7]="#"
scr[25][ 7]="#"
scr[12][ 8]="#"
scr[16][ 8]="#"
scr[13][ 9]="#"
scr[14][ 9]="#"


▲上記データをプログラムに取り込んでlifegame.txtとして保存して実行させてみました
エスケープシーケンス対応していないターミナルだとうまく表示されません

./basic lifegame.txt





▲遅いですが、ちゃんと動作します
完全なライフゲームのコードは4行下にあります。


■自作インタプリタの処理速度を調べる

同じライフゲームの自作BASIC版を適当にC言語版に書き換えてみました

basic と C++のライフゲーム

gccによりコンパイルを行い同時に走らせて見ると、
自作インタプリタ版に比べ、ネイティブ版の実行速度は2000倍以上速いです
自作インタプリタは2000倍以上無駄な動作があるということですねえ
まあ、あれだけ文字列複製、文字列置換やらマップから引いたりしてるから
遅くなるのもあたりまえか笑



■実行速度

lifegameを実行させてプロファイルを取ると

time   seconds   seconds    name
  9.64      3.52     3.52    std::string::compare(char const*) const
  7.39      6.22     2.70    std::string::compare(std::string const&) const
  6.24      8.50     2.28    __gnu_cxx::__exchange_and_add(int volatile*, int)
  4.76     10.24     1.74    __gnu_cxx::__atomic_add(int volatile*, int)
  3.67     11.58     1.34    _Unwind_SjLj_Register
  3.01     12.68     1.10    _Unwind_SjLj_Unregister

どう見てもstring 付近が怪しそうです
いたるところで文字列比較しまくってるからなあ。

▼効果が期待できないと知りつつもgoto とfor next を速くしてみようと思います
goto文やnext文を実行する時は、毎回、対応するラベルやfor文を総当りで検索しています
ならば、一度検索した時の、対応する行ナンバーを変数に控えておけば、少しは速くなるはず・・・・
ソースコードのstring型vecter配列と同じ数だけlong型vecter配列をつくり、
一度目で、対応するラベルやfor文を検索した時には、行番号を控えておいて
二度目からは値を参照するだけで動作するように変更してみます


変更してみましたが、少しは速くなったのでしょうけど、
やはり体感速度は変わらないです笑


■作成後に思ったこと ----------------------------------------------------------


行き当たりばったりで作ったインタプリタとしては実行速度こそは遅いですが
ちゃんと動作させることができました
しかし、現在の設計では言語としての命令事態がインタプリタに直接コーディングされており、
インタプリタに機能(関数)を追加しようとするとインタプリタ自体を書き換えないと実現できません
この状態で関数を追加しようとすると、一つの関数を追加するたびにインタプリタ事態の改造および
デバックを行わなければならず、これでは拡張性自体あったもんじゃないです。

拡張性を上げるには可能な限りインタプリタは書き換えないで
機能を追加できる仕組みを考える必要があります
一番よさそうなのが、インタプリタの言語でインタプリタの機能を作成するということでしょう。


▼言語でインタプリタの機能を追加するために必要と思われる機能

@関数(関数の宣言と呼び出し、引数の引渡し、戻り値の引渡し)
A言語としての機能を実現するために変数の内容をトリガーとしたソフトウェア割り込み
Bライブラリ読み込み機能

上記3つの機能を取り込み、
言語としての関数をすべて言語で記述してライブラリとして保存する
プログラムの実行時には基本となるライブラリを取り込ませる
そうすれば、より完成度の高いインタプリタが作成できると思います


■マニュアル ----------------------------------------------------------

マニュアルは長くなるのでソースと一緒に添付することにしました。


■作成したインタプリタとプログラム

basicではsourceforgeにオープンソースとして登録できなかったから abasic として登録しました
a の次は b -> c -> d と行こうかと思った、ただたんに安易な命名です(笑
そもそも登録したのはCVS(バージョン管理システム)を使ってみたかっただけですし。
登録後気がついたのですが、どこかの有名言語と名前がかぶってないか?と思ったのでしたw


sourceforge.jp




2006/08/19 作成


▲トップページ > プログラミングの実験