· 暮らし・ツールガイド

AP科目A 33 — コンパイラと言語処理：字句・構文・意味解析から最適化まで

応用情報技術者試験 科目Aの補足編。コンパイラの字句・構文・意味解析、3番地コードなどの中間表現、定数畳み込み・共通部分式の除去などの安全な最適化とコード生成を、計算例とオリジナル診断問題5問で整理します。

応用情報技術者試験科目Aコンパイラ言語処理基礎理論

AP科目A・第33回 · 2026年度・シラバスVer.7.2に基づく独立した学習資料です。IPAとの提携はなく、合格を保証しません。 シリーズ一覧を見る

2026年IPA応用情報技術者試験（AP）科目A、シラバスVer.7.2を基準とし、2026-10-22確認。Motitoryの独立した学習資料であり、IPAとの提携やIPAによる承認・確認はない。Ver.7.2の全範囲を網羅せず、合格を保証しない。本文の例題と問題はすべてMotitoryのオリジナルで、IPAの過去問題ではない。

学習インデックス

  1. コンパイラの役割と処理の流れ
  2. 字句解析
  3. 構文解析と文法
  4. 意味解析
  5. 中間表現と最適化
  6. コード生成と目的プログラム
  7. 用語対照表
  8. クイックシートと落とし穴
  9. オリジナル診断5問
  10. セルフチェックと復習スケジュール
  11. 公式出典

本記事は固定の仕上げ計画AP33–38のうち**AP33（補足編）**であり、シリーズ最後の記事ではない。全回はシリーズ一覧で確認できる。木・スタックなどのデータ構造はAP5、状態遷移表の追跡はAP6、開発手法とテストはAP23で扱ったので、ここでは再説明せず、コンパイラ固有の内容だけを扱う。

1. コンパイラの役割と処理の流れ

コンパイラは、高水準言語で書かれたソースプログラム（原始プログラム）を、意味を変えずに対象機械向けの目的プログラムへ翻訳する。目的プログラムは通常、リンクを経て実行ファイルになる。試験で使う標準モデルは次の順序である。

ソースプログラム（文字列）
 → ① 字句解析     ：文字 → トークン列
 → ② 構文解析     ：トークン列 → 構文木（解析木／AST）
 → ③ 意味解析     ：宣言・型・文脈の検査、記号表の更新
 → ④ 中間コード生成：AST → 中間表現（例：3番地コード）
 → ⑤ 最適化       ：観測可能な動作を保ったまま中間コードを改善
 → ⑥ コード生成   ：対象機械の目的コード
目的プログラム

実際のコンパイラは段階をまとめたり、最適化を複数回行ったりするので、この順序は「各段階が何を受け取り何を出すか」を区別する学習モデルとして覚える。

2. 字句解析

字句解析は文字の並びをトークンに切り分ける。空白とコメントはこの段階で捨てられる。トークンの種類（識別子、数値、演算子、区切り記号）は通常正規表現で定義し、有限オートマトンで認識する。例：識別子 = 英字(英字|数字)*。有限オートマトンの状態遷移表を手で追う方法はAP6で扱った。

  • 最長一致： <= は < と = の2トークンではなく1トークンとして読む。
  • 字句エラーの例：どのトークンのパターンにも合わない文字（言語が許さない # など）。

計算例1 — トークン化と構文木

ソース total = price * 3 + tax;

順 トークンの種類 実際の文字列
1 識別子 total
2 代入演算子 =
3 識別子 price
4 乗算演算子 *
5 数値 3
6 加算演算子 +
7 識別子 tax
8 区切り記号 ;

6個の空白はトークンにならないので、結果はトークン8個である。構文木は次節で作る。

3. 構文解析と文法

構文解析は、トークン列が文法に合うかを確かめ、構造を木にする。プログラミング言語の文法は通常文脈自由文法で書き、BNFで表記する。

stmt   → id = expr ;
expr   → expr + term   | term
term   → term * factor | factor
factor → id | num | ( expr )
  • * をより下の層（term）に置いたので、* が + より先にまとまる（優先順位）。
  • expr → expr + term のような左再帰なので、同じ層の演算子は左からまとまる（左結合）。- を + と同じ層に加えると、a - b - c は (a - b) - c になる。
  • E → E + E | E * E | id のように層を分けない文法は、a + b * c に木が2つできるあいまいな文法である。

