コンテンツにスキップ

コンパイラ概論

リンクを追加
出典: フリー教科書『ウィキブックス（Wikibooks）』

コンパイラ概論

[編集]

第1章 序論

[編集]

コンパイラとは何か

[編集]

私たちが日々使用しているコンピュータプログラムは、人間が理解しやすい高水準言語で記述されています。C、Java、Python、Rustなど、様々なプログラミング言語が存在しますが、コンピュータのCPUはこれらの言語を直接理解することができません。CPUが理解できるのは、機械語と呼ばれる0と1の列で表現された命令だけです。

この人間とコンピュータの間のギャップを埋める役割を果たすのがコンパイラです。コンパイラとは、高水準プログラミング言語で書かれたソースコードを、コンピュータが実行可能な機械語に変換するプログラムのことを指します。

コンパイラの基本的な動作

[編集]

コンパイラの動作は、以下のように単純化して表現できます。 

ソースプログラム → [コンパイラ] → 目的プログラム

ここで、ソースプログラムは人間が書いた高水準言語のプログラム、目的プログラムはコンピュータが実行できる機械語のプログラムです。

例えば、次のような簡単なCプログラムを考えてみましょう。 

int main() {
    int a = 5;
    int b = 10;
    int c = a + b;
    return c;
}

このプログラムをコンパイラに入力すると、対応する機械語の命令列が生成されます。機械語は人間には読みにくいですが、アセンブリ言語で表現すると次のようなイメージになります。 

    mov rax, 5      ; a = 5
    mov rbx, 10     ; b = 10
    add rax, rbx    ; c = a + b
    ret             ; return c

コンパイラの重要性

[編集]

コンパイラは現代のソフトウェア開発において極めて重要な役割を果たしています。その理由をいくつか挙げてみましょう。

1. 生産性の向上
高水準言語を使用することで、プログラマは複雑なアルゴリズムやデータ構造を、機械の詳細を気にせずに表現できます。これにより、ソフトウェア開発の生産性が飛躍的に向上します。
2. 移植性の実現
同じソースコードを異なるアーキテクチャのコンピュータでコンパイルすることで、複数のプラットフォームで動作するプログラムを作成できます。
3. 最適化による性能向上
優れたコンパイラは、人間が書いたプログラムを分析し、より効率的な機械語に変換します。場合によっては、熟練したプログラマが手書きしたアセンブリコードよりも高速なコードを生成することもあります。
4. エラーの早期発見
コンパイル時に型チェックや構文チェックを行うことで、プログラムの実行前に多くのエラーを検出できます。

コンパイラの歴史と発展

[編集]

黎明期（1950年代）

[編集]

コンパイラの歴史は、コンピュータサイエンスの歴史と密接に結びついています。1950年代初頭、プログラミングは機械語やアセンブリ言語で行われており、非常に困難で時間のかかる作業でした。

最初の高水準プログラミング言語の一つであるFORTRAN（FORmula TRANslation）は、1957年にIBMのジョン・バッカスとそのチームによって開発されました。FORTRANコンパイラの開発には約18人年が費やされ、当初は多くの技術者がこのプロジェクトの成功を疑っていました。しかし、FORTRANコンパイラは驚くほど効率的なコードを生成し、科学技術計算の分野で広く採用されることとなりました。

理論的基盤の確立（1960年代）

[編集]

1960年代は、コンパイラの理論的基盤が確立された重要な時期です。この時期の主な成果には以下のようなものがあります。

  • ノーム・チョムスキーによる形式言語理論の発展
  • 文脈自由文法の概念の確立
  • LR構文解析アルゴリズムの開発（ドナルド・クヌース）
  • ALGOL 60の仕様策定とそのコンパイラ技術の発展

特にALGOL 60は、構造化プログラミングの概念を導入し、その後の多くのプログラミング言語に影響を与えました。また、ALGOL 60のために開発されたBNF（Backus-Naur Form）記法は、現在でも言語仕様の記述に広く使用されています。

最適化技術の発展（1970年代-1980年代）

[編集]

1970年代から1980年代にかけて、コンパイラ技術は大きく発展しました。この時期には以下のような進歩がありました。

  • データフロー解析の理論的枠組みの確立
  • レジスタ割り当てアルゴリズムの発展
  • グローバル最適化技術の実用化
  • yacc（Yet Another Compiler Compiler）やlex（Lexical Analyzer Generator）などのコンパイラ生成ツールの普及

また、C言語とそのコンパイラの開発も、この時期の重要な出来事です。Dennis RitchieによるCコンパイラは、効率性と移植性を両立させた画期的なものでした。

オブジェクト指向と新しいパラダイム（1990年代-2000年代）

[編集]

1990年代以降、オブジェクト指向言語の普及とともに、コンパイラ技術も新たな課題に直面しました。

  • C++やJavaなどのオブジェクト指向言語のコンパイラ
  • Just-In-Time（JIT）コンパイル技術の発展（Java VM、.NET CLR）
  • ガベージコレクションの高度化
  • 並列化・並行性のサポート

特にJava仮想マシン（JVM）は、中間表現（バイトコード）とJITコンパイルを組み合わせることで、移植性と性能を両立させる新しいアプローチを示しました。

