シェルに時刻を表示する最強の方法
この記事は dotfiles Advent Calendar 2019 - Qiita の25日目の記事です。 zshに関する話題です。
今日は某有名人の誕生日ということで、時刻に関する話題を扱いたいのですが、 UNIXのシェルを操作する場面では
- 今何時？
- あのコマンド叩いたのいつだっけ？
- コマンドの実行に何分かかった？
これらの時間を意識することが多いでしょう。
そんなとき、今何時か知りたければdateと叩き、コマンドの開始時刻を知りたければhistoryで検索し1、実行時間の計測にはtimeを使うというのが、古式ゆかしいUNIXのシキタリといえます。
たくさんあってややこしいですね！
例として、sleep 5というコマンドの実行時間を測ってみましょう。
もちろん5秒ジャストになるはずなのですが、これを計るにはコマンドの前方にtimeと書く必要があります。
$ time sleep 5 sleep 5 0.00s user 0.00s system 0% cpu 5.008 total
こんな感じで実行時間を計測できます。
どうやらsleep 5の実行には5.008秒を要したようです。
5秒ジャストじゃないんだ。へ～～
ところがこのtimeは癖者で、ついつい
「うわ！！コマンドの実行時間を測りたかったのに、timeをつけ忘れた！！でももう実行してから何時間も経ってるし、ここで止めてやり直すのはヤダナ～」
みたいになりがちです。
$ sleep 10000d
$
↑実行に10000日を要するコマンドが、無事完了して感無量なのですが、しかしtimeをつけ忘れるという痛恨のミスをやらかした図。このタイムロスは痛すぎる。。。
改善方法
timeのつけ忘れを防ぐのは簡単です。
そもそもtimeコマンドを使わなければよいのです。
代わりに
シェルのプロンプトに現在時刻を表示
すれば問題が解決します。
実行前のプロンプトの時刻と、実行後のプロンプトの時刻を比較(引き算)すれば、コマンドの実行時間が計算できます。
こうすることで、冒頭の「今何時？あのコマンド叩いたのいつだっけ？」という疑問まで解決するし、一挙三得で超うれし～～
というような記事が量産されているのですが、私の読んだ限り、イマイチな設定例が多いように思われます。 普通にコマンドの終了時刻を表示している例が多いわけですが、、、、、
考えろ！考えるんだっっ！！よくよく考えると、我々はUNIXシェルの前で
- 前回のコマンドが終わる (プロンプトに入る)
- キーボードを叩いて、次回のコマンドを入力
- エンターキーを、ｯﾀｰｰﾝ!!!
- 次回のコマンドが始まる (プロンプトから出る)
つまりプロンプトに入る時刻(1)と、出る時刻(4)は別物です。 これら両方を知っておかないと、コマンドの実行時間は計測できません。 そう、つまり、我々は、入室と退室の2つの時刻を表示する必要に迫られているのです。 それこそが論理的に正しく、真にあるべき姿だと言えましょう。
要するに、欲しいのはコレだ！！
- 左側の数字が、プロンプトに入った時刻(前回のコマンドが終了した時刻)です。
- 右側の数字が、プロンプトから出た時刻(次回のコマンドを開始する時刻)です。
図の読み方ですが、簡単な引き算で諸々に費やした時間を計算できます。
コマンドに色がついてるのは zsh-syntax-hilighting のおかげですが、今回の記事にはあまり関係ないですね。
さて設定方法ですが、以下の設定を$HOME/.zshrcに記述すれば実現できます。
export PREV_COMMAND_END_TIME export NEXT_COMMAND_BGN_TIME function show_command_end_time() { PREV_COMMAND_END_TIME=`date "+%H:%M:%S"` PROMPT="${PREV_COMMAND_END_TIME} - $ " } autoload -Uz add-zsh-hook add-zsh-hook precmd show_command_end_time show_command_begin_time() { NEXT_COMMAND_BGN_TIME=`date "+%H:%M:%S"` PROMPT="${PREV_COMMAND_END_TIME} - ${NEXT_COMMAND_BGN_TIME} $ " zle .accept-line zle .reset-prompt } zle -N accept-line show_command_begin_time
もっとクールにしたい
ここまで見てきた設定で、時刻が表示されて嬉しいわけですが、なんかダサい。 そこで私は以下のような設定で生活しています。
# 色の設定。^[はエスケープ文字 COLOR_BGN="%{^[[044m%}" # 青色。数字を変えて、サーバー毎に色を変えよう COLOR_END="%{^[[m%}" COLOR_DEFAULT="%{^[[000m%}" # gitのブランチ名を表示するための設定 autoload -Uz vcs_info setopt prompt_subst zstyle ':vcs_info:git:*' check-for-changes true zstyle ':vcs_info:git:*' stagedstr "%F{yellow}!" zstyle ':vcs_info:git:*' unstagedstr "%F{red}+" zstyle ':vcs_info:*' formats "%F{green}%c%u[%b]%f" zstyle ':vcs_info:*' actionformats '[%b|%a]' precmd () { vcs_info } # コマンドの開始終了時刻を表示するための設定 export PREV_COMMAND_END_TIME export NEXT_COMMAND_BGN_TIME function show_command_end_time() { PREV_COMMAND_END_TIME=`date "+%H:%M:%S"` PROMPT="${COLOR_BGN}${PREV_COMMAND_END_TIME} - %/${COLOR_END} "'${vcs_info_msg_0_} '"${COLOR_BGN}\$${COLOR_END}${COLOR_DEFAULT} " } autoload -Uz add-zsh-hook add-zsh-hook precmd show_command_end_time show_command_begin_time() { NEXT_COMMAND_BGN_TIME=`date "+%H:%M:%S"` PROMPT="${COLOR_BGN}${PREV_COMMAND_END_TIME} - ${NEXT_COMMAND_BGN_TIME} %/${COLOR_END} "'${vcs_info_msg_0_} '"${COLOR_BGN}\$${COLOR_END}${COLOR_DEFAULT} " zle .accept-line zle .reset-prompt } zle -N accept-line show_command_begin_time
この設定により、カレントディレクトリのパスと、gitのブランチ名が表示されるようになります。 またプロンプトの背景色が青で着色され、視認性が高くなっています。
これを同僚に見せると「なんかお前の画面、ごちゃごちゃしててキモい...」と言われがちなのですが、しかしこの時刻表示こそ自明に最強であることが明らかなので、全世界が間違ってて私だけが真理を見極めているのだと思います。
予期される反論への反論
「今回の記事の方法でコマンドの実行時間を計測すると、1秒前後の誤差が含まれるじゃないか。俺はミリ秒単位の精度が必要なんだ！！timeコマンドは必要だ！！」
という意見が、競プロ等の界隈から来そうな気がします。
そういうミリ秒レベルの計測値が欲しい場合は、素直にtimeコマンドを叩くのがよろしいと思います。
今回の記事で対象としているのは「実行時間の長いコマンド」の時間計測です。
こうした状況では、有効数字の観点から、ミリ秒単位の精度が要求されることは稀だと思います。
誤差1秒程度なら許されるでしょう。
言い換えると、ミリ秒の精度が要求されるコマンドは、実行時間も短時間(せいぜい数十秒)のはずです。
短時間で終わるので、timeをつけ忘れたときの再実行コストは大したことありません。
そうした短時間のコマンドを実行する場合でも、今回の記事の設定をしておくことで
「コマンドが実行された時刻」
がコンソールバッファに残ります。
いつ何の作業をしたのか分かるのは、それなりに嬉しいことだと思います(historyを適切に設定しろという話ではありますが)。
「長時間計測のtimeつけ忘れを改善したいのなら、素直に zsh-command-time プラグインを使えや」
という反論は、極めて妥当だと思います。
私は全コマンドの実行開始・終了時刻をバッファ内に残したい派閥に属しているので、今回の設定を使っています。
このあたりの価値観は様々で喧嘩しても仕方ないので、お互い尊重して生きていきましょう。
あと冒頭のsleep 10000dを計るには、時刻だけではなく年月日も表示しないといけませんね。
さすがにそこまで表示するのは冗長な気がするので、私は時刻だけ出していますが、このあたりも好き好きといったところでしょうか。
-
bash3.0以降で、かつHISTTIMEFORMATを設定しておかないと、コマンド開始時刻の検索は不可能なようです。↩
25日目: 自作コンパイラ、自作エミュ、自作CPUの結合
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の25日目の記事です。
いよいよ最終日。
まず復習を兼ねて、今までの記事を振り返りながら、C言語から半導体までCPUの中を歩く。
最後に自作コンパイラ、自作エミュレータ、自作CPUを結合し、再帰関数でフィボナッチ数を計算する。
25日間の復習
アドベントカレンダーの 初日の記事 に
「普段目にする抽象的なプログラムコードから、CPU内の電圧変動が想像できるようになりたい。」
と書いたので、今までの記事を見返しつつ、C言語から半導体までレイヤーを降りてみる。
C言語からアセンブラまで (18日目-24日目)
C言語のサンプルコード
int main () { int a ; a = 3 ; return 0 ; }
これを1週間かけてアセンブラに変換した。 作ったコンパイラのリポジトリはこれ。
(18日目) コンパイラ概論
(19日目) 字句解析
BNFと呼ばれる、代入可能な正規表現を用いて属性を定義する表を導入した。 これを使ってソースコードに含まれる全単語に属性を付けた。
(20-21日目) 構文解析
トークンの列を構文解析して解析木に変換した。 構文解析に用いたBNFと、再帰降下アルゴリズムで生成された解析木を貼っておく。
(22日目) 抽象構文木
前日の解析木から、冗長な情報を削除した抽象構文木を作った。
(23日目) シンボルテーブル
前日の抽象構文木から、宣言系のノードをまとめたテーブルを作った。
(24日目) コード生成
抽象構文木とシンボルテーブルから、x86のアセンブラのコードを作った。
まず以下のようなテンプレを用意した。
抽象構文木をテンプレに突っ込んで生成された、アセンブラのコードは
bits 32 org 0x0 jmp _main_ _main_: push ebp mov ebp, esp sub esp, 0x10 mov eax, 0x3 ... (以下略) ...
これでコンパイラの内部処理を一通り追うことができた。
ここで本来は、アセンブラのコードをx86の機械語に変換するためのリンカを用意しなければならない。 しかし制作意義を見いだせなかったので、gccのリンカを使うことにした。自作したければ、↓の表を見れば簡単に作れる。
アセンブラから「動作」まで (11日目-17日目)
これらの問題と格闘した。
(11日目) x86の概要
結局、以下の機械語が得られる。
eb 00 55 89 e5 83 ec 10 b8 03 00 00 00 50 89 45 fc b8 00 00 00 00 50 58 eb 00 f4
(12日目) 数値の扱い
x86で数値を扱う際の注意点をまとめた。リトルエンディアンが気持ち悪かった。
(13日目) ModRM
「誰と誰を足すか」を指定するためのオプションを説明した。
(14日目) 関数呼出
関数呼出にはcall、leave、retの3命令を用いるのだった。
これらはスタックメモリへのpushとpop、そしてmovとjmp命令の組み合わせに過ぎなかった。
(15日目) x86エミュレータの製作開始
リポジトリはこれ。 初日なので大枠を作った。メモリ地図が重要だった。
(16日目) x86エミュレータが完成
昨日作った大枠から呼び出される、機械語の解釈器を作った。全体が完成した。
(17日目) x86 CPUをFPGAで実装
リポジトリはこれ。 実際に作ったのはアドベントカレンダーの開始直前。 ツイッターがバズって驚いた。
twitter.com昨晩からx86-80386のCPUをFPGAで自作してるんだけど、ようやくMOV命令が動いた。あと半日あればかなりの量の命令が実装できる気がする。FPGA慣れてきた。#低レイヤ pic.twitter.com/L7oZSvx4aF
— 解答略 (@kaitou_ryaku) 2017年11月25日
以上の工程で、自作コンパイラと、x86風の自作CPUが完成した。この記事の一番下で、これら2つを組み合わせて動作させる。
独自命令セットのCPUの製作(8日目-10日目)
↑でx86風のCPUが完成したわけだが、これはかなり複雑で作るのが大変だった。 そこで今回のアドベントカレンダーでは、x86に取り掛かる前に、プロトタイプとして簡単な命令セットのCPUを作ったのだった。
(8日目) 命令セットの策定
mov, add, sub, cmp, push, pop, jmp, jz, jnz, hlt
の命令セットを持つ8bitのCPUを定義した。
命令の種類は少ないが、十分な汎用性を備えており何でも計算できる。
(9日目) 独自命令セットCPUの製作開始
リポジトリはこれ。 エミュレータ製作の初日と同様に、大枠を作った。 メモリやクロックを用意し、CPUと電圧値をやりとりできるようにした。
(10日目) 独自命令セットCPUが完成
エミュレータ製作の二日目と同様に、機械語の解釈部分を作った。
これは組み合わせ回路になるので、HDLのalways_combブロック内に書く必要があった。
完成後、とりあえずフィボナッチ数を計算した。
twitter.comCPU自作アドベントカレンダー！！ついにCPUが完成しました！！HDLを500行書くだけで、加算減算,if,while,ローカル変数,関数定義呼出の可能なCPUが作れるのです。機械語のmov,add,sub,cmp,push,pop,jmp,jccさえ実装すれば、CPUとコンパイラが繋がります。動画はフィボナッチ計算https://t.co/PieYgoTg50 pic.twitter.com/SfSjxkYaL0
— 解答略 (@kaitou_ryaku) 2017年12月10日
機械語からDフリップフロップまで(4日目-7日目)
CPUの回路構成の説明に全力投球した。
極論すると、CPUはDフリップフロップのループであった。
(7日目) 本格的なCPUの回路構成
要するにCPUとは、メモリに格納された機械語を取得し、実行し、取得し、実行し、、、を繰り返す回路だった。
右の線はメモリに繋がっている。 カウンタには読み込むべきメモリのアドレスが保持されている。 命令の実行が終わると「+1」でインクリメントされる。
メモリも含め、コンピュータの全景を一枚にまとめると
(6日目) ALU
ALUとは計算回路のことだった。
特に複数桁を足すための全加算器が重要だった。
(5日目) レジスタの選択
計算回路はCPUの本質ではない(超暴論)ので、取り外して考えると、
mov命令だけが実行できるCPUになる。
見やすさのためにメモリも取っ払うと
これは変数 a, b, c, dの間で値をコピー(mov命令)する回路だ。
コピー元は線Syの電圧値で指定し、コピー先を線Sxの電圧値で指定する。
メモリはこれらの線に繋がっている。
つまり機械語(バイナリ)は、SxとSyの電圧値に対応している。
指定に用いたMUXはマルチプレクサと呼ばれる回路素子で、if 文的な役割を果たしている。
(4日目) 1bit反転CPU
マルチプレクサはCPUの本質ではない(超暴論)ので、取り外して考える。
見やすさのために変数を1種類(aだけ)にする。
さらにNOTゲートを挟むと
今まで変数と読んできた長方形は、Dフリップフロップと呼ばれる回路素子だ。
- クロックが上がる瞬間に、入力(D)が出力(Q)にコピーされる
- その瞬間以外は、入力を変えても出力は変わらない
という性質を持つ。結果、回路の挙動は
CPUとは、このように代入→計算→代入→計算→...を繰り返す回路のことだった。
極論すると、CPUとは、Dフリップフロップの出口を入口に繋いだループ回路である。
Dフリップフロップから半導体まで(2,3日目)
(3日目) Dフリップフロップ
Dフリップフロップの実装は
つまりNANDゲートとNOTゲートで構成されている。
(2日目) 半導体素子
NANDゲートとNOTゲートの実装は
NOTゲートの回路を、簡略化せずにきちんと描くと
ここに出現するトランジスタは、p型半導体とn型半導体を組み合わせて、以下のように作られている。
さらに下の階層に進むには、量子力学と統計力学の知識が必要になる。 本気でやるなら、周期ポテンシャル下の(多体相関を繰り込んだ)シュレディンガー方程式を解いて、バンド図を描き、輸送係数を調べる必要がある。
以上で低レイヤの解説は終了。
最後に、今までに作成したものを結合してみる。
自作コンパイラ + 自作エミュレータ
10番目のフィボナッチ数を計算するコード(C言語)
int fib(int n); int main() { // 10番目のフィボナッチ数を計算 int a; a = fib(10); return a; } // 再帰的にフィボナッチ数を計算 int fib(int n) { int ret; // ここに計算結果を入れる // 前回と前々回のフィボナッチ数を足す if (n > 2) { ret = fib(n-2) + fib(n-1); } // fib(1)とfib(2)は1とする else { if (n == 2) { ret = 1; } else { if (n == 1) { ret = 1; } } } return ret; }
要するに変数aに10番目のフィボナッチ数を代入するプログラムだ。
else ifが実装されてないので少々読みにくいが、我慢して欲しい。
これを自作コンパイラの minc (リポジトリ) でコンパイルする。
$ ./minc.out fibonacci.c fibonacci.asm
これを機械語に変換して 自作x86エミュレータ (リポジトリ) 上で実行すると
$ nasm fibonacci.asm -o fibonacci.bin
$ ./x86-simulator.out fibonacci.bin
実行結果の末尾を見てみると
Count : 005078 Operation: 00001E : 0xE9 (jmp imm32) --- FLAG --- CF:0 ZF:0 SF:0 OF:0 --- REGISTER --- eax: 0x00000037 ecx: 0x00000000 edx: 0x0000000A ebx: 0x00000000 esp: 0x000003E8 ebp: 0x000003FC esi: 0x00000000 edi: 0x00000000 eip: 0x000000E2 --- STACK MEMORY --- 0003E0: FC 03 00 00 37 00 00 00 37 00 00 00 00 00 00 00 0003F0: 00 00 00 00 00 00 00 00 37 00 00 00 00 00 00 00
重要なのはREGISTERの部分。
eaxの値が0x00000037になっている。
つまり16進数で37、10進数だと16*3+7で55になる。
ところでフィボナッチ数は
1, 1, 2, 3, 5, 8, 13, 21, 34, 55
おお！！10番目のフィボナッチは55だ。 エミュレータで正しく計算できているし、コンパイルには成功したようだ。
命令実行回数はCount: 005078で、約五千回程度。
自作コンパイラ + 自作CPU
さっきのコードを機械語にして自作CPU (リポジトリ) で動かしてみる。
波形シミュレータによる結果は
eaxに0x00000037が入ってる。正しくフィボナッチ数が計算できたようだ。
命令の終了時刻は、約50,780ナノ秒だ。 1クロック10ナノ秒なので、エミュレータによる命令実行回数に一致している。 これは作成したCPUがシングルクロックプロセッサ、つまり1クロック毎に1つの機械語命令を実行しているせいだ。 普通のCPUだと「クロック数 = 命令実行数」みたいな対応関係はないので、注意する必要がある。
これをFPGAの実機で動かしたい。。。が、無理だった。 CPU回路の論理合成には成功したものの、メモリ容量が足りず、インプリメントに失敗した。
(以下は完全に推測だが)メモリが足りなかったのはシングルクロックプロセッサが原因ではないかと考えている。 今回のCPUは1クロックでフェッチすべきメモリデータが多すぎて、データバスが120本という意味不明な構成になっている。 その結果、論理合成時にメモリ機能をフリップフロップで構成しようとして、資源が足りずにエラーをはいてる気がする。
解決するには、1クロックで1byteずつフェッチするようなステートマシンを作ってアドレスバスの本数を減らせば、メモリがメモリアレイで構成されて、問題が解決する。かも。
まぁでも波形シミュレータ上では動いてたし、よしとしよう。 そもそもフィボナッチは 10日目に作ったFPGAのCPU で既に動いてる(下のツイート)し。 全然悔しくないもん(悔しい)1。
twitter.comCPU自作アドベントカレンダー！！ついにCPUが完成しました！！HDLを500行書くだけで、加算減算,if,while,ローカル変数,関数定義呼出の可能なCPUが作れるのです。機械語のmov,add,sub,cmp,push,pop,jmp,jccさえ実装すれば、CPUとコンパイラが繋がります。動画はフィボナッチ計算https://t.co/PieYgoTg50 pic.twitter.com/SfSjxkYaL0
— 解答略 (@kaitou_ryaku) 2017年12月10日
最後に
予想外に多くの方々に読んでいただけたようで、感無量です。
最後に一言だけ。
一連の記事は、あくまで私的なメモです。
初心者が書いた記事なので、誤りが多数含まれているはずです。 この記事を盲目的に信じるのはマジでヤバイので、しっかりした教科書を読むべきです。
それでは25日間、ありがとうございました。
24日目: [コンパイラ] コード生成
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の24日目の記事です。
一昨日は抽象構文木を作り、昨日はシンボルテーブルを作成した。 これらを元にアセンブラのコードを吐き出せば、コンパイラは完成だ。
この最後の工程をコード生成という。 難しい話はないものの、説明すべき内容が多い。 まず第一部として制御フローのコード生成を説明し、第二部で計算関連を説明することにする。
第一部:制御フロー
制御フローというタイトルだが、拡大解釈して計算以外の全処理のコード生成をここで解説する。
抽象構文木をアセンブラのコードに変換する命令は
main関数
内で
// main関数内 // 空のシンボルテーブル TABLE tb[MAX_HASH_NUMBER]; // srcは抽象構文木の構造体 // fileは出力ファイルポインタ asm_program(file, src, tb);
で呼び出される
asm_program関数
によってスタートする。
この関数は以下のテンプレートに従って抽象構文木をx86のニーモニックに変換する。
bits 32 org 0x0 jmp _main_ * -- LOOP BEGIN (PROGRAMノードに生える関数ノード N でループ) * * 1. シンボルテーブルにNの引数とローカル変数を追加 * * 2. asm_function(N) で処理を書き出す * * 3. N が main関数なら、最後を * jmp _program_halt_ * で終える * * 4. N が main 以外の関数なら、最後を * leave * ret * で終える * * 5. シンボルテーブルから N の引数とローカル変数を削除 * -- LOOP END _program_halt_: hlt * グローバル変数の数だけ dd 0x0 * を書く
このコードを上から辿ると
bits 32とorg 0x0はおまじない- 次の
jmp _main_でmain関数にジャンプするが、それは LOOP の内側にいる main関数が終了すると、_program_halt_に飛ぶhlt命令でCPUが停止する
となる。C言語を実行してる雰囲気がつかめると思う。
最後のdd 0x0命令は、単純に
0x00 0x00 0x00 0x00
という4byteの機械語に変化する命令だ。
こうすることで、ゼロで初期化されたグローバル変数が関数本体の後ろに設置される。
関数
前節のPROGRAMノードのテンプレートを見ると、関数処理の書き出しは
asm_function関数
で行われていた。
こいつは以下のテンプレートに基いてコードを生成する。
push ebp mov ebp, esp sub esp, スタックフレーム * -- LOOP BEGIN * FUNCTIONノード直下の、V_DEC以外のノードの処理を * asm_sentence() で書き出す * -- LOOP END
スタックフレームはローカル変数の領域を確保する処理だった。
要するにローカル変数の数 * 4だけespを引けば良い。
ローカル変数の数は、シンボルテーブルを走査すれば容易く計算できる。
この辺の詳しい解説は
昨日のシンボルテーブル記事
の最後に載せた。
ついでにRETURNノードの書き出しも見ておこう。
処理は
asm_return関数
で行っているのだが、テンプレートは
* 返り値をスタックに積む pop eax
シンプルだ。 これで良い理由は 関数呼出の記事 を参照して欲しい。
ちなみにこれは手抜き実装なので、関数末尾以外のreturn文は破綻する。仕様というかバグに近いな。
文
前節で、関数の中身を書き出す処理は
asm_sentence関数
に一任していた。
これはテンプレートではなく実装を貼った方が分かりやすい。
void asm_sentence(FILE *fp, NODE *sentence, SOURCE s, TABLE *tb) { if (sentence != NULL) { const int kind = sentence -> kind; // 文の中に文がある場合 if (kind == SENTENCE) { NODE *down = sentence -> down; // 再帰呼び出し while (down != NULL) { asm_sentence(fp, down, s, tb); down = down -> right; } } // 実質的な処理 else if (kind == IF_FLOW) asm_if( fp, sentence, s, tb); else if (kind == WHILE_FLOW) asm_while( fp, sentence, s, tb); else if (kind == RETURN) asm_return(fp, sentence, s, tb); else if (kind == ASSIGN) asm_assign(fp, sentence, s, tb); else if (kind == CALL) asm_call( fp, sentence, s, tb); else syntax_error(__func__); } }
この関数の挙動を二言で言うと
- 文の中に文がある場合は、再帰的に
asm_sentence自身を呼び出し、どんどんもぐる - ifやwhile、代入文であれば、専用の書き出し関数
asm_***に処理を丸投げ
さっきreturn文は解説したので、その他のif, while, assign, call文の書き出し関数を見てみよう。
if文
asm_if関数
の処理を見てみる。
まず条件文を処理するテンプレートを見ると
* 条件の部分をasm_expr()に投げる。結果がスタックに積まれる pop eax cmp eax, 0
要するに条件式と0を比較している。
条件式の計算を行うasm_expr関数は、第二部の計算パートで扱うことにしよう。
次に、構文がif (...) {...}型の場合のテンプレートを見てみる。
je LABEL@IFNUM@_if_end * asm_sentence() で {...} の部分を書き出す LABEL@IFNUM@_if_end:
さっきの条件式が0なら{...}の部分がスキップされる。
これはC言語の
if (0) {実行されない} ここに飛ぶ if (0以外) {実行される} 終わったらここに進む
という分岐フローに対応している。
ちなみに@IFNUM@は"if"文字列のトークン番号を指す。
この数字は、ソースコード内に出現する複数のif文を区別するためのものだ。
@IFNUM@無しでは、異なるif文のラベル名が重複してしまう。
次に構文がif (...) {...} else {...}のテンプレートを見てみる。
je LABEL@IFNUM@_else * asm_sentence() で else節 の {...} の部分を書き出す jmp LABEL@IFNUM@_if_end LABEL@IFNUM_else: * asm_sentence() で if 節の {...} の部分を書き出す LABEL@IFNUM@_if_end:
さっきとほぼ同じなので、説明不要だと思う。
while文
asm_while関数
で用いるテンプレートは
* 条件の部分を asm_expr() に投げる。結果がスタックに積まれる pop eax cmp eax, 0 je LABEL@WHILENUM@_while_end LABEL@WHILENUM@_while_begin: * while {...} の中身の処理を asm_sentence() に投げる * 条件の部分を asm_expr() に投げる。結果がスタックに積まれる pop eax cmp eax, 0 jne LABEL@WHILENUM@_while_begin LABEL@WHILENUM@_while_end:
前節のif文の処理が理解できれば、while文の仕組みも分かるだろう。
ifの場合と同様に、asm_expr関数で条件式を計算して0と比較し、je命令でジャンプしている。
条件式が0だった場合は、C言語の
while (0) {実行されない} ここにジャンプ
という処理が実現する。
条件式が0以外だった場合は、while {...}の中身を実行する。
その後再び条件式を評価し、もし条件式が0ならジャンプせずループを抜ける。
条件式が0以外だった場合は、while {...}の{あたりにジャンプし、ループが再開する。
代入文
代入文の
asm_assign関数
で使用するテンプレートを見てみる。
* 左辺の変数名をfprint_variable()でアドレスに変換 * 右辺をasm_expr()に投げる。結果がスタックに積まれる mov [左辺のアドレス], eax
要するに
fprint_variable関数
で指定される場所に、右辺の結果をmovしている。
この関数の実装は
void fprint_variable(FILE *fp, NODE *var, SOURCE s, TABLE *tb) { int hash = search_hash(var, tb, s); if (hash < 0) { fprintf(fp, "\n"); syntax_error(__func__); fprintf(fp, "hash:%d str:%s\n", hash, s.token[var -> init].str); } int block = tb[hash].block; if (block == 0) fprintf(fp, "[_%s_]" , tb[hash].str); // グローバル変数 else if (block == 1) fprintf(fp, "[ebp+0x%x]", tb[hash].address); // 関数の引数 else if (block > 1) fprintf(fp, "[ebp-0x%x]", -tb[hash].address); // ローカル変数 }
変数名でシンボルテーブルを検索し、スコープに応じてアドレスを書き出している。 グローバル変数と引数とローカル変数でアドレスの形式が異なるが、これはcdecl規約やスタックフレーム等の絡んだややこしい話だった。 詳細は 昨日のシンボルテーブル記事 の最後の方で説明しておいた。
関数呼出文
関数呼出しを処理する
asm_call関数
のテンプレートを見てみる。
まず引数がない場合のテンプレート
call _呼び出す関数名_
明らかに説明不要なので、引数がある場合のテンプレートを見てみる。
* LOOP BEGIN * 関数呼出の引数を、右側から順に * 全て asm_expr() に投げる。 * 計算結果は自動でスタックに積み重なる * LOOP END call _呼び出す関数名_ * LOOP BEGIN (引数の数だけ) pop edx * LOOP END
まず最初に、cdecl規約に従って右側の引数から順にスタックに積む。 意味が分からなければ 関数呼出の記事 を読み直して欲しい。
次にcall命令で関数を呼び出す。
最後に、引数の数だけpop edxを行っている。
これは引数として積んだスタックを解放する処理だ。
この処理を忘れると、関数呼出しの度にスタックがどんどん増えてゆき、最終的にオーバーフローしてしまう。
ちなみにもう少しスマートに解放するには、add esp 引数の数*4とすればよい。
以上で制御フローの話は終了だ。 x86のニーモニックや関数呼出規約を知った上で読めば、何一つ難しいところはないと思う。
第二部: 計算
前セクションではasm_exprという関数が頻出していた。
これは「式」を受け取って計算結果をスタックに積む関数だが、実装は未説明だった。
ここからの目標は、asm_exprの実装を理解することだ。
スタックマシン
要するに数式をニーモニックに変換したいのだが、まずは簡単な
(0+2)+(4+(6+8))
という数式を考える。 これをC言語のコードだと思って抽象構文木を作ると
手で計算するのは簡単だが、x86のCPUにやらせるにはどうすれば良いだろうか。
素直に考えるとeax=0、ecx=2、edx=4のように各レジスタに値を割り振って計算するのが手っ取り早い。
しかしこの方法は、式中の項の数が増えた時に破綻してしまう。
レジスタの数は高々10個程度しかないからだ。
そこで、あえてレジスタの使用を最低限に留め、スタックを主体として計算する方法を考えてみたい。 スタックは無尽蔵に使えるので、項が増えても対応できるはずだ。
このような系をスタックマシン[^1]という(多分)。x86はスタックマシン的な扱い方ができる。 この系でさっきの計算を実行してみよう。
計算のアルゴリズム
スタックマシンによる計算の手順をgif動画にしてみた。
文章でアルゴリズムを説明すると
- どんどん左下に進む
- 左下の即値に到達したら、値をスタックに積み、ノードを削除
- 1つ上に戻り、1つ右下に移動し、さらにどんどん左下に進む
- 1-3を繰り返す
- 途中で右下の即値に到達したら、値をスタックに詰み、ノードを削除
- 演算を実行し、その結果で演算のノードを置換
みたいな感じだが、意味不明だと思うのでgif動画をしっかり見てくれ。 スタックマシンに搭載された2つのレジスタは、スタックに積まれた2つの即値を足す時に使用している。
ニーモニックで処理を記述すると
mov eax, 0x0 ; push eax ; 0をスタックに積んだ mov eax, 0x2 ; push eax ; 2をスタックに積んだ pop edx ; pop eax ; add eax, edx ; eax=0+2 push eax ; 2をスタックに積んだ mov eax, 0x4 ; push eax ; 4をスタックに積んだ mov eax, 0x6 ; push eax ; 6をスタックに積んだ mov eax, 0x8 ; push eax ; 8をスタックに積んだ pop edx ; pop eax ; add eax, edx ; eax=6+8 push eax ; 14をスタックに積んだ pop edx ; pop eax ; add eax, edx ; eax=4+14 push eax ; 18をスタックに積んだ pop edx ; pop eax ; add eax, edx ; eax=2+18 push eax ; 20をスタックに積んだ
C言語で記述
// 即値ならスタックに積む // 演算子ならasm_operatorを呼び出す void asm_expr(NOedxE *expr) { if (exprが即値) { printf("mov eax, 即値"); printf("push eax\n"); } else if (exprが加算演算子) asm_operator(expr); } // 左下と右下の各々をasm_exprで処理 // 右下が即値ならば、演算を実行し、結果をスタックに積む void asm_operator(NOedxE *ope) { NOedxE *down_left = ope -> down; NOedxE *down_right = down_left -> right; asm_expr(down_left ); asm_expr(down_right); printf("pop edx\n"); printf("pop eax\n"); if (opeが加算演算子) printf("add eax, edx\n"); printf("push eax\n"); }
ポイントは、asm_exprでasm_operatorを呼び出し、またasm_operatorからasm_exprを呼び出す部分。
つまり再帰関数になっている。木の探索でよく使うやつだ。
このコードは加算演算子しか書かなかったけど、減算や乗除に対応するには
if (exprが加算演算子)if (opeが加算演算子)
の部分に他の演算の処理を付け足せば良い。
減算ならaddの代わりにsub、乗算ならimul、除算ならidiv、剰余ならimodとすればよい。
変数と関数への対応
式中に変数や関数が含まれている場合を考える。
変数については、第一節の制御フローの代入文のところで説明したように、変数名を
fprint_variable関数 に入れることで値を取得できる。関数については、第一節の制御フローの関数呼出文の節で値の取得方法を解説した。
これらの方法で得られた値をスタックに詰めば、スタックマシンを用いた計算を継続することができる。
比較演算子の処理
例えばa==bは、aとbが等しい場合は1で、異なる場合は0と定義される(Cと同じ)。
こうした処理を実行するには、cmp命令と条件付きジャンプ命令を使えば良い。
cmp命令はsub命令を実行したと仮定してフラグだけを更新し、汎用レジスタは変更しない処理だった。
どちらも二項演算子であり、ニーモニックをadd命令からcmp命令に変更すればよい。
例として、aの値がeaxに入っていて、bの値がedxに入っている場合に、a==bの値をeaxに入れる処理は
cmp eax, edx ; eax-edxを実行したと仮定してフラグを更新 je _TRUE_ ; ゼロフラグが立っていればジャンプ。つまりeaxとedxが等しければジャンプ mov eax, 0 ; ジャンプしなかった場合は、eaxに0が入る jmp _END_ _TRUE_: mov eax, 1 ; ジャンプした場合は、eaxに1が入る _END_: ; いずれの場合もここにたどり着く
比較演算子と条件付きジャンプ命令を表にしておくと
| 比較演算子 | ジャンプ命令 |
|---|---|
| "==" | je |
| "!=" | jne |
| "<" | jl |
| "<=" | jle |
| ">" | jg |
| ">=" | jge |
冒頭の画像のB_OPERATORのノードは全て加算演算子だったが、もし数式中に比較演算子が出現したら、今説明した方法でeaxを作りスタックに積むことで計算が実行できる。
以上でコード生成は終了。コンパイラが完成した！
どうでもいい話
長かったアドベントカレンダーも、いよいよ明日で終了だ。 それにあわせて今日は大容量の記事になってしまった。 しかし中身は薄いので、苦労せずに終えると思う。
明日は自作コンパイラのコードを自作エミュ上で動かし、自作CPU上でも動かしてみる。 すべてが繋がる。
23日目: [コンパイラ] シンボルテーブル
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の23日目の記事です。
昨日は抽象構文木を作った。
これをアセンブラコードに変換できればコンパイラは完成だ。 変換の手順は、抽象構文木の最上段のPROGRAMノードから出発し、各ノードをニーモニックに置き換えていけばよい。
今日はその中で宣言系に関するノードを扱う。
やりたいこと
今日のサンプルコード(昨日までとは少し違う)
int g; int func(int a); int func(int a) { int c; c = 3; return a+c; }
の抽象構文木は以下のようになる。
着色したノードは宣言系のノードだ。
- 水色は宣言のノード
- 緑色は型と名前のノード
具体的には
- int型のグローバル変数
gの宣言 - int型の関数
funcのプロトタイプ宣言 - int型の関数
funcの宣言 - 関数
funcのint型の引数aの宣言 - 関数
funcのint型のローカル変数cの宣言
これらの宣言は、加算や代入といった具体的操作を表すわけではない。 むしろコンパイラに対し「XXの資源を利用したいです」と予約する感じだ。 コンパイラはこれらの予約情報を受け付けた後で、アセンブラのコードを生成しなければならない。
予約の受付はシンボルテーブルという仕組みで実装される。
今日の目標は、宣言系のノードをシンボルテーブルに変換することだ。
グローバルスコープ
宣言系のノードは大きく2つに分割できる。 PROGRAM直下に生えるグローバル(大域)スコープのノードと、そうではないローカルスコープのノードだ。
グローバルスコープのノードには 関数プロトタイプを表すPROTOTYPE と、 関数宣言を表す F_DEC と、 グローバル変数を表す V_DEC の3つがある。
グローバル変数だけを表示したツリーは
関数プロトタイプだけを表示したツリーは
変数名と関数名は、緑のVARIABLEノードとして抽象構文木に出現している。 このノードは変数名や関数名を表すトークン
- (IDENTIFY, "func")
- (IDENTIFY, "g")
で構成されている。
変数と関数の情報を名前をキーとする表にまとめておくと便利だ。 同一スコープの中で名前が被らないことは言語仕様で保証されているので、テーブルのユニークなキーに適している。 文字列をキーにするには少し工夫がいるが、こういう精神で作成した表のことをシンボルテーブルという。
シンボルテーブル
まずはグローバルな情報をまとめたシンボルテーブルがほしい。
| 名前 | スコープ | 種類 | 型 | サイズ | アドレス | トークン | ハッシュ |
|---|---|---|---|---|---|---|---|
| "func" | "GLOBAL" | 関数 | int | - | - | 4 | 365 |
| "g" | "GLOBAL" | 変数 | int | 4 | 0 | 1 | 287 |
関数プロトタイプのfuncと関数宣言のfuncは重複するので、1つにまとめている。
このテーブルは構造体配列で実装されており、右端のハッシュが配列の添字を表している。
シンボルテーブルの構造体 を見てみると
typedef struct { bool used; char *str; // token.str へのポインタ。"func" NODE *node; // 宣言のノード int kind; // V_DEC or F_DEC int type; // intなら0 int size; // V_DEC intなら4byteなので4 int token_index; // 変数を参照する際に、未宣言変数でないかチェックする用 NODE *root; // 宣言の存在する関数 (グローバルなら &(node[0])) char *root_name; // 宣言の存在する場所の名前(関数名 or "GLOBAL") int block; // 宣言の存在するブロックの深さ (引数なら0, 関数内の宣言なら1) int address; // ローカル変数なら [ebp-address] グローバル変数なら [address] } TABLE;
構造体メンバの意味はだいたい分かると思うので、非自明な部分だけ説明する。
sizeは、宣言ノードによって予約される資源が、メモリ上でどれだけの容量を占めるかbyte単位で表したものだ。 変数のサイズはint型なので4byteになる。 関数のサイズは機械語に変換した後でないと計算できないので、空欄になっている。
addressは、実行時にどのメモリアドレスに予約資源が格納されるかを表している。 実行時のメモリ配置は以下で与えられる。
メモリの0番地のあたりに関数を置いて、その後ろにグローバル変数を置いている。
ローカル変数のアドレスはややこしいので、説明を後に回す。
ハッシュマップ
シンボルテーブルは「名前で検索」するための表と言ったが、文字列そのものを配列添字にするのは難しい。 代替案として、文字列を数値に変換するハッシュマップというアルゴリズムを用いる。
例えば、関数funcの情報をシンボルテーブルに登録したいとする。
まずfuncという文字列を、何らかのアルゴリズムで非負整数(ハッシュ値)に変換する。
その後シンボルテーブル(という名の構造体配列)のハッシュ値番目に、関数の情報を書き込めば良い。
関数の情報を取り出すときも、登録時と同様に、まず関数名をハッシュ値に変換する。 次にシンボルテーブルのハッシュ値番目を見れば、関数の情報がめでたくゲットできるという仕組み。
文字列をハッシュ値に変換する処理は、
two_node_to_hash関数
で実装した。
static int two_node_to_hash(NODE *var, const int kind, SOURCE s) { char *str = s.token[var -> init].str; int hash = 0; for (int i=0; i<strlen(str); i++) { hash += str[i] * (((i+1)%2)*7 + ((i-1)%3)*11); } hash = hash*13 + kind * 23; if (hash < 0) hash = -hash; hash = hash % MAX_HASH_NUMBER; return hash; }
文字列strが与えられたとき、str[i]によってi番目の文字を0から127までの数値に変換できる。
この性質を用いて文字列を数値に変換している。コード中の3とか7とか11に深い意味はない。
何も考えず適当に実装したのだが、まぁ動くからええやろ。
ところで、文字列strを登録しようとしてハッシュ値HASH(str)を計算した結果、その番号が使用済みの場合がある。
そういう時はHASH(str)+1にstrの情報を登録することにした。
でもそんなことしたら検索時に見つからなくなりそうだ。
これを回避する方法がある。
strを検索するときは、まずHASH(str)の番号のハッシュマップを見に行く。
そこに登録されている文字列がstrと同じなら、その情報を取得すればいい。
異なっていれば、HASH(str)+1を見に行く。
こういう手順でハッシュの衝突を解決できる。
グローバルな情報をシンボルテーブルに登録
次はグローバル変数と関数プロトタイプをシンボルテーブルに登録する仕組みを作る。
これはmake_global_table関数
で実装されている。
void make_global_table(TABLE *t, SOURCE s) { for (int i=0; i<MAX_HASH_NUMBER; i++) { t[i] = initialize_table(); } int address = 0; fresh_tree(s); NODE *node = s.program -> down; while (node != NULL) { if (node -> kind == V_DEC) register_global_v( node, &address, t, s); else if (node -> kind == F_DEC) register_function( node, t, s); else if (node -> kind == PROTOTYPE) register_prototype(node, t, s); node = node -> right; } }
要するにPROGRAM直下の一層を左から右に走査している。 そして訪問した宣言ノードの種類に応じて、3種類の関数を呼び出している。
3つの関数は、シンボルテーブルtに宣言ノードの情報を登録するものだ。
例として
register_global_v関数
の実装を見てみると
void register_global_v(NODE *node, int *address, TABLE *t, SOURCE s) { NODE *var = node -> down -> right; int hash = get_empty_hash(var, V_DEC, t, s); // 同名の変数は無いはず assert( search_hash_by_condition(var, s.program, V_DEC, t, s) < 0 ); // 情報を登録 t[hash].used = true; t[hash].str = s.token[var -> init].str; t[hash].node = node; t[hash].kind = V_DEC; t[hash].type = 0; // intなら0 t[hash].size = INT_SIZE; t[hash].token_index = var -> init; // 変数を参照する際に、未宣言変数でないかチェックする用 t[hash].root = s.program; // 宣言の存在する関数 (グローバルなら &(node[0])) t[hash].root_name = "GLOBAL"; // 宣言の存在する場所の名前 t[hash].block = 0; // 宣言の存在するブロックの深さ // グローバルなら0 引数なら1 関数内の宣言なら2 t[hash].address = *address; // プログラム末尾からの差分 *address += INT_SIZE; }
まず最初に、変数名を表すノードvarを
NODE *var = node -> down -> right;
で取得している。
nodeがV_DECのノードであることを踏まえて下図を見て欲しい。
V_DECから下に降りると、左端のTYPEのノードに着く。
さらに右へ進むと、VARIABLEのノードに到着する。
このノードに対応するトークンは
(IDENTIFY, "g")
なので、変数名の"g"が得られた。
次にget_empty_hash関数で変数名をハッシュ値に変換している。
そして同名の変数が既に登録されていないかsearch_hash_by_condition関数でチェックしている。
この関数はシンボルテーブル全体を走査し、varノードに一致する名前の変数が登録されていれば、そのハッシュ値を返す。
見つからなければ-1を返す。
これらの準備の後に、ハッシュテーブルに値を登録している。
関数宣言と関数プロトタイプの登録についてもざっくり説明しておくと、
関数宣言用の
register_function関数では、まず同名の関数プロトタイプが既に登録されているか調べる。- もし登録されていなければ、関数の情報を普通に登録する。
- もし登録済みなら、まず引数が整合するかチェックし、その後シンボルテーブルに登録済みの関数プロトタイプのノードを関数本体のノードに置き換える。
関数プロトタイプ用の
register_prototype関数では、まず同名の関数が既に登録されているか調べる。- もし登録されていなければ、関数プロトタイプを普通に登録する。
- もし登録済みなら、引数が整合するかチェックし、不整合ならエラーを返す。
以上の処理を実行すると、抽象構文木から関数プロトタイプとグローバル変数のノードは不要になる。 残るのは
あとは関数の内部を解析するだけだ。
関数ローカルなシンボルテーブル
func関数の中を解析しよう。
欲しいのは以下のテーブルだ。
| 名前 | スコープ | 種類 | 型 | サイズ | アドレス | トークン | HASH |
|---|---|---|---|---|---|---|---|
| "func" | "GLOBAL" | 関数 | int | - | - | 4 | 365 |
| "g" | "GLOBAL" | 変数 | int | 4 | - | 1 | 287 |
| "a" | "func" | 引数 | int | 4 | 8+ebp | 12 | 475 |
| "c" | "func" | 変数 | int | 4 | -4+ebp | 16 | 79 |
前節で登録したグローバル情報に加え、新たにfunc関数の引数aとローカル変数cが登録されている。
このテーブルが作成された時点で、抽象構文木は以下のように簡約される。
残されたVARIABLEノードを黄色で示した。 これらのノードから「名前」の情報を用いてシンボルテーブルにアクセスすることで、 変数や関数を参照できる。
関数ローカルな情報を登録する処理は
make_local_table関数
で行っている。
void make_local_table( NODE *f_dec, TABLE *t, SOURCE s) { register_arguments(f_dec, t, s); // 引数の処理 register_local_var(f_dec, t, s); // ローカル変数の処理 }
2つの関数が呼び出されているが、どちらも前節で解説したregister_global_v関数とほぼ同じ。
異なるのはアドレスに関する部分だ。
引数の登録と関数呼出
まず引数を処理する
register_arguments関数
について、アドレスに関する部分だけを抜粋して見てみると
void register_arguments(NODE *f_dec, TABLE *t, SOURCE s) { NODE *v_dec = f_dec -> down -> right -> right; int address = 2*INT_SIZE; // INT_SIZEは4なので、初期値は8 while (v_dec -> kind != FUNCTION) { t[hash].address = address; // 8, 12, 16, ... address += INT_SIZE; v_dec = v_dec -> right; } }
これで
int FUNC(int a, int b, int c) { いろいろやる }
というサンプルコードを処理すると、以下のシンボルテーブルができあがる。
| 変数名 | TABLE構造体メンバのaddressの値 |
|---|---|
| "a" | 8 |
| "b" | 12 |
| "c" | 16 |
8,12,16の数字の意味がわかるだろうか？
たぶん意味分からんと思うので、 x86の関数呼出の記事を読み直して欲しい。
int a, int b, int cの3つを引数とする関数呼出をアセンブラで書くと
push cの値 ; 3番目の引数をスタックに詰む push bの値 ; 2番目の引数をスタックに詰む push aの値 ; 1番目の引数をスタックに詰む call FUNC ; 帰還するアドレスをメモしてFUNCにジャンプ ... ; いずれここに帰還 FUNC: push ebp ; 呼出時のebpをメモ mov ebp, esp ; 計算前のespをメモ いろいろやる 引数aの値は[ebp+8] で参照 引数aの値は[ebp+12]で参照 引数aの値は[ebp+16]で参照 leave ; espを計算前に戻し、ebpを呼出時に戻す ret ; 帰還し、espを呼出時に戻す
FUNCを呼び出す前に、c,b,aをpush- 帰還するアドレスをpush
- 呼出時の
ebpをpush mov ebp, espFUNCの内部処理開始
という順序で関数呼出を行う。
つまりebpの値と引数のアドレスの間には、帰還するアドレスと呼出時のebpの値が挟まっている。
これら2つのスタックをスキップして引数にアクセスするには
| 変数名 | メモリアドレス | 構造体メンバのaddressの値 |
|---|---|---|
| "a" | ebp+8 |
8 |
| "b" | ebp+12 |
12 |
| "c" | ebp+16 |
16 |
つまりTABLE構造体メンバのaddressの値は、ebpからの差分を与えているのだ。
ローカル変数とスタックフレーム
最後にローカル変数を処理する
register_local_var関数
も見ておく。
さっきと同様にアドレスに関する部分だけを抜粋すると
void register_local_var(NODE *f_dec, TABLE *t, SOURCE s) { NODE *func = f_dec -> down; int address = -INT_SIZE; // 初期値は-4 while (func != NULL) { if (func -> kind == V_DEC) { t[hash].address = address; // -4, -8, -12, ... address -= INT_SIZE; } func = func -> right; } }
今回も、TABLE構造体メンバのaddressはebpからの差分を表している。
たとえば
int FUNC() { int a; int b; int c; }
というコードから生成されるシンボルテーブルは以下のようになる。
| 変数名 | メモリアドレス | TABLE構造体メンバのaddressの値 |
|---|---|---|
| "a" | ebp-4 |
-4 |
| "b" | ebp-8 |
-8 |
| "c" | ebp-12 |
-12 |
これは、さっきの(引数処理の)アセンブラコードさえ理解できていれば、簡単に分かるはずだ。
アセンブラで考えると
call FUNC ; 帰還するアドレスをメモしてFUNCにジャンプ ... ; いずれここに帰還 FUNC: push ebp ; 呼出時のebpをメモ mov ebp, esp ; 計算前のespをメモ sub esp, 0x10 ; ローカル変数の容量を確保 ; 0xCでも良さそうだが、4byte単位で確保するルールらしい いろいろやる ローカル変数aは[ebp-4] で参照 ローカル変数bは[ebp-8] で参照 ローカル変数cは[ebp-12]で参照 leave ; espを計算前に戻し、ebpを呼出時に戻す ret ; 帰還し、espを呼出時に戻す
重要なのは7行目の
sub esp, 0x10
の部分。 これはスタックをむりやり4個押し上げる操作に対応する。 そうしてできたスタックメモリの空いたスペースに、ローカル変数を3つ詰め込んでいる。
「スタックの押し上げは3個で十分じゃないか？」という指摘は、完全に正しい。
僕もよく知らないのだが、4byte単位で押し上げるのが良しとされているようだ。
もしローカル変数が5個以上なら、sub esp, 0x100とする必要がある。
関数が複数ある場合
今回のサンプルコードでは関数が1つしかなかった。 複数の関数が存在する場合は、シンボルテーブルの更新とコード生成を交互に行う必要がある。
- グローバルスコープの情報をシンボルテーブルに登録
- 関数Aの引数とローカル変数を解析してシンボルテーブルに登録
- 関数Aをニーモニックに変換
- 関数Aの引数とローカル変数をシンボルテーブルから削除
- 関数Bの引数とローカル変数を解析してシンボルテーブルに登録
- 関数Bをニーモニックに変換
- 関数Bの引数とローカル変数をシンボルテーブルに登録
以上でシンボルテーブルの説明は終了。 関数呼出の手続きが理解できていれば、難しいところは全くないはずだ。
22日目: [コンパイラ] 抽象構文木
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の22日目の記事です。
昨日は頑張って解析木を作った。
今日は解析木の冗長性を省いて、抽象構文木を作る。
抽象構文木とは
昨日は以下のサンプルコードを構文解析した。
// C言語風コード int main () { int a ; a = 3 ; return 0 ; }
そして解析木が得られた。
この解析木は冗長すぎるので、簡単化したい。具体的には
- 水色で示したSKIP_NODEを削除
- 緑色で示した中身1個(つまり直下のノードが1個)のコンテナを、中身で置換
- 数式を二分木に変換
SKIP_NODEは、BNFに基いて構文解析する際に無視すべきトークンを、無理やりノード化したものだった。削除しても問題ない。 この辺の詳細は 一昨日の記事 の一番下に書いた。
コンテナは僕が勝手に命名したノード群で、SENTENCE, EXPRESSION, FORMULA, TERM, FACTORの5つを指している。 これらは複数の処理をまとめたノードであり、処理そのものを表すノード(B_OPERATORとかASSIGNとか)とは性質が異なる。 コンテナの中身が一つしかなければ、コンテナは必要ない。
数式の二分岐化については、複雑なのであとで説明する。
これらを処理して解析木をシンプルにしたツリーを抽象構文木という[^1]。
だいぶすっきりした。
抽象構文木の作成命令
まず
main関数
の中で、
昨日作ったPROGRAMノードをSOURCE構造体でラップした。
SOURCE src; src.program = node; src.max_node_num = node_index; src.token = token; src.max_token_num = max_token_num;
SOURCE srcは解析木を走査するための構造体だ。
解析木を構成するNODE構造体に、配列長などの走査時に必要な情報を付け加えたものになっており、
common.h
で宣言されている。
本質はNODEの構造体と同じだ。
typedef struct { NODE *program; // 木の最上段のPROGRAMノード int max_node_num; // NODE配列のサイズ TOKEN *token; // 字句解析結果のトークン配列 int max_token_num; // トークン配列のサイズ } SOURCE;
その後
main関数
から
abstract_tree関数
を呼び出し、NODE配列を解析木から抽象構文木へと上書きしている。
SOURCE abstract_tree(SOURCE s) {
eliminate_insignificant(s); // SKIP_NODEの削除
eliminate_redundant_sentence(s); // 中身1個のコンテナの削除
eliminate_redundant_math(s); // 中身1個のコンテナの削除
operator_zipper(&s); // 数式の二分木化
eliminate_container(s); // 数式の二分木化
return s;
}
この関数の中では、前節で紹介した処理
- SKIP_NODEの削除
- 中身1個のコンテナの削除
- 数式の二分木化
を実行し、解析木を簡単化している。順に見ていこう。
1. SKIP_NODEの削除
abstract_tree関数
内で最初に呼び出されているのは
eliminate_insignificant関数。
これはSKIP_NODEを削除する関数だ。
void eliminate_insignificant(SOURCE s) { // SKIP_NODE と ; だけの命令を全削除する関数 // 走査準備 NODE *node = s.program; for (int i=0; i<s.max_node_num; i++) { s.program[i].arrived = false; } // 走査開始 while (node != NULL) { if (node -> kind == SKIP_NODE) delete_node_recursive(node); node = go_next_node(node); } }
ノードの削除は
delete_node_recursive関数
を呼び出して行っている。
この関数は引数で指定されたノードの子孫のノードを全削除する、汎用的な関数だ。
void delete_node_recursive(NODE *node) { NODE *up = node -> up; assert(up != NULL); // node[0]のPROGRAMは消せない仕様 NODE *left = node -> left; NODE *right = node -> right; if (left != NULL && right != NULL) { left -> right = right; right -> left = left; } else if (left != NULL && right == NULL) { left -> right = NULL; } else if (left == NULL && right != NULL) { up -> down = right; right -> left = NULL; } else if (left == NULL && right == NULL) { up -> down = NULL; } }
こうしてSKIP_NODEを削除すると、解析木から水色のノードがなくなる。
2. 中身1個のコンテナを削除
次は緑のノードの削除だ。この処理は
abstract_tree関数
から呼び出される
eliminate_redundant_sentence(s)eliminate_redundant_math(s)eliminate_container(s)
の3つの関数で行っている。
これらの関数は前節のeliminate_insignificant関数とほぼ同じだ。
唯一の違いは、木の変更操作が「ノードの削除」ではなく「孤立ノードを中身で置換」になるところ。
孤立ノードを置換する際に
replace_by_solitary_node関数
を呼び出している。
上図のN4のノードが、
replace_by_solitary_node関数の引数に対応している。
void replace_by_solitary_node(NODE *node) { NODE *up = node -> up; if ((up != NULL) && (node -> left == NULL) && (node -> right == NULL)) { up -> kind = node -> kind; // 上を孤独な自分で置き換えて、自分を削除 up -> init = node -> init; up -> last = node -> last; up -> down = node -> down; // 関数コールの場合は引数を上にコピーする必要がある NODE *down = node -> down; while (down != NULL) { down -> up = up; down = down -> right; } } }
こうして中身1個のコンテナを削除すると、緑のノードがなくなり抽象構文木っぽいものが得られる。
3. 数式の二分木化
実はSKIP_NODEと中身1個のコンテナを消しただけだと、抽象構文木としては不完全だ。
数式の処理が残っている。
今まで数式についてほとんど触れてこなかったので、一気に話を進めよう。 簡単のために
a*2*3 + (b*4+5)
という数式について考える。 この数式を字句解析して構文解析すると、以下のような解析木が得られる。
この解析木に対し、水色のSKIP_NODEと緑色の中身1個のコンテナを消すと
かなりシンプルになった。 しかし黄色で示した数式コンテナが生き残っている。 これらのコンテナは中身が複数なので、さっき緑ノードの削除では消えなかったのだ。
ところで、我々の最終目標はx86のアセンブラを吐くことだ。
x86の命令セットには、「括弧や加減乗除の優先順位を判断しつつ、イイ感じに計算する命令」などない。
「eaxとebxを足す」とか「eaxの値をスタックに詰む」とか「スタックからeaxに値を戻す」
みたいな単純な命令しかなかった。
つまり
- 登場人物は即値と変数(レジスタとメモリのこと)だけ
- 演算は2項演算しかない
もっというと
1+3+5は計算できない1+3なら計算できる
1+3+5をCPUで計算するには
- 1と3を足す
- その結果と5を足す
つまり2項演算だけに簡約しなければならない。 これは数式を二分木に変換することと等価である。
さっきの数式を二分木に変換すると
黄色い数式コンテナが消えている。
登場人物は2項演算子B_OPERATOR、即値IMMEDIATE、変数VARIABLEの三人になった。
数式の二分木化の実装
二分木化の手順を知るため、さっきの数式の第一項
a*2*3
を考える。
operator_zipper関数で、右端から順に2項演算の形にするeliminate_container関数で、数式コンテナを直下の2項演算子に置換
という処理を行えばよい。
以上で、抽象構文木の作成は完了。
計算の優先順位について
二分木化のところで
1+2*3 --> (1+2)*3
という事件が発生しそうだ。
- 項の加減は
FORMULA直下で行う - 因子の乗除は
TERM直下で行う
と決まっている。 加減と乗除は解析木レベルで分離されているので、両者が交じることはない。
また括弧の優先順位についても解析木のFACTORノードで分離されているので、考えずに済む。
どうでもいい話
このコンパイラ製作の目的は、内部処理と仕組みを理解することだった。 基礎を知りたい。応用はどうでもいい。
そういう目的なので生成コードの最適化には興味がなかった。 しかし今日は抽象構文木の日なので、定数の畳み込みについてだけ言及しておこう。
要するに、コンパイル前のコードに1*2*3+(4*5+6)があれば、それをまるっと35という即値に置き換える最適化を定数の畳み込みという。
1+a+2があれば、和の順番をうまく入れ替えてa+3にする必要がある。
この畳込みはかんたんに実装できるけど、簡単なだけあって、実行時の速さを短縮する効果は薄いらしい(要出典)。 wikipedia を見ると、コンパイラ最適化の手法は山のように列挙されている。 こうした最適化は抽象構文木をどんどん変換する操作に対応するらしい。 (コード生成の段階で行う最適化もある)
また変数の型についても、抽象構文木を走査して不整合がないかチェックするらしい。
ちなみに今作っているminc言語の処理系では、型はintしかないので不整合もへったくれもない。
21日目: [コンパイラ] 構文解析 (実装編)
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の21日目の記事です。
昨日は人力で構文解析を行った。
今日はその処理をC言語で実装する。
構文解析のアルゴリズム
解析木作成のgifアニメを作った。まずこれを5周ぐらい見て欲しい。
これは再帰下降と呼ばれるアルゴリズムだが、日本語で説明すると
- ノード属性N0を解析するパーサに、トークンの列[T1, T2, T3, T4, T5]が入力される
- N0解析パーサは、N0を定義するBNFを参照し、[T1, T2, T3]がN1のノード属性を持つと特定する
- N0のノードの下に、N1のノードを生やす
- N1を解析するパーサに、トークンの列[T1, T2, T3]が入力される
- N1解析パーサは、N1を定義するBNFを参照し、[T1, T2]がN3のノード属性を持つと特定する
- N1のノードの下に、N2のノードを生やす
といった具合にツリーを生成しながら下降し、プログラムを細かく分解していく。
ツリーの下端に到達したら1つ上のノードに戻り、1つ右側のトークンが含まれるノードを特定して、再び下降を開始する。 これは深さ優先探索で再帰的にツリーを作成するアルゴリズムになっている。
アルゴリズムの実装に必要なのは、ノード属性毎の解析パーサだ。それらを用意すれば解析木は自動生成されるだろう。
ノードを表す構造体
解析パーサを作る前に、ツリー構造を表現するための ノードを表す構造体 を見ておく。
typedef struct __STRUCT_NODE__ { int kind; // ノードの種類 int init; // トークン配列の開始index int last; // トークン配列の終了index bool arrived; // 走査時に使う // 周辺のノードへのポインタ struct __STRUCT_NODE__ *left, *right, *up, *down; } NODE;
構造体のメンバの意味は、さっきのgif動画を見ればわかると思う。
周辺ノードへのポインタ*left, *right, *up, *downは動画中の黒矢印を表している。
黒矢印が存在しない場合はNULLにしておく。
このNODE構造体の配列で解析木を表す。
例えばgif動画のツリーの左端三段は
NODE node[1000000]; node[0] = { // N0のノード kind = N0; // 列挙型 enum で実装 init = T1のindex; last = T5のindex; up = NULL ; left = NULL ; right = NULL; down = &(node[1]) ; } node[1] = { // N1のノード kind = N1; init = T1のindex; last = T3のindex; up = &(node[0]) ; left = NULL ; right = &(node[6]); down = &(node[2]) ; } node[2] = { // N1のノード kind = N2; init = T1のindex; last = T2のindex; up = &(node[1]) ; left = NULL ; right = &(node[5]); down = &(node[3]) ; }
minc解析パーサの挙動
gif動画の例だと、ノード属性N0を解析するパーサは以下の入出力を持つ。
| 入力 | 出力 |
|---|---|
| [T1, T2, T3, T4, T5] | N1と[T1, T2, T3]のペア |
| [T4, T5] | N6と[T4, T5]のペア |
シンボリックな例はここまでにする。
例として、minc言語のPROGRAMノードを解析するパーサの挙動を見てみよう。
例としてint a; int func ( int b );というサンプルコードを処理する際の、解析パーサの挙動を解説する。
前処理としてサンプルコードを字句解析すると、以下のトークン配列が得られる。
TOKEN token[] = {
TYPE , // token[0] -- int
VARIABLE , // token[1] -- a
SEMICOLON, // token[2] -- ;
TYPE , // token[3] -- int
VARIABLE , // token[4] -- func
LPAREN , // token[5] -- (
TYPE , // token[6] -- int
VARIABLE , // token[7] -- b
RPAREN , // token[8] -- )
SEMICOLON // token[9] -- ;
}
このトークン配列を解析パーサの
find_program
に入れる。
| ノード種別 | BNFによる構文解析の定義 |
|---|---|
| PROGRAM | (V_DEC SEMICOLON | F_DEC | PROTOTYPE SEMICOLON)* |
| PROTOTYPE | TYPE VARIABLE LPAREN (ep | V_DEC (COMMA V_DEC)*) RPAREN |
| V_DEC | TYPE VARIABLE |
| F_DEC | TYPE VARIABLE LPAREN (ep | V_DEC (COMMA V_DEC)*) RPAREN FUNCTION |
まず最初に、token[0]からtoken[9]までの全トークンをパーサに入れると
int init = 0; int last = 9; // 入力されるトークン列は // TYPE, VARIABLE, SEMICOLON, TYPE, VARIABLE, LPAREN, TYPE, VARIABLE, RPAREN, SEMICOLON // トークン列に対応する入力文字列は // "int a; int func ( int b );" // initとlastを参照渡しで書き換える int find_kind = find_program(&init, &last, token); // 結果 // find_kind == V_DEC // init == 0 つまりV_DECの開始トークンは(TYPE, int) // last == 1 つまりV_DECの終了トークンは(VARIABLE, a)
token[0]からtoken[1] を処理し終えたとして、次に token[2]からtoken[9]をパーサに入力すると
int init = 2; int last = 9; // 入力されるトークン列は // SEMICOLON, TYPE, VARIABLE, LPAREN, TYPE, VARIABLE, RPAREN, SEMICOLON // トークン列に対応する入力文字列は // "; int func ( int b );" int find_kind = find_program(&init, &last, token); // 結果 // find_kind == SKIP_NODE // init == 2 つまりSKIP_NODEの開始トークンは(SEMICOLON, ;) // last == 2 つまりSKIP_NODEの終了トークンは(SEMICOLON, ;)
token[2] を処理し終えたとして、次に token[3]からtoken[9]をパーサに入力すると
int init = 3; int last = 9; // 入力されるトークン列は // TYPE, VARIABLE, LPAREN, TYPE, VARIABLE, RPAREN, SEMICOLON // トークン列に対応する入力文字列は // "int func ( int b );" int find_kind = find_program(&init, &last, token); // 結果 // find_kind == PROTOTYPE // init == 3 つまりPROTOTYPEの開始トークンは(TYPE, int) // last == 8 つまりPROTOTYPEの終了トークンは(RPAREN, 右括弧)
token[3]からtoken[8] を処理し終えたとして、次に token[9]をパーサに入力すると
int init = 9; int last = 9; // 入力されるトークン列は // SEMICOLON // トークン列に対応する入力文字列は // ";" int find_kind = find_program(&init, &last, token); // 結果 // find_kind == SKIP_NODE // init == 9 つまりSKIP_NODEの開始トークンは(SEMICOLON, ;) // last == 9 つまりSKIP_NODEの終了トークンは(SEMICOLON, ;)
こうしたパーサを全ノード属性に対し作成すれば、解析木が作成される。
minc解析パーサの実装
続いて
find_programの実装
を見てみる。
要するに、token[*init]からtoken[*last]までのトークン列が入力された際に、token[*init]を含むノード属性を特定する関数を作りたい。
find_programが呼び出されると
int find_program(int *init, int *last, const TOKEN *token) { const int arg_init = *init, arg_last = *last; int kind = OTHER_NODE; int nt = *init;
- 引数の
*initや*lastは後々書き換わるので、もとの値をarg_initやarg_lastとして保持 kindはfind_programの返り値で、ノード属性を表す。初期値は解析失敗を表すOTHER_NODEntは、トークン列内を遍歴するための整数。こいつが解析の主役
解析を開始する。
前セクションでSEMICOLONだけからなるノードにSKIP_NODEという属性を割り当てていた。あれを先に処理しておく。
if (token[nt].kind == SEMICOLON) { *last = *init; return SKIP_NODE; }
ここからが本番だが、その前にBNFを再度貼っておく。
| ノード種別 | BNFによる構文解析の定義 |
|---|---|
| PROGRAM | (V_DEC SEMICOLON | F_DEC | PROTOTYPE SEMICOLON)* |
| PROTOTYPE | TYPE VARIABLE LPAREN (ep | V_DEC (COMMA V_DEC)*) RPAREN |
| V_DEC | TYPE VARIABLE |
| F_DEC | TYPE VARIABLE LPAREN (ep | V_DEC (COMMA V_DEC)*) RPAREN FUNCTION |
トークン列のノード属性が、V_DECなのかF_DECなのかPROTOTYPEなのか知りたい。 これら3種類のノード属性は、全てTYPE と VARIABLEから始まっている。 そしてTYPEはTYPE_KEYWORDだけからなるノードで、VARIABLEはDENTIFYだけからなるノードだった。
つまりノード列はTYPE_KEYWORD と IDENTIFYのトークンで始まっているはずだ。
このチェックを行いつつ、これら2つのノードを読み飛ばそう。
「このトークンが来るはず」というチェックを行う
syntax_check関数
を作っておくと、処理がスムーズに進む。
// TYPE_KEYWORD ID syntax_check(__func__,nt,arg_init,arg_last,token,TYPE_KEYWORD); nt++; syntax_check(__func__,nt,arg_init,arg_last,token,IDENTIFY); nt++;
TYPE_KEYWORD と IDENTIFY の次のトークンに着目しよう。 これが SEMICOLON ならばグローバル変数なので、ノード属性は V_DEC になる。
// TYPE_KEYWORD ID ; if (token[nt].kind == SEMICOLON) { kind = V_DEC; *last = nt-1; }
関数プロトタイプや関数定義の場合、 IDENTIFY の次は RPAREN になる。
その場合、関数プロトタイプか関数定義か見極めるため、対応するLPARENまでntをワープさせる。
こうした「対応する括弧へのワープ」は
search_next_****系関数
で行っている。
そしてワープ先のLPARENの次のトークンを調べて
- SEMICOLONならばPROTOTYPE (関数プロトタイプ)
- LBRCKETならばF_DEC (関数定義)
として、返り値のkindにノード属性を登録する。
// TYPE_KEYWORD ID (...) else if (token[nt].kind == LPAREN) { nt = search_next_rparen(nt, arg_last, token); nt++; // TYPE_KEYWORD ID (...) ; if (token[nt].kind == SEMICOLON) { kind = PROTOTYPE; *last = nt-1; } // TYPE_KEYWORD ID (...) {...} else if (token[nt].kind == LBRACKET) { kind = F_DEC; nt = search_next_rbracket(nt, arg_last, token); assert(nt > 0); *last = nt; } } return kind;
*initと*lastの更新について書いておこう。
もしPROTOTYPEだった場合、現在のntはSEMICOLONに対応する。
BNFを見ると、SEMICOLONはPROTOTYPEに含まれないので、*last=nt-1とする。
F_DECだった場合は、関数の内部処理が終了するRBRACKETまでntをワープさせて*lastに代入する。
そして最後に、特定したノード種別(kind)をreturnして、処理終了。
以上でfind_program関数の説明は終了だ。
なお本記事では簡単のためにエラー処理を無視している。 ホントの実装はもう少し複雑になるが、本筋は変わらない。
解析木作成の再帰関数
全てのパーサを作っただけでは、解析木は生成されない。 それらを統合して再帰的にトークン配列をパースする司令塔が必要だ。
この司令塔は
make_down_tree関数
が自分自身を再帰的に呼び出すことで実装されている。
この関数の機能を一言でまとめると、入力されたノードAに対し、そのノード以下の全ノードを解析した木を作成し、ノードAに接続して返す関数だ。
NODE *make_down_tree( const int init , // 最初のトークンのindex const int last , // 最後のトークンのindex NODE *up , // 上のノードへのポインタ。`PROGRAM`ノードなら`NULL` NODE *left , // 左のノードへのポインタ。最も左のノードなら`NULL` int *node_index, // ノードの配列のindex。次のノードを登録する場所 TOKEN *token , // 字句解析の全結果の構造体配列。これとinitやlastを組み合わせて、トークン種別を調べる NODE *node // ノードの配列。これをどんどん成長させていきたい ) { NODE *ret = NULL; int find_init = init, find_last = last; int find_kind = OTHER_NODE; // ノード属性に応じて構文解析 if (init <= last) { if (up -> kind == PROGRAM ) find_kind = find_program( &find_init, &find_last, token); else if (up -> kind == PROTOTYPE ) find_kind = find_prototype( &find_init, &find_last, token); else if (up -> kind == F_DEC ) find_kind = find_f_dec( &find_init, &find_last, token); // ... 省略 ... } // token列内に有効なノードが見つかった場合は登録 if (find_kind != OTHER_NODE) { ret = &(node[*node_index]); ret -> init = find_init; ret -> last = find_last; ret -> kind = find_kind; ret -> up = up; ret -> left = left; *node_index += 1; ret -> down = make_down_tree(find_init, find_last, ret, NULL, node_index, token, node); // retの下の木を作成 ret -> right = make_down_tree(find_last+1, last, up , ret , node_index, token, node); // retの下の木を作成 } return ret; }
特に重要なのは、ノード属性に応じて解析パーサを呼び出す部分
if (up -> kind == PROGRAM ) find_kind = find_program( &find_init, &find_last, token); else if (up -> kind == PROTOTYPE) find_kind = find_prototype(&find_init, &find_last, token); ...
解析パーサの返り値は、make_down_tree関数の返り値の構造体retに格納される。
最後にmake_down_tree自身を再帰呼び出ししている。
この再帰呼び出しにより、「入力されたノードAに対し、そのノード以下の全てのノードの木を作成し、ノードAに接続して返す」という機能が実現できる。
解析木全体の作成
前節のmake_down_tree関数を
main関数内で呼び出す
ことでツリー全体を作成している。
その際の引数は
make_down_tree( 0 , // 全てのトークンを解析したいので、開始indexは0 max_token_num-1 , // 全てのトークンを解析したいので、終了indexはトークン列の長さ-1 &(node[0]) , // node[0]を`PROGRAM`ノードとしてあらかじめ準備し、この関数に渡した NULL , // `PROGRAM`ノードの上のノードは無いのでNULL &node_index , // node[1]以降に新たなノードを登録したいので、*node_indexは1になっている token , // 字句解析の全結果の構造体配列 node , // これを成長させて立派な解析木にするぞ );
要するに、あらかじめPROGRAMノードにトークン配列を詰めておき、それをmake_down_tree関数に渡すことで再帰的にツリー全体を生成している。
どうでもいい話
今までの説明で理論上はツリーが生成されるはずだ。しかしこのまま作り始めると地獄を見る。
僕は何も考えずにいきなりパーサを書き始めて、辛い思いをした。 しかしその経験のおかげで、負担を軽減するためのテクニックをいくつか習得したので、一挙に公開しよう。
解析木の図示化
パーサを作るより前に、まずツリーの可視化機能を作る。 グラフィカルで見やすいものを作る。 dot言語でツリーを吐き出して、graphvizで即座に確認できる環境を整える。
(僕はdot言語の存在を知らず、ツリー描画機能を自作してしまった)
テスト駆動開発
解析木の図示化と共に、パーサ毎にユニットテストできる環境を整える。 たとえばif文の解析パーサを書く時は
"if (a==1) {a=2;}""if (func(a)) {;} else {func(c,d);}"
のような文字列と、その構文解析結果をあらかじめ用意しておく。 テストパターンはたくさんあるほどよい。 「おお、このパターンを見過ごしてた」という気づきのオンパレードになるだろう。
(僕はテストの量が少なくて、後々になって抜け漏れが多数見つかって崩壊した)
特にSENTENCEのようなややこしいパーサを書く時は
char *K = "{{{{a=1;}}}}";char *J = "{a=1;{a=2;}a=3;}";
みたいな気持ち悪いテストをたくさん用意しておく。
(僕はテストを書かずに雰囲気でパーサを書き始めて崩壊した)
簡単なパーサから書く
ユニットテスト環境を整える最大のメリットは、簡単なパーサから順に書けることだ。
テスト環境を後回しにすると、まずPROGRAMのパーサを書いて、次にFUNCTIONの解析パーサを書いて、次にSENTENCEの解析パーサを書いて、というように、パーサを書く順番が固定されてしまう。
特にSENTENCEのパーサは難易度が高かった。
5,6個パーサを書くと慣れてくるので、難しいパーサは最後に書こう。
(僕は序盤にSENTENCEの解析パーサを書いて崩壊した)
正しいサンプルコードが正しく解析できれば、よしとする
誤ったサンプルコードに対し、誤っている点を見つけて指摘する機能、すごく魅力的だよね。 でもそれすげぇ難しいからな。 まずは正しいコードが正しく構文解析される状態を目指すべき。
(僕はパーサ製作の初期にsyntax error機能を頑張って実装したが、メンテ不可能で崩壊した)
紙と鉛筆で入念に設計する
いきなりキーボードを叩くのはヤバい。 簡単そうなノードのパーサでも、全てのパターンとその対応法を完璧に準備してからコードを書くのが重要。
(僕は何もかも適当で崩壊した)
設計の失敗
根本的な設計に関してだが、今回作ったパーサの入出力は
| 入力 | 出力 |
|---|---|
| [T1, T2, T3, T4, T5] | N1と[T1, T2, T3]のペア |
| [T4, T5] | N6と[T4, T5]のペア |
もしやり直せるなら、以下のようにするだろう。
| 入力 | 出力 |
|---|---|
| T1, [T1, T2, T3, T4, T5] | N1と[T1, T2, T3]のペア |
| T4, [T1, T2, T3, T4, T5] | N6と[T4, T5]のペア |
mincは言語仕様が単純なので今回作ったパーサで解析できたが、BNFが複雑になると破綻する。 入出力を改良すれば、かなりややこしい言語でも解析できると思う。
さて、コンパイラの作成で一番しんどい部分が終わった。 明日は解析木を抽象構文木に変換するが、作業のしんどさは昨日今日の10%程度なので、へらへらしよう。
20日目: [コンパイラ] 構文解析 (人力編)
この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の20日目の記事です。
今までx86のエミュレータやCPUなど、様々な低レイヤ環境を作ってきた。 その中で、個人的に最も製作が難しかったのが、コンパイラの構文解析器だ。 これを一日で解説するのは無理なので、2日に分けて書こうと思う。 今日はサンプルコードを人力で構文解析してコツをつかむ。 明日は実装コードの解説を行う予定。
構文解析とは
昨日作ったトークンの配列
これを以下の解析木に変換することを、構文解析という。
ツリーを構成する長方形はノードと呼ばれている。 その中の、赤字で書かれたPROGRAMやF_DECをノード属性と呼ぶことにする。 ちなみに最初の画像の緑文字はトークン属性で、両者は別物だ。混同しないように。
このツリーは有効グラフで、最上段のPROGRAMノードはサンプルコード全体に対応している。 そこから下に向かってF_DECが生えており、そこから5個のノードが生えている。
重要なのは、これら5個のノード間には前後関係が存在することだ。 ツリー中にはあらわに描かなかったが、TYPEの次のノードがVARIABLEで、その次のノードがSKIP_NODEとなっている。 この順序は変更できない。
緑のトークン配列から赤の解析木を作るルールは、昨日の字句解析と同じくBNFで与えられる。
構文解析のBNF
ノードの種類を定義するBNFだが、正式版は以下で与えられる。
左辺の赤字で書かれたノード属性を、右辺のトークン属性とノード属性で再帰的に定義している。 ep は empty の略で、そこに何もないことを表している。
ちなみに、このBNFに文字列("int"とか"return"とか)は出現しない。理由がわかるだろうか？
つまり今回のBNFでは、文字列の情報はトークン属性というラベルで隠蔽されている。 このBNFは理論的に真っ当な形式なのだが、人間には読みにくい。もう少し分かりやすい表記法を使うと
これはさっきの正式版BNFに対し、昨日の字句解析のBNFを参照して
| トークン属性 | 字句解析のBNFの定義 |
|---|---|
| EQUAL | "=" |
| COMMA | "," |
| SEMICOLON | ";" |
| IF_KEYWORD | "if" |
これらの、右辺が一種類しかないトークン属性を、その文字列で置換したものだ。
この簡易版BNFなら意味が理解しやすい。日本語でいくつか説明すると
| ノード属性 | 日本語訳 | 構成要素 |
|---|---|---|
| PROGRAM | ソース全体 | グローバル変数宣言と、関数宣言(定義)と、関数プロトタイプ宣言の3種類の列 |
| F_DEC | 関数宣言 | 型名と、関数名と、引数リストの列と、関数本体 |
| FUNCTION | 関数本体 | ローカル変数宣言の列と、文の列 |
| SENTENCE | 文 | 種類としては、複数の文、IF文、WHILE文、RETURN文、関数呼び出し、代入文がある |
| ASSIGN | 代入文 | a = 1;, a = f(b)+2;, a = 1==2 ;など |
| EXPRESSION | あらゆる式 | 両辺比較を含みうる数式。a*f(b) > 2*(3+4)+5, a*f(b), a, f(b), 2*(3+4)+5, (3+4), 5など |
| FORMULA | 多項式 | 両辺比較を含まない数式。a*f(b), a, f(b), 2*(3+4)+5, (3+4), 5など。1<2はダメ。 |
| TERM | 単項式 | 因数分解された数式。a*f(b), a, f(b), 2*(3+4), 5など。1+2はダメ。 |
| FACTOR | 因子 | a, f(b), 2, (3+4), (1==2) など。1*2はダメ。 |
構文解析のやりかたを直感的に把握するため、昨日と同様に人力でパースして、解析木を作ってみよう。
解析木の作成 (人力)
いつもの字句解析結果
これを構文解析して解析木を作る。
BNFをここで使うやつだけに絞って再掲しておく。
さぁ、いよいよ木を作るぞ。
プログラム全体の分割
まずプログラム全体からなるトークン配列を、構文解析器に入れる。
構文解析器は、プログラム全体がBNFの一番上のPROGRAMにマッチするか調べる。
ここで言うマッチとは、プログラム全体が
- V_DEC ";"
- F_DEC
- PROTOTYPE ";"
の3種類がたくさん並んだトークン列であると見抜くことだ1。 マッチに成功した時点で以下のようなツリーを作る。
今回解析したいコードは、グローバル変数も関数プロトタイプもないので、PROGRAMからF_DECだけ生えた木になる。
次にF_DECにマッチしたトークン列を、「F_DEC専用の解析器」に投げる。 (もしV_DECやPROTOTYPEが存在すれば、同様に専用解析器に投げる。)
F_DEC専用解析器は
| ノード属性 | 構文解析BNFによる定義 |
|---|---|
| F_DEC | TYPE VARIABLE "(" (ep | V_DEC (, V_DEC)*) ")" FUNCTION |
に従い、入力されたトークン列を解析する。
入力されたトークン列は
- TYPE
- VARIABLE
- V_DEC
- FUNCTION
の4種類のノードに分割される。この時点で以下のようなツリーを作る。
今回解析したいコードには引数が無いので、TYPEとVARIABLEとFUNCTIONの3ノードが生えたツリーになる。
関数型と関数名の解析
続いてTYPEにマッチしたトークン列を、TYPE専用解析器に投げる。
| ノード属性 | 構文解析BNFによる定義 |
|---|---|
| TYPE | TYPE_KEYWORD |
に従って解析すると、、、 このBNFの右辺は、トークン属性のTYPE_KEYWORDだけしかない。ノード属性が入っていない。 ツリーの言葉に直すと、要するにTYPEはツリーの末端ということだ。これでTYPEの解析は終了。
次にVARIABLEにマッチしたトークン列をVARIABLE専用解析器に投げる。
| ノード属性 | 構文解析BNFによる定義 |
|---|---|
| VARIABLE | IDENTITY |
これもトークン属性しかないので、ツリーの末端ということで解析終了。
関数本体の解析
前節で TYPE(関数の型)と VARIABLE(関数名)の解析は終わった。
最後に残された FUNCTION(関数本体)にマッチしたトークン列を、FUNCTION専用解析器に投げる。この解析器は
| ノード属性 | 構文解析BNFによる定義 |
|---|---|
| FUNCTION | "{" ( V_DEC ";" )* SENTENCE* "}" |
に従って、入力されたトークン列を解析する。そしてマッチに成功した時点で以下のようなツリーを作る。
次はV_DECにマッチしたトークン列
TYPE_KEYWORD IDENTIFY ";"
これをV_DEC専用解析器に投げる。以下のBNF
| ノード属性 | 構文解析BNFによる定義 |
|---|---|
| V_DEC | TYPE VARIABLE |
にマッチさせる。結果、V_DECノードは TYPEとVARIABLE という2つのノードに分割される。
これらのノードは、前節で書いたようにノードの末端になるので、解析は即座に終わる。 その結果得られるツリーは
文の解析
だいぶ慣れてきたと思うので、ここからは飛ばし気味に行こう。 変数宣言の解析は終了したので、次の「文1」にあたる
IDENTIFY "=" NUMBER ";"
というトークン列をSENTENCE専用解析器に投げる。 以下のBNFに従って解析すると
| ノード属性 | 構文解析BNFによる定義 |
|---|---|
| SENTENCE | ( ";" | "{" SENTENCE* "}" | IF_FLOW | WHILE_FLOW | RETURN | CALL ";" | ASSIGN ) |
トークン列全体がASSIGNにマッチする。 これをASSIGN専用解析器に投げる。 以下のBNFに従って解析すると
| ノード属性 | 構文解析BNFによる定義 |
|---|---|
| ASSIGN | VARIABLE "=" EXPRESSION ";" |
VARIABLEにマッチした部分は、前述の通りノードの末端になるので、解析は即座に終わる。
次にEXPRESSIONにマッチした部分を専用解析器に投げて、、と繰り返していくと、最終的にIMMEDIATE専用解析器に投げることになる。
| ノード属性 | 構文解析BNFによる定義 |
|---|---|
| IMMEDIATE | NUMBER |
BNFの定義の中にノード属性(赤字)が入っていないので、ここで解析が終了する。
この時点でのツリーは
「文1」の解析が終わったので、次は「文2」の解析に移る。
"return" NUMBER ";"
というトークン列をSENTENCE専用解析器に投げると、 トークン列全体がRETURNにマッチする。
続いてトークン列全体をRETURN専用解析器に投げるとEXPRESSIONにマッチして、EXPRESSION専用解析器に投げるとFORMULAにマッチして、、、と繰り返すと、最終的にIMMEDIATE専用解析器に到達し、前述の通り解析が終了する。
最終結果は
やっと解析木の作成が終わった。めでたい。
SKIP_NODEに関する補足
プログラム中の代入文 a=3; に着目してほしい。
処理を追うと、まず字句解析してIDENTIFY "=" NUMBER ";"を得たのだった。
次にASSIGN専用の構文解析器
| ノード属性 | 構文解析BNFによる定義 |
|---|---|
| ASSIGN | VARIABLE "=" EXPRESSION ";" |
を用いて解析を行った結果
- VARIABLE の トークン(IDENTITY,
a) - EXPRESSION の (NUMBER,
3)
を得たのだった。
この構文解析の際に、"="と";"の2つのトークンを読み飛ばした。 つまり解析木の中にイコールとセミコロンは存在しなかった。
人力でパースする場合は今回のように読み飛ばしても構わないのだが、構文解析用のプログラムを作るときに読み飛ばしを行うと、バグが発生しやすくなる。 これを避けるテクニックとして、読み飛ばしを行う代わりにSKIP_NODEという名前の仮想ノードを生やす作戦がある。 この記事の冒頭の解析木はSKIP_NODEのテクを駆使して作成したバージョンになっている。
明日は、このSKIP_NODEが存在する解析木を自動生成するプログラムを作ろう。
-
本来は、完璧に見抜いてから後続の処理を実行すべきだ。しかしそれは難しいので、僕の作ったプログラムは「後ろに“(”が無いからV_DECぽい」「後ろに“(”があって“{”がないからF_DECぽい」みたいな雰囲気でPROGRAMの下にノードを生やしている。↩