計算例1の抽象構文木（AST）：

        =
       / \
   total   +
          / \
         *   tax
        / \
    price   3

**解析木（構文木）**は expr、term などの非終端記号をすべて節点として残し、ASTは演算と被演算子だけを残した要約である。括弧と ; は構造が木の形に反映されるので、ASTから消える。

形式言語とオートマトンの対応（試験の定番）：

言語クラス 定義手段 認識する機械 コンパイラでの用途
正規言語 正規表現・正規文法 有限オートマトン 字句解析（トークン）
文脈自由言語 文脈自由文法（BNF） プッシュダウンオートマトン（スタック） 構文解析

有限オートマトンは状態数が有限なので、任意の深さの入れ子の括弧の対応を数えられない。入れ子構造にはスタックが必要なので、構文解析には文脈自由文法を使う。

4. 意味解析

意味解析は、文法上正しい木が言語の意味規則を守っているかを検査する。宣言情報は記号表に記録する。

  • 宣言されていない名前の使用、同じスコープでの二重宣言
  • 型検査：整数変数への文字列の代入、引数の個数・型の不一致
  • 必要に応じた暗黙の型変換（例：整数 → 実数）の挿入

「使用前に宣言されていなければならない」という条件は前後の文脈に依存し、文脈自由文法だけでは表しにくいので、構文解析ではなく意味解析で検査する。逆に、文法も型も正しいがアルゴリズムが誤っている論理エラーは、通常コンパイラでは見つからず、テストの領域である（AP23）。

5. 中間表現と最適化

中間言語・中間表現は、ソース言語と対象機械の間にある形式で、多くの場合特定のCPUに依存しない。そのため同じ中間表現から複数の機械向けのコードを生成でき、機械に依存しない最適化を一度実装すれば再利用できる。代表的な形式は、1命令に演算子1つと最大3つの番地（結果の番地1つ、入力オペランドの番地最大2つ）を使う3番地コードである。

計算例2 — 3番地コードと安全な最適化

b、c は整数の入力、x、y、z は整数のローカル変数とする。示した計算はどれもオーバーフローせず、呼出し・入出力・volatileアクセスもないものとする。

x = 4 * 2;
y = (b + c) * (b + c) - x;
z = y + 1;      // z は以後どこでも読まれない
return y;

① 3番地コード（10行）

t1 = 4 * 2
x  = t1
t2 = b + c
t3 = b + c
t4 = t2 * t3
t5 = t4 - x
y  = t5
t6 = y + 1
z  = t6
return y

② 定数畳み込みと定数伝播： 4 * 2 はコンパイル時に 8 と計算できる。x は変わらないので、t5 = t4 - x を t5 = t4 - 8 にできる。

③ 共通部分式の除去： t2 と t3 の間で b、c は変わらず、整数の + に副作用はないので、t3 = b + c を削除して t2 を再利用する。式が f() のように出力や状態変更を行う呼出しなら、実行回数が変わるのでまとめられない。

④ デッドコード除去（不要コードの除去）： z と t6 は以後読まれず計算に副作用もないので削除する。②の後は x、t1 も読まれないので削除する。出力や例外のように言語が定める動作を生むコードは、結果を使わなくても削除できない。

⑤ 結果（4行）

t2 = b + c
t4 = t2 * t2
y  = t4 - 8
return y

検算：b = 1、c = 2 なら、元のコードは (3) * (3) - 8 = 1、最適化後も 9 - 8 = 1 で一致する。

最適化の原則： 最適化は、言語が定める観測可能な動作（出力、戻り値、入出力の順序など）を保たなければならない。また、すべてのプログラムを必ず速くする保証はない。インライン展開やループ展開のようにコードが大きくなる変換はキャッシュ効率を下げることがあり、コンパイル時間も増える。効果は測定で確かめる。その他の名前：ループ内不変式の移動、強さの軽減（x * 2 → x + x など）。

6. コード生成と目的プログラム