現代のコンパイラ（2010年代-現在）

[編集]

現代のコンパイラ技術は、さらに高度化・多様化しています。

  • LLVMの登場により、コンパイラ基盤の再利用が容易に
  • プロファイルベース最適化による実行時情報の活用
  • マルチコア・GPUプログラミングのサポート
  • 関数型言語やRustなどの新しい言語パラダイム
  • WebAssemblyなど、新しい実行環境への対応

LLVMは、Chris Lattnerによって開発されたコンパイラ基盤で、モジュール化された設計により、新しいプログラミング言語の開発を大幅に容易にしました。現在、Clang（C/C++コンパイラ）、Swift、Rustなど、多くの言語がLLVMを基盤として使用しています。

インタプリタとの違い

[編集]

プログラミング言語の実行方式には、コンパイル方式の他にインタプリタ方式があります。この二つの違いを理解することは、コンパイラの特性を理解する上で重要です。

インタプリタの動作

[編集]

インタプリタは、ソースプログラムを直接解釈しながら実行します。プログラムを機械語に変換する過程はなく、一行ずつ（または一文ずつ）読み込んで、その場で実行していきます。 

ソースプログラム → [インタプリタ] → 実行結果
              ↑                    ↓
              └── 入力データ ──┘

Python、Ruby、JavaScriptなどの多くのスクリプト言語は、伝統的にインタプリタ方式で実行されてきました。

コンパイラとインタプリタの比較

[編集]
特徴 コンパイラ インタプリタ
実行前の処理 ソースコード全体を機械語に変換 特になし
実行速度 高速 比較的低速
開発サイクル コンパイル時間が必要 すぐに実行可能様々な中間表現の形式と、それぞれの利点・欠点を理解します。抽象構文木、三番地コード、SSA形式などを学びます。
エラー検出 コンパイル時に多くのエラーを検出 実行時にエラーを検出
メモリ使用 目的コードを保存する必要がある ソースコードのみ
デバッグ やや困難 比較的容易
移植性 プラットフォームごとにコンパイルが必要 インタプリタがあれば実行可能

ハイブリッドアプローチ

[編集]

現代の多くの言語処理系は、コンパイラとインタプリタの利点を組み合わせたハイブリッド方式を採用しています。

Java仮想マシン（JVM）

Javaプログラムは、まずJavaコンパイラによってバイトコードと呼ばれる中間表現にコンパイルされます。このバイトコードは、Java仮想マシン（JVM）上でインタプリタまたはJITコンパイラによって実行されます。 

Javaソースコード → [javac] → バイトコード → [JVM] → 実行
Python

Pythonも同様に、ソースコードをまず内部的なバイトコードにコンパイルし、それをPython仮想マシンで実行します。さらに、PyPyのようなJITコンパイラを使用した実装もあります。

このハイブリッドアプローチにより、開発の容易さと実行速度のバランスを取ることができます。

コンパイラの構造と各フェーズの概要

[編集]

コンパイラは、複雑なシステムですが、その処理は明確に定義されたいくつかのフェーズ（段階）に分けることができます。これらのフェーズは、大きくフロントエンド、ミドルエンド、バックエンドの3つに分類されます。

全体構造

[編集]
ソースプログラム
    ↓
[フロントエンド]
  │
  ├─ 字句解析
  │    ↓
  ├─ 構文解析
  │    ↓
  └─ 意味解析
       ↓
    中間表現
       ↓
[ミドルエンド]
  │
  └─ 最適化
       ↓
    最適化された中間表現
       ↓
[バックエンド]
  │
  ├─ コード生成
  │    ↓
  └─ 最適化（ターゲット依存）
       ↓
  目的プログラム

フロントエンド

[編集]

フロントエンドは、ソースプログラムを読み込み、その構造を解析して中間表現に変換する役割を担います。

字句解析（Lexical Analysis）
[編集]

字句解析は、ソースプログラムを文字の列として読み込み、意味のある単位であるトークンに分割します。

例えば、次のようなコード片を考えます。 

int sum = a + 123;

字句解析器（レキサー、スキャナー）は、これを次のようなトークン列に変換します。 

<KEYWORD, "int">
<IDENTIFIER, "sum">
<OPERATOR, "=">
<IDENTIFIER, "a">
<OPERATOR, "+">
<NUMBER, "123">
<SEMICOLON, ";">

字句解析では、空白やコメントなどの不要な要素も除去されます。

構文解析（Syntax Analysis / Parsing）
[編集]

構文解析は、トークン列がプログラミング言語の文法規則に従っているかをチェックし、プログラムの構造を表す構文木（パースツリー）を生成します。

先ほどのトークン列から、次のような構文木が構築されます。 

        代入文
       /     \
    変数宣言   式
    /  |      / \
  型 識別子  識別子 +
  |    |     |    / \
 int  sum    a   数値
                  |
                 123

構文解析器（パーサー）は、文法規則に違反する箇所を見つけると、構文エラーを報告します。

意味解析（Semantic Analysis）
[編集]

