文脈自由文法：構文木が育つ
文法規則 E → E + E | E * E | ( E ) | num から文字列を導出し、構文木が枝分かれして育つ様子を見ます。あいまい文法では同じ文字列に 2 通りの木ができることも体感します。
文脈自由文法（CFG）は「非終端記号 → 記号列」という生成規則の集まりです。開始記号
1 つの文字列に対し木が 2 通り以上作れる文法をあいまい（ambiguous）といい、計算結果が変わってしまいます。スライダーとボタンで木を育て、あいまいさと優先順位の必要性を確かめましょう。
E から規則を次々に適用して非終端記号を置き換えていくと、最後は終端記号（数や記号）だけの文字列が得られます。この置き換えの過程を木で表したものが構文木（解析木）です。1 つの文字列に対し木が 2 通り以上作れる文法をあいまい（ambiguous）といい、計算結果が変わってしまいます。スライダーとボタンで木を育て、あいまいさと優先順位の必要性を確かめましょう。
入力式（終端記号の並び）を選ぶ
—
この文法 G（開始記号 E）
E → E + E
| E * E
| ( E )
| num
| E * E
| ( E )
| num
凡例
青丸＝非終端記号 E（まだ育つ）
緑角＝終端記号（木の葉）
黄＝次に展開する記号
緑角＝終端記号（木の葉）
黄＝次に展開する記号
構文木が育つ（左端最導出 / leftmost）
展開ステップ
—
残り非終端記号
—
木の葉（終端記号）
—
木の高さ
—
いま何が起きている？
あいまいさ：同じ文字列で 2 通りの木
文字列 1 + 2 * 3 はこの文法で2 通りに解析できます。
+ と * のどちらを木の上（＝後で計算）に置くかで結果が変わります。
木 A：
(1 + 2) * 3 として読む = 9木 B：
1 + (2 * 3) として読む = 7
同じ 1 + 2 * 3 でも、木 A（(1 + 2) * 3）は 9、木 B（1 + (2 * 3)）は 7 と、木の形が違うだけで計算結果が変わってしまいます ── これがあいまい文法の困りごとです。
* を + より優先するという規則を文法に組み込めば木は B の 1 通りに定まり、ふつうの算数（= 7）と一致してあいまいさが消えます。
ここがポイント
- 導出 = 木の成長 ── 規則
E → …を 1 回使うたびに、葉だった非終端記号 E が子を持つ枝になる。 - 葉は終端記号だけ ── すべての非終端記号が消えたとき、木は完成し、葉を左から読むと元の文字列になる。
- あいまい文法では同じ文字列に複数の木があり、構文木が違えば計算結果も変わる。
- 優先順位・結合規則（例：* は + より先）を文法に組み込めば木が一意に決まり、あいまいさが消える。