※小説ではない※専門書 要約資料集 為替(換算)3.9万円でもらう 紐解集生成 専門 初入門 資料 作：｛作者名｝
> 学問の宇宙・応用の軌道ステーション群「作る力と生きる力」シリーズ 計算機文明部 第2巻。ガイド役: Fable 5 監修 / Sonnet 5 執筆(脚本班)
> トーン規約: GAKUMON_UNIVERSE.md準拠。専門用語は初出で必ず説明する。
> **安全枠(§16.18・絶対厳守)**: 本冊は字句解析・構文解析・先読み・意味論という「言語処理系の仕組み」を、教育用の小さなトイ言語(PICO語)を題材に説明する教材である。難読化技術・マルウェア生成技術・実運用システムへの侵入や権限昇格につながる技術は一切含めない。
> 接続先: →BOOK-0343(情報構造の設計。配列・木・グラフという、言語処理系の内部でも使うデータの入れ物を扱う)、→BOOK-0344(文章の解析と解読。自然言語処理という、本冊の構文解析を人間の言葉に応用する分野)、→BOOK-0066『情報派生_アルゴリズム』第1巻(手順=アルゴリズムという考え方そのものの基礎)。
> 水準: 一〜十二(なぜプログラミング言語は自然言語と違うのかという土台から、字句解析、文法規則の書き方〈BNF〉、構文解析、演算子の優先順位、構文木、意味論、変数と環境、そして先読み〈lookahead〉が必要になる曖昧な文法の実例と解決法までを扱う)。
---
# BOOK-0341 計算機文明: 自分の言語を作る 第1巻 — コンピュータが迷わない言葉のつくり方
> 学問の宇宙・応用の軌道ステーション群「作る力と生きる力」シリーズ 計算機文明部 第2巻。ガイド役: Fable 5 監修 / Sonnet 5 執筆(脚本班)
> トーン規約: GAKUMON_UNIVERSE.md準拠。専門用語は初出で必ず説明する。
> **安全枠(§16.18・絶対厳守)**: 本冊は字句解析・構文解析・先読み・意味論という「言語処理系の仕組み」を、教育用の小さなトイ言語(PICO語)を題材に説明する教材である。難読化技術・マルウェア生成技術・実運用システムへの侵入や権限昇格につながる技術は一切含めない。
> 接続先: →BOOK-0343(情報構造の設計。配列・木・グラフという、言語処理系の内部でも使うデータの入れ物を扱う)、→BOOK-0344(文章の解析と解読。自然言語処理という、本冊の構文解析を人間の言葉に応用する分野)、→BOOK-0066『情報派生_アルゴリズム』第1巻(手順=アルゴリズムという考え方そのものの基礎)。
> 水準: 一〜十二(なぜプログラミング言語は自然言語と違うのかという土台から、字句解析、文法規則の書き方〈BNF〉、構文解析、演算子の優先順位、構文木、意味論、変数と環境、そして先読み〈lookahead〉が必要になる曖昧な文法の実例と解決法までを扱う)。
---
## 入口の物語 — 「2+3×4」が9になった日
ミナは自作のテキストゲームに、プレイヤーが自由に書ける「イベント式」を組み込もうとしていた。「所持金が100以上なら、扉を開ける」という条件を、プログラムの知識がない友人でも書けるように、`所持金 >= 100 かつ 3 + 4 * 2 <= 所持金` のような短い式を自由に入力できる欄を作ったのだ。
最初の実装は単純だった。入力された文字列を空白で区切り、左から順番に演算子を見つけて計算していく――というやり方である。ためしに `3 + 4 * 2` と入力してテストすると、結果は `14`(正しい掛け算優先の答え)ではなく、`3+4=7`を先に計算してから`7*2=14`……のはずが、実装のバグで`3`だけ拾って`+`を無視し、`4*2=8`だけを返すというおかしな挙動になった。慌てて直しても、次は`10 - 3 - 2`が`9`(10-(3-2)のように右側から計算してしまう誤り)になったり、`(3 + 4) * 2`のカッコが完全に無視されたりと、直すたびに別の場所が壊れる。友人にテストしてもらうと、今度は`if 所持金 >= 100 then 開ける else if 鍵 == true then 壊す`という一文で、`else`がどちらの`if`にくっつくのかで結果が変わってしまうという、もっと厄介な問題まで見つかった。
「文字列を空白で割って、前から読むだけ」というやり方では、いつまでも場当たり的な修正の繰り返しになる――そう気づいたミナは、先輩プログラマーに相談した。先輩は言った。「きみは今、日本語の感覚でプログラムの文を読もうとしている。人間なら『3+4*2』を見て、学校で習った『掛け算・割り算を先に計算する』というルールを常識として補って読める。でもコンピュータには常識がない。曖昧さを一切残さない、機械的にたどれる規則の集まりとして文を組み立て直さないと、同じ入力に対して毎回同じ答えを返すプログラムにはならないんだ」。
先輩はさらに続けた。「その規則の集まりのことを文法(ぶんぽう)と呼ぶ。文字列を文法に従って読み解く作業は、大きく二段階に分かれている。まず文字の並びを意味のある単語の単位に区切る作業、次にその単語の並びを、どの部分がどの部分にかかるかがはっきりした木の形に組み立てる作業だ。この二段階を自分の手で作れるようになれば、`2+3*4`のような式だけでなく、条件分岐や変数を持つ、きみだけの小さなプログラミング言語だって設計できるようになる」。
この一言が、この冊子の出発点になる。本冊では、PICO語という小さなトイ言語(教育用に単純化された自作プログラミング言語)を一から設計しながら、文字の並びをトークン(意味のある最小単位)に分ける字句解析、文法規則の書き方、トークンの列を木構造に組み立てる構文解析、次に来るものをあらかじめ覗き見る先読み、そして木を実際に計算して答えを出す意味論という、言語処理系(プログラムを読み解いて実行する仕組み全体)の骨格を、一段ずつ積み上げていく。
---
## 第一章: ことばとプログラムのあいだ — なぜ「厳密さ」が要るのか(水準一)
### 人間の言葉は「察する」ことができる
日本語や英語のような**自然言語(しぜんげんご、水準一: 人間が日常のコミュニケーションのために、長い年月をかけて自然に発達させてきた言語)**には、曖昧な表現がたくさん残っている。「ここでは着物を脱いでください」という古典的な例え話のように、区切り方によって意味が変わってしまう文があっても、人間は場の状況・話の流れ・常識を頼りに、たいてい正しい方の意味を「察して」読み解ける。多少文法が崩れていたり、語順が入れ替わっていたりしても、聞き手が推測で補って意味を通してしまう柔軟さこそ、自然言語の強みの一つである。
### プログラムは「察してくれない」
一方、プログラミング言語のような**形式言語(けいしきげんご、水準一: 曖昧さを許さない、厳密に定められた規則によって組み立て方が決まっている言語)**には、この「察する」能力がまったくない。ミナの`3 + 4 * 2`の例で見たとおり、同じ文字列に対して複数の読み方が成立してしまう性質を**曖昧性(あいまいせい、水準一: 同じ記号の並びが、複数の異なる構造・意味に解釈できてしまう性質)**と呼ぶ。人間同士の会話なら笑い話で済む曖昧性も、プログラムの世界では「今日は14になったが、明日は8になるかもしれない」という致命的な不具合の原因になる。コンピュータは常識を持たず、目の前の文字列を、あらかじめ決められた規則にただ機械的に従って処理するだけの存在だからである。
### 曖昧さを許さない、という設計思想
この違いを乗り越えるために、プログラミング言語の設計者たちは、文をどう組み立てるかという並び方の規則を指す**構文(こうぶん、水準一: 文をどのような順序・組み合わせで並べるかという、形の上でのルール)**を、一切の読み違いが起きないように、隅々まで厳密に定めておく。本冊が題材にするPICO語も、この「曖昧さをあらかじめ設計で潰しておく」という思想に沿って、一段ずつ規則を積み上げて作っていく小さな言語である。厳密さは不自由に思えるかもしれないが、裏を返せば「同じ入力には必ず同じ答えが返ってくる」という信頼性を生み出す土台でもある。
---
> **定着量の目安(第一章)**: 自然言語と形式言語の違い、曖昧性という概念を人に説明できるようにするには、身の回りの曖昧な日本語の例文(「ここでは着物を脱いでください」型の言葉遊び)を自分で3〜5個ほど探し、「人間はどの手がかりで意味を選んでいるか」「コンピュータならどこで詰まるか」を書き出してみる練習が有効である。
---
## 第二章: 字句解析 — 文字の並びをトークンに分ける(水準二〜三)
### 文字の川を単語の粒に区切る
`let x = 3 + 4 * 2;`という文字の並びを、コンピュータはまず一文字ずつの連続としてしか受け取らない。この文字の並びを、意味のある最小単位に切り分ける処理を**字句解析(じくかいせき、水準二: 文字の並びを、意味のある最小単位〈トークン〉に分割する処理。「レキシング」「スキャニング」とも呼ばれる)**と呼び、その最小単位一つひとつを**トークン(水準二: プログラムの文字列を、意味のある最小単位に区切ったときの、その一片)**と呼ぶ。字句解析を行う部品は**字句解析器(レキサー、水準二: 文字の並びをトークンの列に変換する部品)**と呼ばれ、PICO語の処理系(プログラムを読み解いて実行する仕組み全体を指す言葉)の入り口を担う。
### トークンの種類
PICO語のトークンは、おおむね次の種類に分けられる。
- **キーワード(予約語、水準二: あらかじめ言語の側で意味が決められていて、変数名などには使えない特別な単語)**――`let`・`if`・`else`のように、PICO語自身が意味を決めている単語。
- **識別子(しきべつし、水準二: 変数名や関数名など、プログラムを書く人が自由に名付けられる名前)**――`x`・`所持金`のように、プログラマが好きに付けられる名前。
- **リテラル(水準二: プログラムの中に直接書かれた値そのもの)**――`3`・`42`のような数値そのもの。
- **演算子(えんざんし、水準二: 値同士を計算したり比較したりするための記号)**――`+`・`-`・`*`・`/`・`=`・`==`など。
- **区切り記号(水準二: 文の構造の切れ目を示すための記号)**――`(`・`)`・`;`など。
### 検算1 — "let x = 3 + 4 * 2;" をトークン化する
先頭から一文字ずつ読み進め、空白で区切りながらトークンに分けると、次のようになる。
```
入力: let x = 3 + 4 * 2 ;
トークン列:
[KEYWORD:let] [IDENT:x] [OP:=] [NUM:3] [OP:+] [NUM:4] [OP:*] [NUM:2] [DELIM:;]
```
9文字の単語(let・x・=・3・+・4・*・2・;)が、9個のトークンにきれいに対応している。字句解析の時点では、まだ「掛け算を先に計算する」といった**意味**にはいっさい踏み込んでいないことに注意したい。ここでやっているのは、あくまで「文字の川を、意味のある粒に区切る」という機械的な下ごしらえだけである。
### コラム — 空白とコメントは「読み飛ばされる」トークン
字句解析器は、空白・改行・タブや、`# これはコメント`のようなコメントも一度は目にするが、これらはトークン列には残さず読み飛ばすのが一般的である。人間が読みやすくするための余白や注釈は、機械にとっては意味を持たない「捨ててよい情報」として扱われる、という点も、字句解析の重要な仕事の一つである。
---
> **定着量の目安(第二章)**: `let x = 3 + 4 * 2;`のような短い文を5〜10個自分で用意し、紙の上でキーワード・識別子・リテラル・演算子・区切り記号に手作業で色分けしてトークン列を書き出す練習を20問程度こなすと、字句解析の感覚がほぼ完全に定着すると見込まれる。
---
## 第三章: 文法規則を書き表す — BNFの基礎(水準四)
### 規則を規則として書き下す
字句解析でトークンの列ができても、それだけでは「どの順番で並べば正しい文になるか」がまだ決まっていない。この並び方の規則を、誰が読んでも同じように解釈できる形で書き表す記法が**BNF(バッカス・ナウア記法、水準四: 文法規則を「非終端記号 ::= 展開のしかた」という形で書き表す記法)**である。BNFでは、文法上の部品の名前であり、さらに他の規則へと展開されていく**非終端記号(ひしゅうたんきごう、水準四: それ自体はまだ具体的なトークンではなく、他の規則によってさらに詳しく展開される、文法上の部品の名前)**と、それ以上展開されず実際のトークンそのものを指す**終端記号(しゅうたんきごう、水準四: それ以上分解されない、実際のトークンそのものを表す記号)**を組み合わせて規則を書く。
### PICO語の文法(検算2)
PICO語がこれから扱う範囲の**文法(ぶんぽう、水準四: ある言語で許される文の組み立て方を、規則の集合として定めたもの)**を、BNFに近い書き方(EBNF、*は0回以上の繰り返し、?は0回か1回を表す)でまとめると、次のようになる。
```
program ::= statement*
statement ::= "let" IDENT "=" expr ";"
| "if" "(" expr ")" statement ("else" statement)?
| expr ";"
expr ::= term (("+" | "-") term)*
term ::= factor (("*" | "/") factor)*
factor ::= NUMBER
| IDENT "(" args? ")"
| IDENT
| "(" expr ")"
args ::= expr ("," expr)*
```
この文法は、この冊子全体を通じて何度も立ち返る「地図」になる。`program`(プログラム全体)は`statement`(文)の繰り返し、`statement`は`let`文・`if`文・ただの式文のいずれか、`expr`(式)は`term`の足し算・引き算の繰り返し、`term`は`factor`の掛け算・割り算の繰り返し、`factor`は数値・関数呼び出し・変数・カッコ付きの式のいずれか――という入れ子の構造になっている。
### コラム — BNFの生まれた場所
BNFという記法は、1960年に発表されたプログラミング言語ALGOL60の仕様書で整えられた記法として広く知られている。**ジョン・バッカス(John Backus)**がALGOL58の報告のために考案した記法を、**ピーター・ノーア(Peter Naur)**がALGOL60の仕様書でさらに整理し直したことから、二人の名前を取って「バッカス・ナウア記法」と呼ばれるようになった、というのが定番の紹介である。文法規則を厳密な記法で書き表すという発想は、その後もほとんどのプログラミング言語の仕様書で使われ続けている、息の長い道具である。
---
> **定着量の目安(第三章)**: 本章のPICO語文法(program・statement・expr・term・factor・args の6規則)を、何も見ずに自分の手で書き出せるようにし、さらに与えられた短い文が文法のどの規則の組み合わせで作られているかを口頭で説明する練習を10例ほどこなすと、水準四の内容がほぼ完全に定着すると見込まれる。
---
## 第四章: 構文解析 — トークンの列を「木」に組み立てる(水準五〜六)
### トークンの列から構造を取り出す
字句解析で得たトークンの列を、第三章の文法規則に従ってたどりながら、どの部分がどの部分にかかっているかがはっきりした構造に組み立てる処理を**構文解析(こうぶんかいせき、水準五: トークンの列を、文法規則に従って木構造に組み立てる処理。「パース」とも呼ばれる)**と呼ぶ。構文解析を行う部品は**構文解析器(パーサー、水準五: トークンの列を受け取り、文法規則に従って構造〈木〉を組み立てる部品)**と呼ばれ、字句解析器の直後に置かれる。
### 再帰下降パーサという作り方
構文解析器の作り方にはいくつかの流儀があるが、初めて自作するのに向いているのが**再帰下降パーサ(さいきかこうパーサー、水準六: 文法規則の一つひとつを、それぞれ対応する関数として実装し、規則同士の入れ子を関数呼び出しの入れ子でそのまま表現するパーサの作り方)**である。この作り方は特定の一人の発明者に帰属させられるようなものではなく、1960年代以降、多くの実装者たちが独立にたどり着いた、素朴で応用範囲の広い技法として知られている。名前のとおり、`expr`という規則には`parse_expr()`という関数を、`term`という規則には`parse_term()`という関数を、一対一で対応させ、規則の中で他の規則を呼び出す部分は、そのまま関数呼び出しとして書く。
### 検算3 — parse_expr() でトークン列をたどる
`3 + 4 * 2`のトークン列 `[NUM:3] [OP:+] [NUM:4] [OP:*] [NUM:2]` を、第三章の文法に従って擬似コードでたどってみる。
```
関数 parse_expr():
左辺 = parse_term() # まず term を読む → 3
くり返し 次のトークンが "+" か "-" の間:
演算子 = 今のトークンを消費
右辺 = parse_term() # 次の term を読む
左辺 = ノード(演算子, 左辺, 右辺) # 二つをまとめて新しい木にする
返す 左辺
関数 parse_term():
左辺 = parse_factor() # まず factor を読む
くり返し 次のトークンが "*" か "/" の間:
演算子 = 今のトークンを消費
右辺 = parse_factor()
左辺 = ノード(演算子, 左辺, 右辺)
返す 左辺
```
`3 + 4 * 2`にこの手順を当てはめると、`parse_expr()`はまず`parse_term()`を呼ぶ。`parse_term()`は`parse_factor()`で`3`を読み取ったあと、次のトークンが`+`(掛け算でも割り算でもない)なのでそこで止まり、`3`だけを`parse_expr()`に返す。`parse_expr()`は次のトークンが`+`なので消費し、もう一度`parse_term()`を呼ぶ。今度は`parse_term()`が`4`を読んだあと次のトークンが`*`なので、`4`と`2`を`*`でまとめた小さな木を作ってから返す。最後に`parse_expr()`が、さきほどの`3`と、いま返ってきた「`4*2`の木」を`+`でまとめる。この「小さい規則から呼び出して、返ってきた結果を大きい規則が組み立てる」という流れこそが、再帰下降パーサの骨格である。
---
> **定着量の目安(第四章)**: `parse_expr()`・`parse_term()`・`parse_factor()`の3つの関数の呼び出し順を、`10 - 3 - 2`や`(3+4)*2`など5個ほどの短い式について、自分の手で紙に書き下す練習を行うと、再帰下降パーサの流れがほぼ完全に定着すると見込まれる。
---
## 第五章: 演算子の優先順位と結合則(水準七)
### なぜ文法の「層」が優先順位を決めるのか
第三章の文法をよく見ると、`expr`(足し算・引き算の層)が`term`(掛け算・割り算の層)を内側に含む、という入れ子の順番になっている。**演算子の優先順位(えんざんしのゆうせんじゅんい、水準七: 複数の演算子が並んだとき、どれを先に計算するかを決める順位)**は、この文法の層の深さによって自然に表現される。内側の層(`term`)ほど先に組み立てられ、外側の層(`expr`)はそれを部品として扱うため、掛け算・割り算が足し算・引き算より先に計算される、という規則が、特別な条件分岐を書かなくても文法の形だけで実現されている。
### 検算4 — "2+3*4"はなぜ14になるのか
第四章の手順で`2+3*4`をたどると、`parse_term()`が先に`3*4`を`12`相当の一つの木にまとめ、`parse_expr()`がその木と`2`を`+`でまとめる。結果として組み上がる木は「`+`の下に、左に`2`、右に`3*4`の木」という形になり、これを根から評価すると`2+(3*4) = 2+12 = 14`になる。もし文法の層を逆にして`+`を内側、`*`を外側にしてしまうと、`2+3`が先にまとめられて`(2+3)*4=20`という、掛け算優先の規則に反した誤った木になってしまう。文法の層の順番そのものが、優先順位のルールを体現している、という点が、この検算のいちばんの要点である。
### 検算5 — "10-3-2"はなぜ5になるのか
同じ優先順位の演算子が並んだとき、左右どちら向きにまとめるかを決める規則を**結合則(けつごうそく、水準七: 同じ優先順位の演算子が連続したとき、左右どちらの向きから先にまとめるかを決める規則)**と呼ぶ。第四章の`parse_expr()`の「くり返し」の書き方(左辺を更新しながらループする形)は、常に**左から**まとめていく**左結合(ひだりけつごう、水準七: 同じ優先順位の演算子が並んだとき、左側から先にまとめる結合則)**を表している。`10-3-2`であれば、まず`10-3=7`の木ができ、その`7`と`2`をもう一度`-`でまとめて`7-2=5`になる。もし右結合(右側から先にまとめる)で解釈してしまうと`10-(3-2)=10-1=9`になり、答えが変わってしまう。PICO語の四則演算はすべて左結合であり、この左結合という決まりのおかげで`10-3-2`は常に`5`という一つの答えに定まる。
---
> **定着量の目安(第五章)**: `2+3*4`・`10-3-2`・`2*3+4*5`・`(2+3)*(4-1)`のような式を10問ほど選び、それぞれについて「どちらの演算が先に木にまとまるか」を自分の手で図示して答えを検算する練習をすると、優先順位と結合則の感覚がほぼ完全に定着すると見込まれる。
---
## 第六章: 構文木(AST)を作る(水準八)
### 文の構造を木の形で描く
構文解析によって組み上がった、文の構造を根・枝・葉を持つ木の形で表したものを**構文木(こうぶんぎ、水準八: 文の構造を、根〈ルート〉・枝・葉を持つ木の形で表したもの)**と呼ぶ。中でも、区切り記号やカッコなど「木の形そのものに情報が残っていて省いてよい部分」を取り除き、演算子と値だけを残した、より簡潔な木を**抽象構文木(ちゅうしょうこうぶんぎ、AST、水準八: 構文木から、カッコなどの見た目上の情報を取り除き、演算子と値だけを残した、より簡潔な木構造)**と呼ぶ。この冊子で扱ってきた検算3・検算4の「ノード(演算子, 左辺, 右辺)」という組み立て方は、まさにこのASTを作る操作そのものである。
### 検算6 — "2+3*4"のASTを描く
第五章の検算4で組み立てた木を、ASCII図として描くと次のようになる。
```
+
/ \
2 *
/ \
3 4
```
根には`+`が置かれ、その左の枝には`2`という値がそのまま、右の枝には`*`を根とするもう一つの小さな木が伸びている。この木を根から評価すれば、右の`*`の枝がまず`3*4=12`を計算し、それから根の`+`が`2+12=14`を計算する、という手順が、木の形からそのまま読み取れる。カッコ`(3+4)*2`のASTも見ておくと、`(`と`)`という記号そのものは木の中に残らず、「`+`の木がまるごと`*`の左側の子になる」という**位置**によって、カッコの意味が表現されていることが分かる。
```
*
/ \
+ 2
/ \
3 4
```
---
> **定着量の目安(第六章)**: `10-3-2`・`(3+4)*2`・`2*3+4*5`など5〜8個の式について、自分の手でASTをASCII図として描き、根から葉までの評価順を矢印でなぞる練習をすると、水準八の内容がほぼ完全に定着すると見込まれる。
---
## 第七章: 意味論の基礎 — 木を「評価」する(水準九〜十)
### 木をたどって実際に計算する
構文木ができても、それはまだ「構造」でしかなく、実際の答えは出ていない。プログラムの構文が「実際に何を行うか」を定める規則を**意味論(いみろん、水準九: プログラムの構文が、実際に何を行うか〈どんな値を生み出すか、どんな効果を起こすか〉を定める規則)**と呼び、構文木をたどりながら実際に計算を実行して値を求める処理を**評価(ひょうか、水準九: 構文木を根から〈または葉から〉たどりながら、実際に計算を実行して値を求める処理)**と呼ぶ。評価を行う部品はしばしば**評価器(エバリュエータ、水準九: 構文木を受け取り、それをたどって実際の値を計算する部品)**と呼ばれ、ここまで作ってきた字句解析器・構文解析器の、いわば最後の仕上げを担う。
### 検算7 — ASTを評価して14を得る
検算6で描いた`2+3*4`のASTを、擬似コードで評価する手順は次のようになる。
```
関数 eval(ノード):
もし ノードが数値なら:
返す その数値
もし ノードが演算子なら:
左の値 = eval(ノードの左の枝)
右の値 = eval(ノードの右の枝)
もし 演算子が "+" なら 返す 左の値 + 右の値
もし 演算子が "*" なら 返す 左の値 × 右の値
…(以下 "-" "/" も同様)
```
`eval(根の+)`を呼ぶと、まず左の枝`eval(2)`が`2`を返す。次に右の枝`eval(*)`が呼ばれ、その中でさらに`eval(3)`と`eval(4)`が呼ばれて`3`と`4`が返り、`3×4=12`が計算される。最後に根の`+`が、`2`と`12`を受け取って`2+12=14`を返す。木の葉(いちばん端の値)から計算が始まり、根に向かって値が積み上がっていく――という流れが、評価という処理の実体である。
### 変数と環境
`let x = 3 + 4 * 2;`のような、名前に値を結びつける文を評価するには、変数名と値の対応を記録しておく表が必要になる。この表を**環境(かんきょう、水準十: 変数名と値の対応を記録しておく表)**と呼ぶ。`let`文を評価するときは、右辺の式`3+4*2`をまず`eval()`で`14`まで計算し、その結果を環境の中で`x`という名前に結びつける。以降、`x`という識別子が式の中に現れるたびに、評価器はこの環境を調べて`14`という値を取り出す。
変数が意味を持つ範囲を**スコープ(水準十: ある変数名が、プログラムのどの範囲で有効かという範囲)**と呼ぶ。PICO語のように「プログラム全体で一つの環境を共有する」という単純な作りでもプログラムは書けるが、実用の言語の多くは、関数の中だけで有効な変数を持てるように、複数の環境を入れ子にする仕組みを備えている。この入れ子の仕組みは、より発展的な話題として次巻以降に譲る。
### 検算8 — "let x = 3 + 4 * 2; x * 2" を評価する
```
1行目: let x = 3 + 4 * 2;
→ 右辺を eval() すると 14
→ 環境に x = 14 を記録
2行目: x * 2;
→ eval(x) は環境を調べて 14 を返す
→ 14 × 2 = 28
```
1行目で環境に記録された`x = 14`が、2行目の評価で正しく再利用され、最終的な答え`28`が得られる。字句解析(第二章)でトークンに分け、文法(第三章)に従って構文解析(第四章)で木を組み立て、演算子の優先順位(第五章)を反映したAST(第六章)を、環境を持つ評価器(本章)でたどる――ここまでで、PICO語は「2+3*4」を正しく計算できる小さなインタプリタとしての骨格を、一通り備えたことになる。
---
> **定着量の目安(第七章)**: `let a = 2 * 3; let b = a + 4; b - 1`のような、複数行にわたって変数を使い回す文を5〜8個自分で作り、環境の中身がどう更新されていくかを表にして書き出す練習をすると、意味論と環境の感覚がほぼ完全に定着すると見込まれる。
---
## 第八章: 先読み(lookahead)とは何か(水準十一)
### 次を覗いてから決める
ここまでのパーサは、多くの場面で「次のトークンを一度覗いてから、消費するかどうかを決める」という動作を暗黙のうちに行ってきた。この、次のトークンを実際に消費する前にあらかじめ覗き見て、どの文法規則を適用するかを決めるための処理を**先読み(さきよみ、lookahead、水準十一: 次のトークンを実際には消費せずに覗き見て、どの規則を適用すべきかを判断するための処理)**と呼ぶ。
### 検算9 — "=" と "==" を字句解析で区別する
字句解析の段階でも、先読みは欠かせない。PICO語の字句解析器が`=`という文字を読んだとき、そのすぐ次の文字も`=`であれば、`=`(代入)ではなく`==`(等しいかどうかを調べる比較演算子)という、まったく別のトークンとして扱わなければならない。1文字だけ先を覗いてから、より長く一致する側を優先してトークンを確定させるこの規則を**最長一致(さいちょういっち、maximal munch、水準十一: 字句解析で複数の解釈が可能なとき、もっとも長く一致するトークンを優先して選ぶ規則)**と呼ぶ。
```
入力: x == 5
1文字目 "=" を読む → 次の文字を1文字だけ先読み
次も "=" だった → "==" という1つのトークンとして確定
(もし次が "=" でなければ、"=" 単独のトークンとして確定)
```
### 検算10 — 関数呼び出しか、ただの変数か
第三章の文法をもう一度見ると、`factor`の規則には`IDENT "(" args? ")"`(関数呼び出し)と`IDENT`(ただの変数)の二通りがあった。パーサが識別子`f`を読んだ時点では、まだこの`f`が関数呼び出しなのか、ただの変数参照なのかは決められない。そこで、識別子を読んだ**直後の1個先のトークン**を覗き見て、それが`(`であれば関数呼び出し、そうでなければただの変数参照、と決める。
```
関数 parse_factor():
もし 次のトークンが NUMBER なら 消費して数値ノードを返す
もし 次のトークンが IDENT なら:
名前 = 消費する
もし その次のトークンが "(" なら: # 1個先読み
"(" を消費し、args を読み、")" を消費
返す 関数呼び出しノード(名前, 引数)
でなければ:
返す 変数参照ノード(名前)
もし 次のトークンが "(" なら:
"(" を消費し、expr を読み、")" を消費
返す その式の木
```
このように、次に来る1個のトークンだけを覗けば、どの規則を適用すべきかが一意に決まる文法を**LL(1)文法(水準十一: 左から読み進めながら〈Left-to-right〉、左側の規則から順に展開し〈Leftmost derivation〉、1個先のトークンを覗くだけで次の規則が一意に決まる文法)**と呼ぶ。PICO語のこれまでの規則は、おおむねこのLL(1)の範囲に収まるように設計されている。
---
> **定着量の目安(第八章)**: `y(3+4)`と`y`だけの2種類の入力、`<`と`<=`のような2文字にまたがる可能性のある記号を含む短い式を5〜8個作り、それぞれ「何文字(何トークン)先読みすれば区別できるか」を自分の手で書き出す練習をすると、先読みという概念がほぼ完全に定着すると見込まれる。
---
## 第九章: 先読みが必要になる曖昧な文法の実例と解決法(水準十二)
### 曖昧な文法1 — ぶら下がりelse問題
入口の物語でミナがつまずいた`if 所持金 >= 100 then 開ける else if 鍵 == true then 壊す`のような、`if`文が入れ子になった文には、古くから知られた曖昧性がある。これを**ぶら下がりelse問題(ダングリングelse、水準十二: if文が入れ子になったとき、elseがどちらのifに属するのか、文法上一意に決まらなくなる曖昧性の代表例)**と呼ぶ。第三章の文法`"if" "(" expr ")" statement ("else" statement)?`をそのまま使うと、`if (a) if (b) x; else y;`という一文には、次の二通りの木が両方とも文法上「正しい」ことになってしまう。
```
解釈A(elseが内側のifに属する): 解釈B(elseが外側のifに属する):
if (a) if (a)
if (b) x; else y; if (b) x;
else y;
```
厳密に言えば、この問題は「1個先を覗けば済む」という意味での先読みだけでは解決しない。文法そのものが、elseの所属先について複数の木を許してしまっているため、いくら先を覗いても、文法上はどちらも正しいままだからである。この曖昧性を取り除くには、文法の側に判断基準を追加するしかない。実際に広く使われている解決法は二つある。
1. **「elseは直前の、まだelseと組んでいない一番近いifに属する」という規約を追加する**――C言語をはじめ多くの言語がこの規約を採用しており、解釈Aが常に選ばれることになる。曖昧な木の候補が複数あっても、規約によってどちらか一方だけを常に選ぶ、という解決法である。
2. **文法そのものを、曖昧さが生じないように書き換える**――たとえば`if`文の終わりに明示的な区切り(`end`や`fi`のような単語)を必ず書かせるようにすれば、`if (a) if (b) x; end else y; end`のように、どのelseがどのifに対応するかが記号の上ではっきりし、そもそも曖昧な解釈が生まれなくなる。
### 曖昧な文法2 — 識別子の直後は先読みで決着がつく好例
一方、検算10で見た「識別子の直後が`(`かどうか」という判断は、1個先を覗くだけで確実にどちらか一方に決まる、健全な先読みの例である。ぶら下がりelse問題との違いは、こちらは文法自体が曖昧なのではなく、パーサが判断に必要な情報(次のトークン)を、実際に確認する前に決めてしまっていた点にある。先読みという道具は、「文法上は一意に決まるが、パーサの実装がまだその情報を見ていないだけ」というケースには非常によく効くが、「文法そのものが複数の木を許してしまっている」というケースには効かない、という違いを押さえておくことが大切である。
### コラム — 1個先読みでも足りないとき
文法によっては、1個先のトークンを覗くだけでは規則が一意に決まらず、2個・3個と先まで覗く必要がある場合もある。このような文法を一般に**LL(k)文法(水準十二: k個先のトークンまで覗けば、次の規則が一意に決まる文法)**と呼ぶ。さらに、何個先まで覗いても決められない、より込み入った文法に対しては、ある規則をいったん試してみて、途中で行き詰まったら読み進めた位置を巻き戻して別の規則を試す**バックトラック(水準十二: ある規則を試してみて失敗したら、読み進めた位置を巻き戻して、別の規則を最初からやり直す解析方法)**という手段が使われることもある。ただし、覗く先が増えるほど、また巻き戻しが増えるほど、パーサの実装は複雑になり、処理に時間もかかるようになる。PICO語のような教育用の小さな言語では、なるべく1個先読み(LL(1))の範囲に収まるように文法そのものを設計しておく、という方針が、実装の単純さと動作の速さの両方を守るうえで理にかなっている。
---
> **定着量の目安(第九章)**: `if (a) if (b) x; else y;`について解釈Aと解釈Bの木をそれぞれ自分の手で描き分け、「規約を追加する解決法」と「文法を書き換える解決法」のそれぞれで曖昧性がどう消えるかを説明できるようにする練習を行うと、水準十二の内容がほぼ完全に定着すると見込まれる。
---
## 三つの実践解(§16.21) — 紙と手だけでできる実践
コンピュータを使わなくても、紙と鉛筆だけで確かめられる実践を三つ紹介する。
1. **手トークン化実践**: 自分で短いPICO語の文を5個ほど考え(例: `let 得点 = 10 + 5 * 2;`)、第二章の分類(キーワード・識別子・リテラル・演算子・区切り記号)に従って、一文字ずつ手で色分けしながらトークン列を書き出す。字句解析器が「機械的に」やっていることを、自分の手で追体験する練習である。
2. **手パース木実践**: 第三章の文法を横に置きながら、`(2+3)*4-1`のような少し込み入った式について、第四章の`parse_expr()`・`parse_term()`・`parse_factor()`の手順を紙の上でたどり、第六章のようなASCII図でASTを描く。木が正しく描けたら、第七章の`eval()`の手順で根まで値を積み上げ、電卓で計算した答えと一致するかを検算する。
3. **(発展)実在の言語での確認実践**: 手元にPython・JavaScriptなど使い慣れたプログラミング言語の実行環境があれば、`print(2+3*4)`のように本冊で扱った式をそのまま実行し、結果がPICO語の検算(検算4など)と一致することを確かめる。さらに余裕があれば、`if`文をわざと入れ子にして、その言語がぶら下がりelse問題をどちらの規約(規約追加型か、インデント・波かっこによる明示型か)で解決しているかを、公式ドキュメントで調べてみるとよい。
---
## まとめ — 曖昧さを消しながら積み上げる
本冊では、`2+3*4`という式が期待どおりの答えを返さなかったミナの物語から出発し、自然言語と形式言語の違い(第一章)、字句解析でトークンに分ける処理(第二章)、BNFで文法規則を書き表す方法(第三章)、再帰下降パーサでトークンの列を木に組み立てる構文解析(第四章)、演算子の優先順位と結合則が文法の層で表現される仕組み(第五章)、構文木(AST)の描き方(第六章)、木を実際に計算する意味論と、変数を記録する環境(第七章)、次のトークンを覗いてから判断する先読み(第八章)、そして先読みだけでは解決できない、ぶら下がりelse問題のような真に曖昧な文法の実例と、その二つの解決法(第九章)までをたどってきた。
字句解析でトークンに分け、文法規則で並び方を定め、構文解析で木を組み立て、優先順位と結合則で計算の順番を確定させ、意味論と環境で実際の値を求め、先読みで次に来るものをあらかじめ判断する――この一直線の積み上げこそが、「自分だけの言語」を設計するための骨格である。本冊で扱ったのはPICO語という小さな算術・変数・条件分岐だけの言語だが、ここで身につけた考え方は、より大きなプログラミング言語の処理系にもそのまま応用できる土台になっている。
---
## 章末: 簡易構文木とまとめの階段図
まずは検算4〜検算7で組み立てた`2+3*4`のASTと、その評価の流れを、あらためてASCII図で確認しておく。
```
構文木: +
/ \
2 *
/ \
3 4
評価の流れ: eval(2)=2, eval(3)=3, eval(4)=4
→ 3×4=12 (termの層が先にまとまる)
→ 2+12=14 (exprの層が最後にまとまる)
```
続いて、本冊全体の歩みを階段図としてまとめる。
```
[水準十二] 先読みでも解決しない曖昧な文法
ぶら下がりelse問題 → 規約追加 or 文法書き換え(第九章)
▲
│ 「規則が決まらない」場合と「情報を見ていないだけ」の場合を分ける
[水準十一] 先読み(lookahead)
"="と"=="の最長一致/識別子直後の"("判定(検算9・10)
▲
│ 次のトークンを消費前に覗く
[水準九〜十] 意味論・評価・環境
eval(2+3*4)=14/let x=…でx=14を環境に記録(検算7・8)
▲
│ 木を実際にたどって値を求める
[水準八] 構文木(AST)
根に演算子、葉に値(検算6)
▲
│ 木の形で構造を描く
[水準七] 演算子の優先順位と結合則
2+3*4=14(層の入れ子)/10-3-2=5(左結合)(検算4・5)
▲
│ 文法の層が計算順を決める
[水準五〜六] 構文解析・再帰下降パーサ
parse_expr()→parse_term()→parse_factor()(検算3)
▲
│ トークン列を木に組み立てる
[水準四] 文法規則(BNF)
program/statement/expr/term/factor/args の6規則(検算2)
▲
│ 並び方の規則を厳密に書き表す
[水準二〜三] 字句解析
"let x = 3+4*2;" → 9個のトークン(検算1)
▲
│ 文字の川をトークンに区切る
[水準一] 自然言語と形式言語の違い
曖昧性を許す/許さない、という設計思想の分かれ目
安全枠: 教育用トイ言語(PICO語)の設計にとどめ、難読化・マルウェア生成技術は扱わない。
```
---
## 参照文献(定番教科書・一般に確立した内容)
1. コンパイラ・プログラミング言語処理系の標準的な入門教科書群(字句解析・構文解析・再帰下降パーサ・意味論・先読みを扱う、大学初年次〜情報工学系で広く使われている定番の入門書群)。
2. ALGOL60仕様書(1960年)におけるバッカス・ナウア記法(BNF)の整備――ジョン・バッカスの原案とピーター・ノーアによる整理として広く紹介される経緯。
3. 再帰下降パーサ(Recursive Descent Parsing)という技法――特定の単一の発明者に帰属させられる技術ではなく、1960年代以降、多くの実装者によって独立に確立され、広く使われてきた技法として紹介される。
4. LL(1)文法・先読み・バックトラックという、構文解析理論の基礎概念(形式言語理論・コンパイラ理論の定番教科書で広く扱われる内容)。
---
(本冊子は現代学問宇宙図鑑シリーズ BOOK-0341。応用の軌道ステーション群「作る力と生きる力」シリーズ・計算機文明部の第2巻(自分の言語を作る 第1巻)。接続先の→BOOK-0342(論理回路からCPUへ)・→BOOK-0343(情報構造の設計)・→BOOK-0344(文章の解析と解読)は、いずれも本冊で組み立てたPICO語の骨格を土台として発展させる予定である。GAKUMON_UNIVERSE.md 進捗台帳・CATALOG_作る力と生きる力シリーズ.mdを参照。)
# BOOK-0341 計算機文明: 自分の言語を作る 第1巻 — コンピュータが迷わない言葉のつくり方