意味解析は、構文木を検査し、プログラムが言語の意味規則に従っているかを確認します。主な処理には以下があります。

  • 型チェック: 変数や式の型が正しく使われているか
  • スコープ解決: 変数や関数が適切に宣言されているか
  • シンボルテーブルの構築: 変数や関数の情報を管理

例えば、次のようなコードは構文的には正しいですが、意味的に誤りです。 

int x = "hello";  // エラー: 整数型に文字列を代入

意味解析の結果、通常は抽象構文木（AST: Abstract Syntax Tree）が生成されます。これは構文木から不要な情報を削除し、後続の処理に必要な情報のみを残したものです。

ミドルエンド

[編集]

ミドルエンドは、中間表現に対して様々な最適化を行います。

最適化（Optimization）
[編集]

最適化フェーズでは、プログラムの意味を変えずに、より効率的なコードに変換します。主な最適化技術には以下があります。

  • 定数畳み込み（Constant Folding）: コンパイル時に計算できる式を事前に計算
  x = 2 + 3 * 4  →  x = 14
  • デッドコード除去（Dead Code Elimination）: 実行されることのないコードを削除
  if (false) {
      // このブロックは削除される
  }
  • 共通部分式の削除（Common Subexpression Elimination）: 重複する計算を一度だけ実行
  a = b * c + d;
  e = b * c + f;
  →
  temp = b * c;
  a = temp + d;
  e = temp + f;
  • ループ最適化: ループ内の不変式を外に移動するなど

中間表現は、特定のハードウェアに依存しない形式であるため、様々なターゲットアーキテクチャに対して同じ最適化コードを使用できます。

バックエンド

[編集]

バックエンドは、最適化された中間表現を、特定のターゲットマシンの機械語に変換します。

コード生成（Code Generation）
[編集]

コード生成では、中間表現をターゲットマシンのアセンブリ言語または機械語に変換します。このフェーズでは以下の処理が行われます。

  • 命令選択: 中間表現の各操作に対応する機械語命令を選択
  • レジスタ割り当て: 変数をCPUのレジスタに割り当て
  • 命令スケジューリング: 命令の実行順序を最適化
ターゲット依存最適化
[編集]

ターゲットマシン固有の特性を利用した最適化を行います。例えば：

  • 特定のCPU命令の活用
  • キャッシュの効率的な利用
  • パイプライン処理の最適化

シンボルテーブルとエラーハンドラ

[編集]

これらのフェーズに加えて、コンパイラ全体で使用される重要なコンポーネントが2つあります。

シンボルテーブル（Symbol Table）

変数、関数、型などの識別子に関する情報（名前、型、スコープ、メモリ位置など）を格納するデータ構造です。コンパイラの各フェーズからアクセスされます。

エラーハンドラ（Error Handler）

コンパイルの各段階で検出されたエラーを収集し、適切なエラーメッセージをユーザーに報告します。優れたコンパイラは、わかりやすいエラーメッセージと、可能であればエラーの修正方法の提案を提供します。

本書の構成と学習の進め方

[編集]

本書は、コンパイラの理論と実装の両面をバランスよく学習できるように構成されています。

各章の概要と学習目標

[編集]
第2章：形式言語とオートマトン
コンパイラを理解するための理論的基礎を学びます。正規表現、有限オートマトン、文脈自由文法など、コンパイラ設計に不可欠な数学的ツールを習得します。
第3章：字句解析
トークンの認識方法を学び、正規表現から有限オートマトンへの変換、lexやflexなどのツールの使い方を習得します。
第4章：構文解析
文法規則に基づいたプログラムの構造解析を学びます。トップダウン解析とボトムアップ解析の両方のアプローチを理解し、パーサジェネレータの活用方法を習得します。
第5章：意味解析
型システム、スコープ解決、シンボルテーブルの設計など、プログラムの意味を理解し検証する方法を学びます。
第6章：中間表現
様々な中間表現の形式と、それぞれの利点・欠点を理解します。抽象構文木、三番地コード、SSA形式などを学びます。
第7章：コード最適化
プログラムの性能を向上させる様々な最適化技術を学びます。データフロー解析やループ最適化など、実用的な最適化手法を習得します。
第8章：コード生成
中間表現から機械語への変換方法を学びます。命令選択、レジスタ割り当て、命令スケジューリングなどの技術を理解します。
第9章：実行時環境
プログラムが実際に動作する際のメモリ管理、関数呼び出しの仕組み、ガベージコレクションなどを学びます。
第10章：高度な話題
関数型言語、オブジェクト指向言語、JITコンパイルなど、現代的なコンパイラ技術の諸相を学びます。
第11章：実践：簡単なコンパイラの実装
これまで学んだ知識を統合し、実際に動作する小さなコンパイラを一から構築します。

効果的な学習方法

[編集]
  1. 順序立てて学習する: 各章は前の章の内容を前提としているため、順番に学習することを推奨します。
  2. 手を動かす: 理論を学んだら、必ず自分でコードを書いて実装してみましょう。小さなプログラムでも実際に動かすことで、理解が深まります。
  3. 演習問題に取り組む: 各章末の演習問題は、理解度を確認するための重要な手段です。できるだけ多くの問題に挑戦してください。
  4. 既存のコンパイラのコードを読む: GCC、LLVM、tinyccなど、オープンソースのコンパイラのソースコードを読むことで、実際のコンパイラがどのように実装されているかを学べます。
  5. 段階的に理解を深める: 最初から完璧に理解しようとせず、まずは全体像を把握し、繰り返し学習することで徐々に理解を深めていきましょう。