コード生成は中間表現を対象機械の命令に変換する。命令選択とレジスタ割付けが中心である。出力の目的プログラムは通常そのままでは実行されず、リンカが他の目的モジュールやライブラリと結合して実行可能なロードモジュールを作る。

  • インタプリタ： 目的プログラムを作らず、ソースプログラム（または中間コード）を解釈しながら実行する。
  • クロスコンパイラ： コンパイラが動く機械とは別の機械向けの目的コードを生成する。

7. 用語対照表

日本語 English 한국어 一行定義
コンパイラ compiler 컴파일러 ソースプログラムを目的プログラムに翻訳
字句解析 lexical analysis 어휘 분석 文字 → トークン
トークン token 토큰 識別子・数値・演算子などの最小の意味単位
構文解析 syntax analysis (parsing) 구문 분석 トークン → 文法に従った木
抽象構文木 abstract syntax tree 추상 구문 트리 演算と被演算子だけを残した木
文脈自由文法 context-free grammar 문맥 자유 문법 構文の定義に使う文法、BNFで表記
形式言語 formal language 형식 언어 文法や機械で定義される記号列の集合
オートマトン automaton 오토마톤 入力を読んで状態を変える抽象機械
意味解析 semantic analysis 의미 분석 宣言・型・文脈規則の検査
記号表 symbol table 기호표 名前と型・スコープ情報を保存
中間言語 intermediate language 중간 언어 ソース言語と機械語の間の表現
3番地コード three-address code 3번지 코드 1命令に演算1つ、結果の番地1つと入力の番地最大2つ
最適化 optimization 최적화 動作を保ちながらコードを改善
コード生成 code generation 코드 생성 中間表現 → 対象機械の命令
目的プログラム object program 목적 프로그램 コンパイラの出力

8. クイックシートと落とし穴

  • 字句 = 文字→トークン（正規・有限オートマトン）／構文 = トークン→木（文脈自由・スタック）／意味 = 宣言・型／コード生成 = 対象機械の命令。
  • エラーの分類：許されない文字 → 字句、括弧の欠落 → 構文、未宣言・型の不一致 → 意味、結果が誤り → 論理エラー（テスト）。
  • 優先順位は文法の層で、結合性は再帰の向きで決まる。
  • 3番地コード = 1命令に演算子1つ。一時変数 t1, t2, … が生じる。
  • 定数畳み込みはコンパイル時の計算、共通部分式の除去は副作用・途中の更新がないときだけ、デッドコード除去は観測可能な効果がないときだけ。
  • 落とし穴：「最適化は常に速くする」「中間言語は特定CPUの機械語」「目的プログラム = ソースプログラム」「有限オートマトンで入れ子の括弧を検査できる」。

9. オリジナル診断5問

以下の問題はMotitoryが作成した原文であり、IPAの過去問題を使用・翻案していない。

Q1 — 処理段階

ソースプログラムの文字列から空白とコメントを読み飛ばし、count、<=、10 のような単位に分ける段階はどれか。

ア. 構文解析

イ. 意味解析

ウ. 字句解析

エ. コード生成

  • ア：誤り。構文解析は、すでに分けられたトークン列を文法に従って木にまとめる。
  • イ：誤り。意味解析は、字句解析・構文解析の後で宣言や型を検査する。
  • ウ：正解。 文字 → トークンであり、最長一致により <= は1トークンになる。
  • エ：誤り。コード生成は、中間表現から対象機械の命令を作る後半の段階である。

Q2 — 文法と優先順位

3節の文法で a + b * c を解析したASTとして正しいものはどれか。

ア. 根が *、左の子が a + b、右の子が c

イ. 根が + で、a、b、c がすべてその子

ウ. この文法はあいまいなので、2つの木のどちらも正しい結果

エ. 根が +、左の子が a、右の子が b * c

  • ア：誤り。(a + b) * c の木である。括弧がなければこの文法からは得られない。
  • イ：誤り。二項演算の節点は子を2つ持つ。3つを1つの節点に置くと演算順序が失われる。
  • ウ：誤り。この文法は expr/term/factor の層であいまいさを除いている。層のない E → E + E | E * E | id ならあいまいだった。
  • エ：正解。 * が下の層 term で先にまとまる。

Q3 — エラーを検出する段階

次のうち、典型的に意味解析で検出されるものはどれか。

