Table of Contents

ひと目で見るパイプライン

クイックスタートでは5行で構文解析を動かしてみましたね。
その5行の中では、実はいくつもの段階が 順番に起こっています。
この章では、その 全体の流れ（パイプライン） を大きな絵として見ます。
細部は それぞれの章で扱うので、ここでは「地図」だけ頭に入れてください。

テキストが結果になるまで

私たちの入力 a + a * a がどんな道をたどるのか、追いかけてみましょう。

   "a + a * a"            ← ① ただの文字の並び (テキスト)
        │
        ▼  字句解析 (Lexing)
   [a] [+] [a] [*] [a]    ← ② 意味のあるかけら = トークン(token)たち
        │
        ▼  構文解析 (Parsing)
        Expr              ← ③ 文法構造 = 構文木(parse tree)
       /  |  \
     Expr '+' Term
      |       / | \
     Term  Term '*' Factor
      ...
        │
        ▼  (その次の段階たち — 意味解析、コード生成 …)
     実行 / 翻訳 / コンパイル

それぞれの矢印が一つの 変換段階 です。

① テキスト → ② トークン : 「字句解析（Lexing）」

コンピュータにとって a + a * a は、最初は空白を含めて9文字でしかありません。
最初の段階は、これを 意味のある 最小単位（トークン） に切り分けることです。

  • a → 「名前（識別子）」トークン
  • + → 「足し算演算子」トークン
  • * → 「掛け算演算子」トークン
  • 空白 → 捨てる

この仕事をするのが 字句解析器（lexer） または トークナイザー（tokenizer） です。

② トークン → ③ 木 : 「構文解析（Parsing）」

ここでトークンたちが 文法に合うように並んでいるか を確認し、その構造を木にします。
たとえば a + a * a で掛け算が足し算より先にまとまるべきだということ（優先順位）も、この木の形で あらわれます。

a + a * a   →   a + (a * a)      ← '*'がより深く(先に)まとまる

この仕事をするのが パーサー（parser） です。
そして Janglim が力を注いでいるのが、まさにここです。

③ 木 → その次

構文木ができると、その後は目的に応じて分かれます。
電卓なら木をたどって値を計算し、 コンパイラなら意味を解析して機械語/LLVM IR に翻訳します。
Janglim が dogfooding（自己検証） 用に作った AJ言語 は、ここまで進みます。

LRパーサーの隠れた0段階: 「テーブルを前もって作る」

上の絵には、実は 隠れた段階 がもう一つあります。
パーサーはトークンを受け取る 前に、文法を分析して 構文解析表（parse table） という巨大な表を前もって計算します。

この表は「今こういう状態で、次のトークンがこれなら → こう行動せよ」をすべて書きとめた 行動指針書 です。
構文解析のとき、パーサーは考えずに、この表だけを見て機械的に動きます。
だから LR 構文解析は速くて正確です。

💡 だから LR パーサーを「決定的（deterministic）パーサー」と呼びます。 表の各マスには行動が きっちり一つ に定まっています。だからパーサーは毎瞬間、分かれ道で迷ったり後戻り（backtrack） したりせず、一本の道だけを進みます。このように 次の行動が常に一意に定まる パーサーを決定的パーサーと呼び、 LR がその代表です。（文法に 衝突 があったり、複数の分岐を探索する GLR/LGLR 方式を使うと決定的では なくなりますが — それは後ろの 衝突 の章で扱います。）

文法  ──(前もって分析)──▶  構文解析表  ──(構文解析のとき参照)──▶  決定(shift? reduce?)

この表を作るには FIRST/FOLLOW、LR項目、正準集合 といった概念が必要です。
この表を作る旅 こそがマニュアルの本論です。
私たちは FIRST/FOLLOWから 始めます。

コードの層（layer） — ほんの少しだけ

Janglim の内部は、いくつものモジュールが 層を重ねて 積み上がっています。
下に行くほど、より基礎的な部品です。

  ┌─────────────────────────────────────────────┐
  │  AJ言語 → 意味解析 → LLVM IR (コンパイラ)       │  ← 上段 (応用)
  ├─────────────────────────────────────────────┤
  │  パーサーエンジン: 正準集合 · 構文解析表 · ドライバ │
  ├─────────────────────────────────────────────┤
  │  文法(Grammar) コンテナ                         │
  ├─────────────────────────────────────────────┤
  │  シンボル · レキサー · FIRST/FOLLOW · 正規化 · 構文木 │  ← 核心部品の集まり
  ├─────────────────────────────────────────────┤
  │  トークン型 · 共通ヘルパー                       │  ← 下段 (基礎)
  └─────────────────────────────────────────────┘

おもしろい点: FIRST/FOLLOW が 下段の近く にありますね？ コード構造の上では、とても基礎的な部品です。 でも 概念を学ぶ順番では、構文解析表の直前に学ぶのが一番よく理解できます（なぜ 必要なのかが、そのときに腑に落ちるからです）。だからこのマニュアルは コードの層の順番ではなく、理解の順番 で 進みます。各ページごとに「この概念はどの層/ファイルか」は、別に表示しておきます。

モジュール層の全体地図は、あとで 付録 で別にまとめます。

次の章

これで地図を手に入れたので、LR 構文解析の最初の核心概念に入っていきましょう。

👉 FIRST / FOLLOW

Edit this page