必要な前提知識

[編集]

本書を読むにあたって、以下の知識があることが望ましいです。

  • プログラミングの基礎: CやJavaなどの命令型言語でのプログラミング経験
  • データ構造とアルゴリズム: 木、グラフ、ハッシュテーブルなどの基本的なデータ構造
  • コンピュータアーキテクチャの基礎: CPUの動作原理、メモリ階層の基本的な理解

これらの知識が不足している場合でも、必要に応じて参考資料を確認しながら学習を進めることができます。

本章のまとめ

[編集]

この章では、コンパイラの基本概念と歴史、全体構造について学びました。重要なポイントを振り返りましょう。

  • コンパイラは高水準言語を機械語に変換するプログラムである
  • コンパイラの歴史は1950年代のFORTRANから始まり、現在も発展を続けている
  • インタプリタとは異なる特性を持ち、それぞれに利点と欠点がある
  • コンパイラはフロントエンド、ミドルエンド、バックエンドの3つの主要部分から構成される
  • 各フェーズ（字句解析、構文解析、意味解析、最適化、コード生成）が協調してプログラムを変換する

次章では、コンパイラの理論的基礎となる形式言語とオートマトンについて学びます。これらの概念は、字句解析や構文解析の仕組みを理解するために不可欠です。


第2章 形式言語とオートマトン

[編集]

アルファベット、文字列、言語の定義

[編集]

コンパイラを理解するためには、まずプログラミング言語を数学的に扱うための基礎概念を学ぶ必要があります。形式言語理論は、言語を厳密に定義し、その性質を解析するための理論的枠組みを提供します。

アルファベット

[編集]

アルファベット（記号の集合）は、文字列を構成するための基本的な記号の有限集合です。通常、Σ（シグマ）で表記されます。

例：

  • 2進数のアルファベット: Σ = {0, 1}
  • 英小文字のアルファベット: Σ = {a, b, c, ..., z}
  • C言語のトークンのアルファベット: Σ = {if, while, int, +, -, (, ), ...}

文字列

[編集]

文字列（string）は、アルファベットの記号を有限個並べたものです。文字列の長さは、それに含まれる記号の個数です。

例（Σ = {0, 1}の場合）:

  • "0", "1", "01", "101", "000111" はすべて文字列
  • 空文字列ε（イプシロン）は長さ0の文字列

文字列に対する操作：

  • 連接（concatenation）: 2つの文字列を繋げる操作
    • x = "abc", y = "def" のとき、xy = "abcdef"
  • 冪乗: 文字列を繰り返す操作
    • x = "ab" のとき、x³ = "ababab"
  • 反転: 文字列を逆順にする操作
    • x = "abc" のとき、x^R = "cba"

言語

[編集]

言語（language）は、あるアルファベット上の文字列の集合です。通常、Lで表記されます。

例（Σ = {0, 1}の場合）:

  • L₁ = {0, 1, 00, 01, 10, 11} （長さ1または2の2進文字列）
  • L₂ = {ε, 0, 00, 000, ...} （0のみからなる文字列）
  • L₃ = {0ⁿ1ⁿ | n ≥ 0} （0がn個、その後に1がn個続く文字列）
    • 例: ε, "01", "0011", "000111", ...

言語に対する操作：

  • 和集合: L₁ ∪ L₂ = {w | w ∈ L₁ または w ∈ L₂}
  • 連接: L₁L₂ = {xy | x ∈ L₁ かつ y ∈ L₂}
  • クリーネ閉包: L* = {ε} ∪ L ∪ LL ∪ LLL ∪ ...
    • Lの文字列を0回以上連接したもの全て

プログラミング言語との関係

[編集]

プログラミング言語も形式言語の一種です。例えば、C言語の文法で正しいプログラムの集合は、「C言語」という言語を形成します。

コンパイラの役割の一つは、与えられた文字列（ソースコード）が、その言語に属するかどうかを判定することです。これをメンバーシップ問題と呼びます。

正規表現と正規言語

[編集]

正規表現

[編集]

正規表現（regular expression）は、文字列のパターンを簡潔に記述するための表記法です。コンパイラの字句解析において、トークンのパターンを定義するために広く使用されます。

正規表現の定義
[編集]

アルファベットΣに対する正規表現は、以下のように再帰的に定義されます。

  1. 基本要素:
    • ε（空文字列）は正規表現
    • ∅（空集合）は正規表現
    • Σの各記号aは正規表現
  2. 複合要素（r, sを正規表現とする）:
    • (r|s) または (r+s): 選択（rまたはs）
    • (rs): 連接（rの後にs）
    • (r*): クリーネ閉包（rを0回以上繰り返し）
正規表現の例
[編集]

Σ = {0, 1}とします。

