KDOC 289: 『コンパイラとバーチャルマシン』

• 作成
  • <署名>

• レビュー
  • <署名>

『コンパイラとバーチャルマシン』は、主にコンパイラを解説した本である。

• 日本語の項目名のバッカス記法で、例示のプログラミング言語が示されている。わかりやすい(p21)

式の構文規則
式 → 項|式+項
項 → 因子|項*因子
因子 → 名前|(式)

• LL(k)構文解析
  • kは先読み記号を最大 k 個まで許すことを意味する。 k が1の場合には、バックトラックのない下向き構文解析が可能である
• 上向き構文解析法は、葉を枝に、枝を木に…というように、個別の項目から全体の項目へ構文解析を進めていく
• 下向き構文解析法は、次に何が来るかを仮定しながら構文解析を進めていく
• First, Follow, Director 集合
• 項 → 項*因子 名前と定義の両方に出現している。左再帰性をもつ、という
• 下向き構文解析では左再帰性の問題を取り除くために構文を書き換えて対応する
• 文法の定義として、チョムスキーによる句構造文法がある
• if文などは条件付き分岐命令を生成するが、まだthen側のオブジェクトコードを生成していないので、その時点では番地が確定しない。こういった場合、いったん命令を生成して先に進んだあとで後戻りしてその一部を修正する。バックパッチという
• データフロー解析で、到達するかを調べる。定義点と使用点を解析して、到達しない箇所を特定する
• ループ不変式の追い出し。ループ内で変化しない値はループの外に追い出して同じ計算を繰り返し行わないようにする
• ループ展開。ループの繰り返し部分を展開して、ループ繰り返し回数の計算と終了判定の条件分岐を除去する
  • 一般にループ繰り返し回数はコンパイル時にはわからないので、4倍や8倍など2のべき乗の倍数で展開する。静的なオブジェクトコードの数は増えるが、実行するオブジェクトコードの数は減らせる
• 定数伝播。変数の使用を定数で置き換えて静的にする
• 静式評価。コンパイル時に計算できるものはコンパイル時に計算し、結果だけをオブジェクトコードに反映する
• a = b; のような右辺に演算のない代入文をコピー文という。コピー伝播は、このような a の値の使用を、 b の値の使用で置き換える変換である
  • 置き換える a の使用には、このコピー文からの使用定義連鎖だけしか届いていない、などの条件がある
• コンパイル時に実行できる部分、実行時にしか実行できない部分、がある

なし。