再帰下降構文解析：規則を降りていく

式を expr → term → factor と再帰的に「降りて」いき、構文木を組み立てます。コールスタックと構文木を同時に見ると、演算子の優先順位が木の形に現れるのがわかります。

式を入力（数字 0–9 と + - * / ( ) が使えます）

数式プリセット（押すと読み込み）

ステップ位置 0 / 0

使っている文法（LL(1) の式文法）

expr → term ( ('+' | '-') term )*
term → factor ( ('*' | '/') factor )*
factor → number | '(' expr ')'

入力（残りトークン）

—

いま見ているトークン

—

コールスタックの深さ

現在の規則

—

コールスタック（下＝最初の呼び出し、上＝いま実行中）

構文木（できあがってきた部分）

再帰下降構文解析（recursive descent parsing）は、文法の規則 1 つひとつをそのまま 1 つの関数にして、上位の規則から下位の規則へ関数呼び出しで「降りて」いく解析法です。
式の文法では、足し算/引き算を扱う expr が、掛け算/割り算を扱う term を呼び、 term が数や括弧を扱う factor を呼びます。優先順位の低い演算子ほど木の上（根に近い側）に来るのは、expr が一番外側で呼ばれるからです。
括弧が来ると factor の中からもう一度 expr を呼ぶ ── ここで再帰が起きます。だからコールスタックが深くなり、その中に小さな部分木ができていきます。
式を入力するかプリセットを選び、スライダーやボタンで 1 ステップずつ「降りて・戻って」、コールスタックと構文木が連動する様子を追ってみましょう。

いま何が起きている？

ここがポイント

規則 = 関数 ── expr / term / factor がそれぞれ関数で、文法の階層がそのまま呼び出しの階層になる。
優先順位は呼び出し順に現れる ── 外側の expr が + -、内側の term が * / を扱うので、1+2*3 では * が下に潜り + が根になる。
括弧で再帰する ── factor が ( を見ると中で expr を呼び直す。コールスタックが深くなり、優先順位の壁ができる。
左から1トークン先読み ── 次の記号 1 個を見て次の規則を選ぶ LL(1)。バックトラックなしで構文木を 1 パスで組める。