正規表現 意味 マッチする文字列の例
0 記号0のみ "0"
0 1 0または1 "0", "1"
01 0の後に1 "01"
(0 1)* 0と1の任意の並び ε, "0", "1", "01", "101", ...
0* 0を0回以上繰り返し ε, "0", "00", "000", ...
1(0 1)* 1で始まる2進文字列 "1", "10", "11", "101", ...
(0 1)*1 1で終わる2進文字列 "1", "01", "11", "001", ...
プログラミング言語での正規表現
[編集]

実際のプログラミング言語では、より便利な記法が追加されています。

記法 意味 例
[a-z] 文字クラス（範囲） [a-z]は小文字英字
. 任意の1文字 a.bは"aab", "acb"など
r+ rを1回以上繰り返し a+は"a", "aa", "aaa"など
r? rを0回または1回 colou?rは"color"と"colour"
r{n} rをn回繰り返し a{3}は"aaa"
r{n,m} rをn回以上m回以下 a{2,4}は"aa", "aaa", "aaaa"
字句解析での正規表現の使用例
[編集]

C言語のトークンを正規表現で表現してみましょう。 

識別子:    [a-zA-Z_][a-zA-Z0-9_]*
整数:      [0-9]+
浮動小数点: [0-9]+\.[0-9]+
文字列:    "[^"]*"
コメント:   /\*.*\*/

正規言語

[編集]

正規表現によって表される言語を正規言語（regular language）と呼びます。正規言語は、形式言語のヒエラルキー（チョムスキー階層）において、最も制限的なクラスに属します。

正規言語の性質
[編集]

正規言語は以下の性質を持ちます。

  1. 閉包性: 正規言語は以下の操作に対して閉じています

和集合、積集合、補集合

    • 連接、クリーネ閉包
  2. 判定可能性: 正規言語には以下の判定アルゴリズムが存在します
    • メンバーシップ問題（ある文字列が言語に属するか）
    • 空性問題（言語が空集合か）
    • 有限性問題（言語が有限か）
  3. ポンピング補題: ある言語が正規言語でないことを証明するために使用される定理
正規言語でない例
[編集]

すべての言語が正規言語とは限りません。例えば、以下の言語は正規言語ではありません。

  • L = {0ⁿ1ⁿ | n ≥ 0}（0をn個、その後1をn個）
  • 対応する括弧の言語（"(())", "((()))"など）

これらの言語は「数を数える」能力が必要であり、有限オートマトンでは認識できません。このような言語には、より強力な文脈自由文法が必要です。

有限オートマトン（DFA/NFA）

[編集]

有限オートマトン（finite automaton）は、正規言語を認識する抽象機械です。コンパイラの字句解析器は、基本的に有限オートマトンとして実装されます。

決定性有限オートマトン（DFA）

[編集]

決定性有限オートマトン（Deterministic Finite Automaton, DFA）は、以下の5つ組で定義されます。

DFA = (Q, Σ, δ, q₀, F)

  • Q: 状態の有限集合
  • Σ: 入力アルファベット
  • δ: Q × Σ → Q（遷移関数）
  • q₀: 初期状態（q₀ ∈ Q）
  • F: 受理状態の集合（F ⊆ Q）
DFAの例1: "01"で終わる文字列
[編集]

Σ = {0, 1}上で、"01"で終わる文字列を認識するDFAを構築してみましょう。 

状態:
  q0: 初期状態
  q1: 直前に0を読んだ状態
  q2: 直前に01を読んだ状態（受理状態）

遷移:
  q0 --0--> q1
  q0 --1--> q0
  q1 --0--> q1
  q1 --1--> q2
  q2 --0--> q1
  q2 --1--> q0

このDFAは以下のように動作します。

  • 入力"101"の場合:
    • q0 --1--> q0 --0--> q1 --1--> q2（受理）
  • 入力"100"の場合:
    • q0 --1--> q0 --0--> q1 --0--> q1（非受理）
DFAの例2: 識別子の認識
[編集]

C言語の識別子（英字またはアンダースコアで始まり、英数字とアンダースコアが続く）を認識するDFAです。 

状態:
  q0: 初期状態
  q1: 受理状態（有効な識別子）

遷移:
  q0 --[a-zA-Z_]--> q1
  q1 --[a-zA-Z0-9_]--> q1

非決定性有限オートマトン（NFA）

[編集]

非決定性有限オートマトン（Nondeterministic Finite Automaton, NFA）は、DFAを拡張したもので、以下の特徴を持ちます。

  1. 同じ状態から同じ入力記号で複数の状態に遷移できる
  2. ε遷移（入力を消費せずに状態を変える）が可能

NFA = (Q, Σ, δ, q₀, F)

  • δ: Q × (Σ ∪ {ε}) → 2^Q（遷移関数は状態の集合を返す）
NFAの例: "ab"を含む文字列
[編集]

Σ = {a, b}上で、部分文字列"ab"を含む文字列を認識するNFAです。 

状態:
  q0: 初期状態
  q1: 'a'を読んだ状態
  q2: "ab"を読んだ状態（受理状態）

遷移:
  q0 --a--> q0
  q0 --b--> q0
  q0 --a--> q1
  q1 --b--> q2
  q2 --a--> q2
  q2 --b--> q2

