C++でbasicインタプリタを作る
プログラムを書き始める前に、ソフトのイメージを想像してみる
■Windows,Linux両対応にする
Windows:VC6 Linux:g++
でコンパイルできるようにする
つまり、WindowsのAPIやLinuxのAPIを直接使わないようにする
■basicコードのファイル名は引数で入力する
実行ファイル名.exe basicコード.txt
■変数というか、インタプリタのメモリは、マップデータ構造を使う
map[変数名] = 値
すなわち、変数宣言自体が必要なくなる
■計算ロジック
バリアント型を作成して、
すべての計算はバリアント型で行い、結果を変数に格納する
double型とSTL Stringクラスを内封するバリアントクラスを作り、逆ポーランド法に従い計算する
文字列は""に囲まれたものとする
文字列演算や数値演算を気にせずに出来るようにする
比較演算 = <= >= < > <> 論理演算 && || も計算できるようにする
比較演算や論理演算の結果は 、TRUEは１としてFALSEは０とする
バリアント型は前回 "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を加算
②条件式を判断
結果が 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つの生きているセルがあれば次の世代では生きる。
②生きているセルの周囲に2つか3つの生きているセルがあれば次の世代でも生き残る。
③上以外の場合には次の世代では死ぬ。
ライフゲームのプログラムを自作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
▲遅いですが、ちゃんと動作します
■自作インタプリタの処理速度を調べる
同じライフゲームの自作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文を検索した時には、行番号を控えておいて
二度目からは値を参照するだけで動作するように変更してみます
変更してみましたが、少しは速くなったのでしょうけど、
やはり体感速度は変わらないです笑
■サブルーチンの追加 ----------------------------------------------------------
サブルーチンとは今で言う関数みたいなものとイメージしてください
大昔のプログラム言語では関数という観念が存在しなくてサブルーチンという方法で
プログラムの制御構造を作成していました
実際に自作Basicでプログラムを書いてみると、
プログラムの制御構造を操作する命令がgoto文しかないため、
がんばって見やすく書いてもスパゲティなプログラムが出来てしまいます
そこで、gosub return を追加したいと思います
gosubとは、サブルーチン呼び出しを行う命令で、gosubに続くラベルに指定された行にジャンプします
returnとは、サブルーチンの呼び出し元に戻る命令です
▼実行されるBasicプログラムのイメージ
gosub Label ←サブルーチンLabelにジャンプする
end
Label ←サブルーチンのラベル
サブルーチンの処理
return ←呼び出し元(gosub Label)に戻る
このような感じで動作するようにしようと思います
▼インタプリタの動作イメージとして
①gosub文が呼ばれた時点の実行行番号を控えて目的のラベルにジャンプする
②ラベルからプログラムを実行する
③return文が呼ばれた時点で①で控えた行番号の次の行にジャンプする
このように処理すれば動作するような気がします。
しかし、サブルーチンの中からサブルーチンを呼び出した場合、
控えた行番号が書き換えられてしまい、returnが正しく動作しません。
そこで先入れ後出しのデータ構造、スタックを使い行番号を控えようと思います
スタックは先入れ後出しのため、サブルーチンが何重にネストしたとしても、
returnにより正しい戻り行番号が返ってきます。
上記方法に従いインタプリタにgosub return を追加しました
■動作確認用のbasicプログラム
gosub aaa
print "ggg"
end
aaa
print "aaa"
gosub bbb
return
bbb
print "bbb"
gosub ccc
return
ccc
print "ccc"
gosub ddd
return
ddd
print "ddd"
gosub eee
return
eee
print "eee"
gosub fff
return
fff
print "fff"
return
▲上記プログラムをcheck8.txtとして保存して実行させてみました
$ ./basic check8.txt
aaa
bbb
ccc
ddd
eee
fff
ggg
正しくgosubとreturn が動作している事を確認できます
■作成後に思ったこと ----------------------------------------------------------
行き当たりばったりで作ったインタプリタとしては実行速度こそは遅いですが
ちゃんと動作させることができました
しかし、現在の設計では言語としての命令事態がインタプリタに直接コーディングされており、
インタプリタに機能（関数）を追加しようとするとインタプリタ自体を書き換えないと実現できません
この状態で関数を追加しようとすると、一つの関数を追加するたびにインタプリタ事態の改造および
デバックを行わなければならず、これでは拡張性自体あったもんじゃないです。
拡張性を上げるには可能な限りインタプリタは書き換えないで
機能を追加できる仕組みを考える必要があります
一番よさそうなのが、インタプリタの言語でインタプリタの機能を作成するということでしょう。
▼言語でインタプリタの機能を追加するために必要と思われる機能
①関数(関数の宣言と呼び出し、引数の引渡し、戻り値の引渡し)
②言語としての機能を実現するために変数の内容をトリガーとしたソフトウェア割り込み
③ライブラリ読み込み機能
上記３つの機能を取り込み、
言語としての関数をすべて言語で記述してライブラリとして保存する
プログラムの実行時には基本となるライブラリを取り込ませる
そうすれば、より完成度の高いインタプリタが作成できると思います
■マニュアル ----------------------------------------------------------
□起動方法
basic filename
引数にインタプリタで実行するプログラムの書かれたテキストファイルを渡すことにより実行できます
□制限事項
▽一行あたりの行数
プログラムは一行あたりの文字数がデフォルトで1024文字以内である必要があります。
また、変数に格納可能な最大文字数もデフォルトで1024文字以内である必要があります。
文字数を変更するには、
common.h 内の #define MAX_STR_LEN 1024 を変更する必要があります。
□プログラムで使用可能な変数
変数型は64ビット浮動小数点型と文字列型があります。
変数名および、変数型の宣言は必要ありません。
総ての変数はグローバルスコープを持ちます。
配列は data[1] のように指定します。
多次元配列は data[1][2] のように指定します次元数の制限はありません。
以下のように配列の添え字として文字列を指定することもできます
data["aaa"]=1
□文字列と数値の演算
文字列の足し算が行われた場合は文字列が連結され、
数値同士の演算が行われた場合には、数値の演算結果が戻されます。
数値と文字列の足し算が行われた場合においては、数値が文字列として扱われ、文字列をして連結されます。
▽プログラム
print 1+1
print 1+"test"
print "test"+1
print "test"+"test"
▽実行結果
$ ./basic test.txt
2
1test
test1
testtest
□プログラムで使用可能な命令
▽コメント
'コメント文
'で始まる文字列はコメントとして扱われます
▽条件分岐
if 条件式 then 命令１ else 命令２
条件式の結果が0の場合は命令２が実行され、それ以外には命令１が実行されます
・条件式には以下のものが使用できます
= イコール
< 小なり大なり
> 大なり小なり
<= 小なり大なりイコール
>= 大なり小なりイコール
&& アンド
|| オア
<> ノットイコール
・条件分岐のサンプル
if 1=1 then print "true" else print "false"
if "test"="test" then print "true" else print "false"
if 1<1 then print "true" else print "false"
if 1>1 then print "true" else print "false"
if 1<=1 then print "true" else print "false"
if 1>=1 then print "true" else print "false"
if 1=1 && 2=1 then print "true" else print "false"
if 1=1 || 2=1 then print "true" else print "false"
if "test"<>"aaaa" then print "true" else print "false"
▽ループ
for x=1 to 10
print x
next x
xが1～10までループします
for文のネストも可能です
▽ジャンプ
goto label
label
goto文によりラベルにジャンプします
ラベルは命令として利用されていない文字列であれば制限はありません
▽サブルーチン
gosub label
label
return
gosub命令により指定されたラベルにジャンプし、return命令により、ジャンプ元に復帰します
サブルーチンのネストも可能です
▽入力命令
input 変数
入力を要求してきます、入力結果が変数に格納されます
▽出力命令
print "文字列"
print 変数
値を画面上に出力します
▽エスケープシーケンス命令
エスケープシーケンス対応の端末のみ対応します
clr
location 1,1
clr命令により画面をクリアします
location命令によりカーソルを画面の指定座標に移動します
▽待機命令
wait
この命令が入ると、約1秒間プログラムが停止します
▽abs命令
abs 変数
変数に格納されている値の、小数点以下を切り捨てます
▽shell命令
shell "notepad test.txt"
指定したプログラムを実行します
実行したプログラムが終了するまで待機します
▽終了命令
end
この命令が読み込まれた時点でプログラムが終了します
□プログラム中で使用可能な環境変数
代入は出来ません、参照のみです。
通常の変数のように読み出します。
▽乱数
取得できる乱数値は 0～9999 の範囲です
rand
▽時間
time.year 年
time.mon 月
time.day 日
time.week 日曜を0、月曜を1とする曜日をあらわす値
time.hour 時間
time.min 分
time.sec 秒
■作成したインタプリタとプログラム
sourceforge.jp
2006/08/19 作成
▲トップページ
>
プログラミングの実験