スクリプト言語作成のきっかけ
文法をパースするプログラムを自作してみたところ正規表現でパースできないことがわかった。
正規表現は有限回の文法をパースできるが無限回の文法をパースできないことが原因だ。正規表現の限界を感じた。
BNFのBisonなら無限回の文法をパースできるのでBisonを使ってみようと思った。
Yash
Bison記述が爆速化するVisual Studio Codeの拡張機能。
Flex/Bisonの構文を強調表示するだけでなく、自動的なコード診断でエラー表示するリンターでもある。
Bisonを使ってみた感想
Yaccが1970年代、Bisonが1980年代に開発された。歴史のあるパーサー生成器だ。
月並みな表現だがBisonはすごいと思った。BNFを受け付ける範囲が広い。+や**などで演算子の優先順位や結合法則を気にして異なる非終端記号を使ってBNFを記述するのかと思っていたが、同列に記述できた。マニュアルに、異なる演算子の相対的な優先順位は、それらが宣言される順序で決まるとある。
var変数とクロージャ関数を作った
JavaScriptのようなvar変数を作った。関数呼び出しにC++のmapを付けることでvar変数を作った。
後からクロージャ対応するのは二度手間になると思ったので最初からクロージャ対応した。関数呼び出しの戻り値が関数ならmapを保持したままにするようにした。異なる関数呼び出しは異なるmapを保存するようにした。
スクリプト言語作成の感想
メモリリークのデバッグが大変だった。
デバッガで調べる方法ではメモリリークの原因を特定できなかったが新たなデバッグ法で解決した。その方法とはデバッグのためにプログラミングすることだ 
メモリリーク問題
フィボナッチ数の計算でメモリが1ギガを超えた 
C++のmapによるメモリリーク対策
mallocのアドレスをキーにして型ごとにC++のmapに登録し、freeしたらmapから削除する。これによりfreeされず残ったmallocの数が型ごとにわかる。
実行後に数が多いことでメモリリークが起きたことはわかったが、原因を特定できなかった。実行するたびにメモリのアドレスがランダムに変わるからだ。
ASLRと自作mallocによるメモリリーク対策
ASLR(address space layout randomization)とはアドレス空間配置のランダム化のことだ。
gccなら-Wl,--disable-dynamicbaseで、clなら/link /DYNAMICBASE:NOのオプションでメモリのアドレスがランダムになるdynamicbaseの機能を無効化した実行ファイルを作成できる。peflags -vで実行ファイルからdynamicbaseのフラグが消えることを確認できる。
私の環境では、大域変数のメモリアドレスを固定化できたが、mallocのメモリアドレスを固定できなかった。
大域変数に大きな領域を取ってメモリを割り当てる単純なmallocを自作した。mallocのアドレスが大域変数になりメモリアドレスを固定化できた。
メモリリークの疑いのあるメモリアドレスをmallocかfreeする場所でブレークポイントを設定することができ、メモリリークの原因を特定できた。
車輪の再発明のススメ
車輪の再発明はよくないという格言があり、mallocを自作しようと思わないかもしれない。var変数を作るときC++のmapを使った。
しかし、格言に例外もありえる。メモリリークの原因を特定できたようにmalloc自作は可能性を広げると思う。標準のmallocはプログラマーが期待する機能を提供していないと思う。バッファオーバーフローを防ぐためメモリ参照ごとに範囲チェックをしたら役に立ちそうだと思う。
参考
- パース IT用語辞典 e-Words
- AddressSanitizer LinuxやOS Xで動作するバッファオーバーフローなどの検知ツール。
- Linux: mallocで返されるアドレスを固定する Linuxでmallocアドレスを固定できるという記事。
- Bison のマニュアルの日本語訳
まとめ
Bisonを使ってスクリプト言語を作成してみた。デバッガで調べる方法ではメモリリークの原因を特定できなかったが、自作mallocで解決した。
GitHubリポジトリ: QKumaScriptのソースコード