注目すべき点は、q0から'a'を読んだ時、q0とq1の両方に遷移できることです。

ε遷移の例
[編集]

ε遷移を使うと、より簡潔にNFAを記述できます。

正規表現 (a|b)*abb を認識するNFA: 

q0 --ε--> q1
q1 --a--> q1
q1 --b--> q1
q1 --a--> q2
q2 --b--> q3
q3 --b--> q4（受理状態）

DFAとNFAの関係

[編集]

重要な定理: 任意のNFAに対して、それと等価なDFAが存在します。

つまり、NFAとDFAは認識能力において等価です。ただし、表現の簡潔さは異なります。

  • NFAの利点: 正規表現から直接構築しやすい、状態数が少ない
  • DFAの利点: 実装が単純、実行時の効率が良い

実際のコンパイラでは、正規表現からまずNFAを構築し、それをDFAに変換する手法がよく使われます。

部分集合構成法（NFA→DFA変換）

[編集]

NFAをDFAに変換するアルゴリズムを部分集合構成法と呼びます。

基本的なアイデア:

  • DFAの各状態は、NFAの状態の集合に対応させる
  • NFAである入力記号で複数の状態に遷移できる場合、DFAではそれらの状態すべての集合を一つの状態とする

例: 前述のNFA（"ab"を含む文字列）をDFAに変換すると: 

DFA状態 {q0} --a--> {q0,q1}
DFA状態 {q0} --b--> {q0}
DFA状態 {q0,q1} --a--> {q0,q1}
DFA状態 {q0,q1} --b--> {q0,q2}
DFA状態 {q0,q2} --a--> {q0,q1,q2}
DFA状態 {q0,q2} --b--> {q0,q2}
...

DFAの最小化

[編集]

部分集合構成法で得られるDFAは、しばしば冗長な状態を含みます。DFAの最小化アルゴリズムにより、状態数が最小のDFAに変換できます。

最小化の基本的な考え方:

  1. 受理状態と非受理状態に分割
  2. 同じ動作をする状態を統合
  3. これ以上統合できなくなるまで繰り返す

最小化されたDFAは、以下の利点があります。

  • メモリ使用量の削減
  • 実行速度の向上
  • コードの見通しの改善

文脈自由文法（CFG）

[編集]

正規言語では表現できない、より複雑な構造を持つ言語を記述するために、文脈自由文法（Context-Free Grammar, CFG）が使用されます。プログラミング言語の構文は、通常CFGで記述されます。

文脈自由文法の定義

[編集]

文脈自由文法は、以下の4つ組で定義されます。

G = (V, T, P, S)

  • V: 非終端記号の有限集合（変数）
  • T: 終端記号の有限集合（トークン）
  • P: 生成規則の有限集合
  • S: 開始記号（S ∈ V）

生成規則は A → α の形式で、Aは非終端記号、αは終端記号と非終端記号の列です。

簡単な例: 算術式の文法

[編集]

算術式を表すシンプルな文法を定義してみましょう。 

E → E + T    （式は、式 + 項）
E → T        （式は、項）
T → T * F    （項は、項 * 因子）
T → F        （項は、因子）
F → (E)      （因子は、括弧で囲まれた式）
F → id       （因子は、識別子）

ここで:

  • 非終端記号: E（式）、T（項）、F（因子）
  • 終端記号: +, *, (, ), id
  • 開始記号: E

導出

[編集]

文法から文字列を生成するプロセスを導出（derivation）と呼びます。

例: "id + id * id" の導出 

E ⇒ E + T
  ⇒ T + T
  ⇒ F + T
  ⇒ id + T
  ⇒ id + T * F
  ⇒ id + F * F
  ⇒ id + id * F
  ⇒ id + id * id

導出には2つの方法があります。

  • 最左導出: 常に最も左の非終端記号を展開
  • 最右導出: 常に最も右の非終端記号を展開

パースツリー（構文木）

[編集]

導出の過程は、木構造で表現できます。これをパースツリーまたは構文木と呼びます。

"id + id * id" のパースツリー: 

        E
       /|\
      E + T
      |  /|\
      T T * F
      | |   |
      F F   id
      | |
     id id

このツリーは、演算子の優先順位を正しく表現しています（掛け算が足し算より先に評価される）。

曖昧性

[編集]

文法が曖昧（ambiguous）であるとは、同じ文字列に対して複数の異なるパースツリーが存在することを意味します。

例: 曖昧な算術式の文法 

E → E + E
E → E * E
E → (E)
E → id

この文法では、"id + id * id" に対して2つのパースツリーが可能です。

パースツリー1（正しい優先順位）: 

      E
     /|\
    E + E
    |  /|\
   id E * E
      |   |
     id  id

パースツリー2（誤った優先順位）: 

      E
     /|\
    E * E
   /|\  |
  E + E id
  |   |
 id  id

曖昧性は、コンパイラにとって問題です。なぜなら、同じプログラムに対して異なる意味が生じる可能性があるからです。

曖昧性の除去

[編集]

曖昧性を除去する方法はいくつかあります。

