Table of Contents

FIRST · 定義と導出

🎓 発展コース · 理論 です。基本コースの FIRST/FOLLOW で 概念 を先に 掴んでくると良いです。このページでは FIRST が正確には何なのか（定義） と、その 定義どおりに自分で 導出して求めていく過程 までを見ます。

気負わないでください — ゆっくり進みます。

📍 ある場所 · エンジン FirstFollowAnalyzer · モジュール Janglim.FrontEnd — Layer 2（構文解析表より 下 の段にあたる土台）

ずっと使う例文法です。

Expr   : Expr '+' Term | Term ;
Term   : Term '*' Factor | Factor ;
Factor : '(' Expr ')' | id ;

基本で手で求めた答えは FIRST(Expr) = FIRST(Term) = FIRST(Factor) = { '(', id } でした。
ですがその前に — FIRST が 正確に 何なのか から、はっきりと定義しておきます。
（これが抜けると、後の計算規則がただ暗記する呪文のようになってしまいます。）

定義 — FIRST とは何か

まず一行で釘を刺しておきます。

FIRST(X) = 記号 X を 導出して一番最初に現れうる終端記号 の集合。

核心となる言葉が二つあります — 導出 と 一番最初に現れる終端記号（つまり 先頭 に来るその終端記号）。
一つずつ見ていきましょう。

「導出（derivation）」 — 規則で展開すること

非終端記号をその生成規則の右辺で 置き換える 一歩を 導出 と呼び、矢印 ⇒ で書きます。

Expr を一歩ずつ展開してみます。

   Expr  ⇒  Term  ⇒  Factor  ⇒  id
        (Expr:Term)  (Term:Factor)  (Factor:id)

規則を三回適用して、結局 終端記号だけからなる文字列 id に到達しましたね。
このように 何歩も 展開することを ⇒* と書きます → Expr ⇒* id（「Expr は id を導出する」）。

だから FIRST は

X を あらゆる方法で 最後まで展開して、そこで 一番最初に現れうる終端記号（= 先頭に来る終端記号）を全部集めたものです。

Expr で実際に見てみると：

   Expr ⇒* id …             →  先頭が id   ⇒   id ∈ FIRST(Expr)
   Expr ⇒* ( Expr ) …       →  先頭が (    ⇒   ( ∈ FIRST(Expr)

Expr が作れる文字列は無数にありますが（id、id + id、( id ) * id、…）、先頭に来うる 終端記号 は結局 id か ( の二つだけです。だから：

   FIRST(Expr) = { '(', id }

記号でもっとかっちり書くとこうです（T = 終端記号の集合）：

   FIRST(X) = { a ∈ T | X ⇒* a … (a で始まる文字列を導出) }

📎 ε（空文字列）を一つだけ追加で。 もし X が 何でもないもの まで導出できるなら （X ⇒* ε）、ε も FIRST(X) に入れます。 「X はまるごと消えることもある」という表示です。

ところが私たちの expr 文法には 何でもないものになれる 非終端記号がなく、expr では見せられません。ε を一度目で見るために、小さな文法を一つ持ってきます。この章で例に使う文法は以下のとおりです：

S → A B
A → a | ε
B → b | ε

ここで A は生成規則が二つあり、そのうちの一つが A → ε なので、A ⇒ ε のように 何でもないもの まで導出されます。定義どおり ε も A の FIRST に入り、B も同じ理由で入ります。

   FIRST(A) = { a, ε }
   FIRST(B) = { b, ε }

この小さな ε 文法は、後の 計算規則 章でも ε の例として使い続けます — expr の代わりにこれが出てきたら「ああ、ε を見せるあの文法」と思って読んでください。

整理すると — 終端記号でも、非終端記号でも、複数の記号からなる並び でも、「導出して一番最初に現れうる終端記号（＋必要なら ε）の集合」 が FIRST です。
これが定義のすべてです。

定義どおりに — 導出して自分で求めてみる

ではこの「導出して先頭の終端記号を集める」を、その定義を 直接適用 して手で求めてみます。
簡単な Factor から。

Factor — 詰まることなく最後まで展開されます

Factor の二つの 生成規則（| で区切られた一行ずつ — A → α の形、ここで α は 右辺の記号の並び。詳しくは Single）を最後まで導出してみましょう。

   Factor ⇒ id              →  先頭の終端記号 :  id
   Factor ⇒ ( Expr )        →  先頭の終端記号 :  (

Factor が生み出す文字列の先頭は id か ( — 二つだけです。
定義どおりに集めると：

   FIRST(Factor) = { id, '(' }

簡単ですよね？
Factor の中には自分自身が出てこないので、導出がきれいに終わります。

Term — 展開していくと自分自身がまた出てきます

Term : Term '*' Factor | Factor。
二つの生成規則を導出してみましょう。

   ① Term ⇒ Factor ⇒ … ⇒ id または (          →  先頭 :  id, (
   ② Term ⇒ Term '*' Factor                  →  先頭がまた Term ?!

②番が妙です。
先頭が 自分自身 Term なので、先頭の終端記号を知るには、その Term を また 展開しなければなりません。

   Term ⇒ Term '*' Factor
        ⇒ Term '*' Factor '*' Factor
        ⇒ …                              ←  展開しても展開しても先頭はずっと Term、終わりが見えない

でも結局、先頭の Term もいつかは Factor の生成規則に降りていき、そうすると先頭の終端記号はまた id か ( になります。 だから：

   FIRST(Term) = { id, '(' }

Expr（Expr : Expr '+' Term | Term）も同じかたちなので、FIRST(Expr) = { id, '(' } になります。

ここで引っかかります — 「最後まで」導出できません

Term で見たように、自分自身を抱えていると（再帰）、導出が無限に長くなりうるのです。
定義は明確なのに（「導出して一番最初に現れる終端記号」）、その導出を 一つひとつ最後まで 展開するのは、手でもコンピューターでも厄介です。

次へ — 計算規則へ

そこで次のページでは — 導出を直接展開しなくても 同じ FIRST を取り出せる 計算規則 へ 進みます。
（再帰もおとなしく処理されます。）

👉 FIRST · 計算規則

👈 基本概念へ戻る： FIRST / FOLLOW

Edit this page