名残

プレゼント・デイ　プレゼント・タイム

言語処理系周りの用語とコンパイラの構造

言語処理系

これからは、自分が興味を持った技術とか理論に関して書き散らしていくつもり。
おそらく当面は ↓ の本を読んだ感想とか言語処理系の開発進捗について載せていく

今日は「コンパイラの構成と最適化」を読み進めたので、その要約を書く

１章「はじめに」

言語処理系周辺の用語の定義

1. コンパイラ

高級言語で書かれたプログラムを、機械向き言語 (計算機での実行に適した言語) のプログラムに翻訳するためのプログラム

2. 変換系

ある言語 (原始言語) で書かれた (原始) プログラムを他の言語 (目的言語) の (目的) プログラムに変換するためのプログラム

3. インタプリタ (翻訳系)

高級言語に都合よく設計された VM の言語 (中間言語) に変換して、それを解釈実行するプログラム

計算機が特定のプログラム言語に対して設計されているわけではなく、高級言語で書かれたプログラムを機械語のプログラムに直接変換するのは難しいことが多いため、よく用いられる

利点：コンパイラ / インタプリタの開発が比較的容易

欠点：目的プログラムの実行速度が遅い

4. 前処理系

原始プログラムのレベルで前処理的な変換を行う変換系

5. (言語)処理系

原始プログラムのコンパイルから実行までに必要なすべてのシステムを合わせたもの

関係性の図式化

↓ こんな感じ

２章「コンパイラの簡単な例」

コンパイラの論理的構造/物理的構造について説明されていた。
式の構文解析を理解するための準備としてスタックの原理と後置記法、操車場アルゴリズムが解説されていたがググればすぐわかるので言及しない。

コンパイラの論理的構造

1. 字句解析

(入力: 原始プログラムの文字列, 出力: 解析結果を表すトークン列)

原始プログラムのソースコードを先頭から１字１字調べながら、プログラムの基本要素であるトークンを切り出していく

2. 構文解析

(入力: トークン列, 出力: AST (抽象構文木))

プログラムのどの部分がどの文法規則に対応するかを解析し、文法的に正しければその構造を反映した木構造データである AST を出力する

3. 中間語生成

(入力: AST, 出力: 中間語)

AST をそのまま中間語とすることもあるが、より目的コードに近い形として AST の構成要素を実行順に整列したものを中間語とすることもある。複数の中間語を用いるコンパイラもある

中間語の例：RTL (Register Transfer Language)
レジスタとのデータのやり取りを手続き的に記述する中間表現 (intermediate representation) で、GCC でも実際に使われているらしい。すごい

※ これを構文解析と同時に行うコンパイラも存在している

4. 最適化

(入出力: 中間語)

目的プログラムを、実行効率のよいものにする

中間語の列の中で無駄なものを省いたり、順序を入れ替えたりして、より効率のいい目的プログラムを吐き出せるようにする

最適化のタイミングは様々：

  • 構文解析の直後
  • 中間語の生成直後
  • 目的コードへの変換直後

5. コード生成

(入力: 中間語, 出力: 目的プログラム)

機械語の目的プログラムを生成し、ファイルに出力する

主ルーチンからサブルーチンまで、そのプログラムの実行に必要なプログラムをまとめて一度にコンパイルする場合は、コード生成完了後にすぐ実行することができる

C や Fortran などのように、主ルーチンやサブルーチンを別々にコンパイルする場合は、目的プログラムは別々のファイルに出力される。それらを結合して実行可能ファイルを出力するには、リンカやリンケージエディタが必要になる

コンパイラの物理的構造

相 (Phase)

コンパイラの論理的構造の各段階を指す

パス (Pass)

言語処理系のなかで、１つの言語の変換を担当するルーチン群

例えば字句解析と構文解析が異なるルーチンに分離され、ソース全体をトークン列に変換したものを字句解析ルーチンから構文解析ルーチンに渡す構成の場合、ここには２つのパスが存在していることになる

構文解析ルーチンが先行して呼び出され、サブルーチンとして適宜字句解析ルーチンが呼び出される構成の場合、１つのパスにまとまっていることになる

１パスコンパイラ

論理的構造のすべてを１パスにまとめてしまう実装

中心的役割を担うのは構文解析ルーチンで、通常は最適化の相がない

コンパイル時間が短いのでデバッグ時には都合がいい

マルチパスコンパイラ

複数のパスに分かれた実装

複数の原始言語に対応するには「字句解析」〜「中間語生成」のパス (フロントエンド) を原始言語ごとに開発して、以降のパス (バックエンド) は共通化すればいい

さらに複数の目的言語に対応するには「コード生成」のパスだけを目的言語ごとに開発すればいい (この場合「コード生成」のみがバックエンドに属する)

特に最適化のためのパスを持ったものを「最適化コンパイラ」と呼ぶ

最適化の効果を高めるためには各種の解析が必要になるので、そのためにパスをさらに複数に分割することも多い

なお中間言語を実際のマシンに依存しない形にすれば、その最適化のパスは共通化できる

複数のパスに分ける他の理由

  • メモリの節約 (昔のコンパイラはメモリ不足になるのを防ぐためにパスを分けてたらしい)
  • 言語仕様 (例えば飛越し命令を含む目的プログラムを吐き出すのが厄介だったりするらしい)

雑なまとめ

今回はまぁ言語処理系・コンパイラに関しての基本的な概念を整理する感じだったので「それはそう、大事」って感想しかない

これからは具体的な字句解析・構文解析の理論や実装に触れていく予定

あと今まさに開発している、自作言語「Psyche (プシュケ)」を wasm に変換するコンパイラについての話も絡めながら進めて行けたらいいなぁ、なんて考えている

おしまい