文法の書き換え
[編集]

演算子の優先順位を文法に組み込む方法です（前述の算術式の文法参照）。

優先順位と結合性の規則
[編集]

パーサに優先順位と結合性の情報を与える方法です。 

演算子の優先順位（高い順）:
  1. *（左結合）
  2. +（左結合）

BNF記法とEBNF記法

[編集]

文脈自由文法を記述するための標準的な記法があります。

BNF（Backus-Naur Form）
[編集]
<式> ::= <式> + <項> | <項>
<項> ::= <項> * <因子> | <因子>
<因子> ::= ( <式> ) | id
EBNF（Extended BNF）
[編集]

EBNFでは、正規表現のような記法を使用できます。

  • [ ]: オプション（0回または1回）
  • { }: 繰り返し（0回以上）
  • ( ): グループ化
式 ::= 項 { + 項 }
項 ::= 因子 { * 因子 }
因子 ::= ( 式 ) | id

EBNFはより簡潔で読みやすく、実際の言語仕様書でよく使用されます。

C言語の文法例

[編集]

実際のプログラミング言語の文法の一部を見てみましょう。 

<program> ::= <declaration-list>

<declaration-list> ::= <declaration> | <declaration> <declaration-list>

<declaration> ::= <var-declaration> | <fun-declaration>

<var-declaration> ::= <type-specifier> id ;
                   | <type-specifier> id [ num ] ;

<type-specifier> ::= int | void

<fun-declaration> ::= <type-specifier> id ( <params> ) <compound-stmt>

<params> ::= <param-list> | void

<statement> ::= <expression-stmt>
             | <compound-stmt>
             | <selection-stmt>
             | <iteration-stmt>
             | <return-stmt>

<selection-stmt> ::= if ( <expression> ) <statement>
                  | if ( <expression> ) <statement> else <statement>

<iteration-stmt> ::= while ( <expression> ) <statement>

プッシュダウンオートマトン

[編集]

プッシュダウンオートマトン（Pushdown Automaton, PDA）は、文脈自由言語を認識する抽象機械です。有限オートマトンにスタックを追加したもので、より複雑な構造を認識できます。

PDAの構成

[編集]

PDA = (Q, Σ, Γ, δ, q₀, Z₀, F)

  • Q: 状態の有限集合
  • Σ: 入力アルファベット
  • Γ: スタック記号のアルファベット
  • δ: 遷移関数
  • q₀: 初期状態
  • Z₀: 初期スタック記号
  • F: 受理状態の集合

PDAの動作

[編集]

PDAは、各ステップで以下を実行します。

  1. 現在の状態、入力記号、スタックトップの記号を見る
  2. 新しい状態に遷移
  3. スタックトップをpopして、新しい記号列をpush

PDAの例: {0ⁿ1ⁿ | n ≥ 0}

[編集]

この言語は正規言語ではありませんが、PDAで認識できます。

基本的な戦略:

  1. 0を読むたびに、スタックにXをpush
  2. 1を読むたびに、スタックからXをpop
  3. 入力が終了し、スタックが空なら受理
状態q0（初期状態）:
  入力0、スタックトップZ → Z0をスタックに残して、Xをpush
  入力0、スタックトップX → Xをスタックに残して、Xをpush
  入力1、スタックトップX → Xをpopして、状態q1へ

状態q1:
  入力1、スタックトップX → Xをpop
  入力ε、スタックトップZ → 受理

PDAと構文解析

[編集]

構文解析器は、本質的にPDAとして動作します。スタックを使って、現在のパース状態を追跡します。

例えば、再帰下降パーサーは、関数呼び出しのスタックを使用して、暗黙的にPDAを実装しています。

チューリングマシンと計算可能性

[編集]

チューリングマシン

[編集]

チューリングマシン（Turing Machine, TM）は、アラン・チューリングが1936年に提案した計算の数学的モデルです。理論上、どんな計算可能な問題も解ける最も強力な抽象機械です。

チューリングマシンの構成要素:

  • 無限長のテープ（メモリ）
  • テープヘッド（読み書き可能）
  • 有限の状態集合
  • 遷移関数

チューリングマシンの能力

[編集]

チューリングマシンは、以下のような問題を解くことができます。

  1. 正規言語の認識（有限オートマトン）
  2. 文脈自由言語の認識（プッシュダウンオートマトン）
  3. 任意の計算可能な関数の計算

計算可能性

[編集]

チャーチ＝チューリングのテーゼは、「チューリングマシンで計算できるものは、直感的に計算可能なものすべてである」と主張します。

これは証明不可能な仮説ですが、広く受け入れられています。

決定不能問題

[編集]

すべての問題がチューリングマシンで解けるわけではありません。停止性問題は有名な決定不能問題です。

停止性問題: 「任意のプログラムと入力に対して、そのプログラムが停止するかどうかを判定する」

アラン・チューリングは、この問題を解くアルゴリズムは存在しないことを証明しました。

コンパイラとの関係

[編集]

コンパイラの多くの問題は決定可能ですが、一部は決定不能です。

決定可能:

  • 字句解析（正規言語）
  • 構文解析（文脈自由言語）
  • 型チェック（ほとんどの言語で）

