学び直し45日目:10章 コンパイラ#1:構文解析(背景)
記録
構文解析が、トークナイザとパーサの2つの仕事に分かれていることを学んだ。
構文解析器のしくみ
構文解析器は、トークナイザとパーサから成る。トークナイザでプログラムを分解して、パーサでそれら要素をルール(文法)に照らし合わせて構文構造を理解する。
パーサ
言語の文法ルールに基づいて、トークンをグループ分けしてプログラムの構造を理解するためのモジュール。
再帰的な構文解析のざっくり理解
トークンには終端要素と非終端要素がある。終端要素はプログラム中の "while", "if", ";", "{", "}" などの意味としての開始や区切りとなるようなトークンであり、そのほかの要素が非終端要素と呼ばれている。
構文解析のざっくりとした理解は、
- 終端要素があったら、次の要素を調べる。
- 次の要素が非終端要素だったら、その中の要素を調べる。
- その中の要素が非終端要素だったら、さらにその中を調べる。
- さらにその中の要素が非終端要素だったら、(以下略)を終端要素に出くわすまでつづける。
- 終端要素に出くわしたら、そのグループはおしまい。はじめと終わりの終端要素で挟まれているグループの完成。
- 次のグループ調査へ (1 へ戻る)。
学び直し43日目:9章 高水準言語:(一通り読んでさらっと終了)
記録
かなりごぶさた。かなり妥協しているが、とりあえず一通り読めました。
高水準言語として、結構シンプルな Jack という言語に慣れ親しむための章。使い方は C とか Python とか、一般的な言語を触ったことがあればわかるはず。
今日の筋トレ
リングフィット
学び直し42日目:8章 バーチャルマシン#2:実装、展望、プロジェクト(8章強引に終了)
記録
ダレてきてしまったので、いったんこの章を完了とする。
実装
要点としては、VM ではスタック構造をとるため、関数呼び出しやフロー制御(分岐やループ処理)が入れ子型の構造となってることを理解できればよさげ。
関数を呼び出した側の状態は呼び出した時点の状態が保持され、いったん呼び出された側に制御が移る。そこからさらに別の処理に渡ったり、処理を終えてもとの制御に return したりする。いずれにせよ、スタック構造がなせる業。
ブートストラップコード
コンピュータがブートアップしたときに、最初に実行されるコードのこと。ROM[0] からはじまるコードセグメント。今回の場合、「SP を 256 番地に設定する」&「初期化プログラムの Sys.init を呼ぶ」が、ブートストラップコードとなる。Sys.init はメインプログラムのメインプログラムを呼び出して無限ループに入る。
今日の筋トレ
…ぜんぜんやってないぜ!
学び直し41日目:8章 バーチャルマシン#2:VM仕様
記録
書いてある通り、としか言いようがない。中でも、関数呼び出しについてだけ記載しておく。
関数呼び出しプロトコル
- if 文は、if-goto が呼ばれたときにスタックの最上位をポップして 0 かどうかで判定している。
- 関数を呼び出す側の挙動としては、「引数をスタックにプッシュする」→「関数を呼び出す(call)」→「スタック最上位に格納されている返り値を受け取る」→「呼び出し側のメモリセグメントが関数を呼ぶ前の状態に戻る」といった感じ。
- 呼び出される関数側の挙動としては、「呼び出し側から渡された引数で argument セグメントを初期化する」→「その他セグメントもそれぞれ適切に初期化する(詳細省略)」→「演算実行する」→「リターンされる前に、返り値をスタックにプッシュする。」といった感じ。
今日の筋トレ
最近モチベが…
学び直し40日目:8章 バーチャルマシン#2:背景(プログラムフロー)
記録
7章で作った VM に、プログラムフローとサブルーチン呼び出しを追加する。これにより、VM が完成する。
プログラムフローは if、while、for など、条件に応じて次の実行先が変わる処理のこと。サブルーチン呼び出しは、プログラム実行中にサブルーチン(プロシージャ、関数、メソッドと同じ概念)に処理を渡して、そちらの処理が終わったら結果と処理を返してもらうこと。
これらの実現には、スタック処理が用いられる。
プログラムフロー
「goto distination」コマンドを用いて、任意の場所にある命令を実行する。distination の指定には、スタックの最上位にある値を条件とする。スタック最上位値が 0 でなければ指定された場所へ移動する。0 であれば jump せずに次のコマンドを実行する。
サブルーチン呼び出し
ビルトインコマンドや、ユーザーが定義する抽象的なコマンドをサブルーチン(プロシージャ、関数、メソッド)と呼ぶ。
ビルトインコマンドはコマンドをそのまま記載すれば呼び出せるが、ユーザー定義のサブルーチンは "call" を使って呼び出す。使い方はどちらも同じで、スタックから引数を読み出し、結果をスタックの最上位に返す。
サブルーチンの処理順序をいい感じにコントロールすることをハウスキーピング処理というらしい。処理の実行順序の整理も、スタック処理が利用されている。call-return ロジックという方式を利用している。
call されたらそのサブルーチンのローカル変数や引数、ワーキングスタック(pop, push, add などの命令)とリターンアドレスをメモリ領域(この領域をフレームとよぶ)に確保していく。このことをグローバルスタックというらしい。で、先にスタックされたサブルーチンは、あとから入れられたサブルーチンが終わるまで待ちの状態となる。まさに LIFO のスタック処理。
今日の筋トレ
リングフィットアドベンチャー。