Table of Contents

文法の読み方

このマニュアルはこの 小さな文法一つ を主な例として使います（ε のような特別な概念には、ときどき小さな補助文法を別に見せます）。
本格的な内容に入る前に、この文法を 読める ようになっておきたいですよね。
心配いりません — 記号はたった四つ 覚えれば、すらすら読めます。
一緒にゆっくり分解していきましょう。

これがその文法です。
初めて見ると記号が多くて、少し見慣れないかもしれません。

Expr   : Expr '+' Term | Term ;
Term   : Term '*' Factor | Factor ;
Factor : '(' Expr ')' | id ;
id     := "[a-zA-Z]+" ;

🎨 色のヒント — 紫 は 非終端記号、青緑 は 終端記号 です。（どちらもすぐ下できちんと説明します。今は「色の違う二種類があるんだな」だけで。）

記号は四つ

記号 意味 わかりやすく言うと
: 「〜はこう作られる」 左の名前を、右の方法で作る
| 「または」 作り方が複数あるときに分ける
; 「このルールはここまで」 文末のピリオドのようなもの
'+' (引用符) 文字そのもの 画面に本当に表示される + 記号

最初の行を日本語に訳すと

Expr : Expr '+' Term | Term ;

→ 「Expr はこう作れる：Expr のあとに +、そのあとに Term、または ただの Term 一つ。」

ゆっくりもう一度読んでみてください。
: は「〜はこう作る」、| は「または」、; は「ここまで」。
難しくないでしょう？

ちょっと待って、Expr の中にまた Expr があります（再帰）

気づきましたか？
Expr を説明しているのに、その中にまた Expr が出てきます。
自分が自分を指しているのです。
これを 再帰（recursion） と呼びます。

「あれ、無限ループじゃないの？」と不安になるかもしれませんが — 大丈夫。まったく問題ありません。
これはただ 「+ でいくつもどんどんつなげられる」 という意味なだけです。
たとえば a + a + a のように。
（a + a が Expr で、そこにさらに + a をくっつけたわけです。）
自然ですよね？
再帰という単語が怖いだけで、中身は「いくつもつなげる」だけがすべてです。

残りの行も同じ調子です

  • Term : Term '*' Factor | Factor ; → 「Term は Term * Factor、または Factor 一つ。」（* 掛け算でつなげるもの）
  • Factor : '(' Expr ')' | id ; → 「Factor は ( Expr )（括弧で包んだ式）、または id（名前一つ）。」

最後の行だけ少し違います

id := "[a-zA-Z]+" ;

→ 「id はアルファベットの文字でできたトークンだよ。」

ここの "[a-zA-Z]+" は 正規表現（regular expression） というものです。
でも — 正規表現を知らなくても本当に大丈夫です。
今はただ 「英語のアルファベットでできた名前」（例：a、x、foo）くらいに理解しておけば100%十分です。
（:= は「これは文字パターンで定義するトークンだよ」という印です。）

いま私たちが読んだそれ — 名前があります

ここまで来たら、この文法を 読めるように なったということです。
そして — いま私たちが扱った、このように ルールで文法を書く表記法 には名前があります。
EBNF（Extended Backus–Naur Form、「拡張バッカス–ナウア記法」）と呼びます。
名前は仰々しいですが、形はたったいま見たものがすべてです。
これから誰かが「EBNF」と言ったら 「ああ、あのルールを書く書き方ね！」 と思えばいいのです。
専門用語を一つゲットしましたね 😎

単語はたった二つ：終端記号 / 非終端記号

最後に単語を二つだけ。
文法の中の名前たちは二種類に分かれます。
この二つを区別できれば終わり です。

  • 非終端記号（non-terminal） = さらに分解できる 「ルール名」 → Expr, Term, Factor （右側に「作り方」が書いてありますよね。）
  • 終端記号（terminal） = これ以上分解できない 「実際のトークン」 → +, *, (, ), id （入力に本当に登場する断片。）

なぜこんな名前なのかというと — 「終端記号（終端、terminal）」は 終わり、終着点 という意味です。これ以上 分解するものがなくて、そこで「終わる」からです。非 終端記号はその逆 — まだもっと展開できるものが残っているのです。 名前の意味を知っておくだけでも、混乱することがぐっと減ります。

たとえるなら — 非終端記号は「料理の名前」（例：キムチチゲ）、終端記号は「実際の材料」（キムチ、豆腐、水）です。
料理の名前は別の料理や材料で展開できますが、材料はそれ自体で終わりです。

一行まとめ：大文字で始まる（Expr, Term…）は非終端記号、記号や id は終端記号。
（さきほどの料理/材料のたとえで言えば — 非終端記号 = 料理の名前、終端記号 = 材料。）

次の章

文法が読めるようになりました！
いちばんの難所は、実はたったいま越えました 👍
さあ、LR 構文解析の最初の概念、FIRST / FOLLOW へ進みます。

👉 FIRST / FOLLOW

Edit this page