決定不能または非常に困難:

  • 最適なコード生成
  • デッドコードの完全な検出
  • プログラムの等価性判定

実際のコンパイラは、完全性を犠牲にして、実用的なヒューリスティックを使用します。

チョムスキー階層

[編集]

ノーム・チョムスキーは、形式言語を生成能力によって4つのレベルに分類しました。これをチョムスキー階層と呼びます。

チョムスキー階層の4レベル

[編集]
タイプ0: 再帰的可算言語
  ↑ 包含関係
タイプ1: 文脈依存言語
  ↑
タイプ2: 文脈自由言語
  ↑
タイプ3: 正規言語

各レベルの特徴

[編集]
タイプ3
正規言語
  • 生成: 正規文法
  • 認識: 有限オートマトン（DFA/NFA）
  • 例: トークンパターン、簡単な文字列パターン
タイプ2
文脈自由言語
  • 生成: 文脈自由文法（CFG）
  • 認識: プッシュダウンオートマトン（PDA）
  • 例: プログラミング言語の構文、対応する括弧
タイプ1
文脈依存言語
  • 生成: 文脈依存文法
  • 認識: 線形有界オートマトン
  • 例: 自然言語の一部の構造
タイプ0
再帰的可算言語
  • 生成: 無制限文法
  • 認識: チューリングマシン
  • 例: 任意の計算可能な言語

プログラミング言語とチョムスキー階層

[編集]

ほとんどのプログラミング言語の構文は、文脈自由言語（タイプ2）として記述されます。しかし、完全な意味的制約を含めると、多くの言語は文脈自由ではありません。

例: C言語の「変数は使用前に宣言されなければならない」という制約は、文脈自由文法では表現できません。

執筆中

[編集]

第3章 字句解析

[編集]

字句解析の役割と目的

[編集]

トークンの定義と分類

[編集]

正規表現によるトークン仕様

[編集]

有限オートマトンの実装

[編集]

lexなどのツール

[編集]

エラー処理と回復

[編集]

第4章 構文解析

[編集]

構文解析の役割

[編集]

文脈自由文法とBNF記法

[編集]

構文木と抽象構文木(AST)

[編集]

トップダウン構文解析

[編集]

再帰下降パーサ

[編集]

LL(1)パーサ

[編集]

ボトムアップ構文解析

[編集]

LR(0)、SLR、LR(1)、LALR

[編集]

エラー回復戦略

[編集]

yaccなどのパーサジェネレータ

[編集]

第5章 意味解析

[編集]

意味解析の目的

[編集]

シンボルテーブルの設計と実装

[編集]

スコープと名前解決

[編集]

型システムと型検査

[編集]

静的セマンティクス

[編集]

属性文法

[編集]

第6章 中間表現

[編集]

中間表現の必要性

[編集]

抽象構文木(AST)

[編集]

三番地コード

[編集]

静的単一代入形式(SSA)

[編集]

制御フローグラフ(CFG)

[編集]

データフローグラフ

[編集]

疎な条件付き定数伝播（Sparse conditional constant propagation; SCCP）

[編集]

第7章 コード最適化

[編集]

最適化の基本概念

[編集]

ローカル最適化

[編集]

定数畳み込み

[編集]

共通部分式の削除

[編集]

デッドコードの除去

[編集]

グローバル最適化

[編集]

データフロー解析

[編集]

到達定義解析

[編集]

生存変数解析

[編集]

ループ最適化

[編集]

ループ不変式の移動

[編集]

帰納変数の最適化

[編集]

インライン展開

[編集]

第8章 コード生成

[編集]

ターゲットマシンのアーキテクチャ

[編集]

命令選択

[編集]

レジスタ割り当て

[編集]

グラフ彩色法

[編集]

線形走査法

[編集]

命令スケジューリング

[編集]

実行時環境

[編集]

第9章 実行時環境

[編集]

メモリ構成

[編集]

活性化レコードとスタックフレーム

[編集]

静的リンクと動的リンク

[編集]

ヒープ管理

[編集]

ガベージコレクション

[編集]

マーク&スイープ

[編集]

参照カウント

[編集]

世代別GC

[編集]

エスケープ解析

[編集]

第10章 高度な話題

[編集]

関数型言語のコンパイル

[編集]

オブジェクト指向言語の実装

[編集]

Just-In-Time(JIT)コンパイル

[編集]

並列化と並行性

[編集]

プロファイルベース最適化

[編集]

LLVM/GCCなどの現代的なコンパイラ基盤

[編集]

第11章 実践：簡単なコンパイラの実装

[編集]

設計する言語の仕様

[編集]

字句解析器の実装

[編集]

構文解析器の実装

[編集]

意味解析とシンボルテーブル

[編集]

コード生成

[編集]

テストとデバッグ

[編集]

附録

[編集]

A. 主要なコンパイラツールとライブラリ

[編集]

B. アセンブリ言語の基礎

[編集]

C. 文法記法の比較

[編集]

D. 参考文献とさらなる学習資源

[編集]
"https://ja.wikibooks.org/w/index.php?title=コンパイラ概論&oldid=284220" より作成