ア. if (x > 0 { のように閉じ括弧が欠けている。

イ. 宣言されていない変数 totl をタイプミスで使っている。

ウ. 識別子に言語が許さない文字 # が含まれている。

エ. 繰返し条件が1つずれて、合計が1小さくなる。

  • ア：誤り。文法違反なので構文解析で検出する。
  • イ：正解。 totl は正しい識別子トークンで文法にも合うが、記号表に宣言がない。
  • ウ：誤り。トークンのパターンに合わない文字なので字句解析で検出する。
  • エ：誤り。言語規則の違反ではなく論理エラーで、コンパイラではなくテストで見つける。AP23でテストを復習

Q4 — 安全な最適化

整数のローカル変数だけを使う関数で、log() は画面に出力する関数である。動作を変えない変換はどれか。

ア. t = 6 * 7 を t = 42 に置き換える。

イ. log(x) + log(x) を 2 * log(x) に置き換える。

ウ. 戻り値を使っていないので、log(x); の呼出し文を削除する。

エ. 最適化すればすべてのプログラムが速くなるので、測定せずに最大の最適化を既定にする。

  • ア：正解。 定数畳み込みであり、同じ値をコンパイル時に計算するだけで観測可能な動作は変わらない。
  • イ：誤り。出力が2回から1回に減る。副作用のある式は共通部分式としてまとめられない。
  • ウ：誤り。出力は観測可能な動作なので、戻り値を使わなくてもデッドコードではない。
  • エ：誤り。コードの増加やコンパイル時間などのコストがあり、すべてのプログラムが速くなる保証はないので測定が必要である。

Q5 — 形式言語とオートマトン

正しい記述はどれか。

ア. 任意の深さの入れ子の括弧 ((())) の対応検査は、有限オートマトンだけで十分である。

イ. 中間言語は常に特定CPUの機械語なので、別の機械向けに変換できない。

ウ. 正規言語は有限オートマトンで認識でき字句解析に使われ、文脈自由文法はスタックを使うプッシュダウンオートマトンに対応し構文解析に使われる。

エ. 目的プログラムとは、字句解析に入る前のソースプログラムのことである。

  • ア：誤り。状態が有限なので深さに制限のない入れ子を数えられず、スタックが必要である。データ構造としてのスタックはAP5で復習する。
  • イ：誤り。中間言語は多くの場合機械に依存せず、だから複数の対象機械や共通の最適化に使われる。
  • ウ：正解。 言語クラス・認識する機械・コンパイラの段階の対応である。状態遷移の追跡はAP6で復習する。
  • エ：誤り。目的プログラムはコンパイラの出力で、ソースプログラムが入力である。

正解：ウ、エ、イ、ア、ウ

10. セルフチェックと復習スケジュール

  • 6つの段階の入力と出力を順に言える。
  • total = price * 3 + tax; のトークン8個とASTを描き直せる。
  • 文法の層と再帰の向きから優先順位・結合性を説明できる。
  • 例のエラーを字句・構文・意味・論理に分類できる。
  • 計算例2の10行を4行に減らし、各変換が安全な理由を言える。
  • 正規言語と有限オートマトン、文脈自由文法とプッシュダウンオートマトンを対応づけられる。

推奨復習サイクル（公開スケジュールとは別）：当日に計算例1・2を見ずに解き直す → 1日後にQ1–Q5 → 3日後にクイックシートだけを見て用語表の空欄を埋める → 7日後に新しい式で3番地コードを書いて最適化する → 14日後に間違えた問題だけを確認する。

11. 公式出典

  • IPA 応用情報技術者試験 シラバスVer.7.2 — 大分類1／中分類1／3. 情報に関する理論／（10）コンパイラ理論、PDF p.10（印刷ページ -6-）。コンパイラの役割と処理過程、字句解析、構文解析、意味解析、コード生成、最適化と、用語（文脈自由文法、中間言語、目的プログラム、形式言語、オートマトン）を確認した。2026-10-22確認。
  • IPA シラバス ハブ — 2026-10-22確認。

本記事はAP33–38仕上げ計画の最初の回である。次に予定しているテーマはAP34 無線LANで、シリーズはAP38で完結する。

ブログへ