構文解析（字句解析と構文木）
数式をトークンに分け、再帰下降法と操車場アルゴリズムで構文木を組み立てる様子を 1 手ずつ表示します。演算子の優先順位と結合の向き、エラーの位置、構文木からの計算と逆ポーランド記法も確かめられます。
1. 字句解析（トークンに分ける）
空白を読み飛ばし、数・名前・記号のまとまり（トークン）に切り分けます。
2. 構文解析（構文木を組み立てる）
同じ式を 2 つの方法で解析できます。どちらも同じ構文木になります。
式を読み終えて、部分木を呼び出し元に返す((-(x ^ 2)) + (4 * x))
次に読むトークン
呼び出しの積み重なり（上が今の規則）
- 式
文法（規則 1 つが関数 1 つ）
| 式 | := | 項 (("+" | "-") 項)* |
| 項 | := | 単項 (("*" | "/" | "%") 単項)* |
| 単項 | := | "-" 単項 | べき |
| べき | := | 基本 ("^" 単項)? |
| 基本 | := | 数 | 名前 | 名前 "(" 式 ("," 式)* ")" | "(" 式 ")" |
優先順位の低い演算子ほど外側の規則（式）で扱うので、優先順位の高い演算子が木の下のほうに入り、先に計算されます。
3. 構文木と計算
構文木を帰りがけ順（子を先に）にたどって計算します。丸の右上の小さな数字は計算した順番、下の数字はその節点の値です。
- 計算の結果
- 3
- すべて括弧で囲んだ式
- ((-(x ^ 2)) + (4 * x))
- 逆ポーランド記法（後置記法）
- x 2 ^ neg 4 x * +
再帰下降法と操車場アルゴリズムは同じ構文木を作りました。neg は符号の反転、max/3 は引数 3 つの max です。逆ポーランド記法は、左から読んで数をスタックに積み、演算子が来たら積んだ数を取り出して計算すれば、括弧なしで計算できます。
演算子の優先順位
順位が大きいほど先に結びつきます。左結合は左から（8 − 3 − 2 = (8 − 3) − 2）、右結合は右から（2 ^ 3 ^ 2 = 2 ^ (3 ^ 2)）まとめます。
| 演算子 | 意味 | 順位 | 結合 |
|---|---|---|---|
| ^ | べき乗 | 4 | 右 |
| -（前置） | 符号の反転（-x） | 3 | 右 |
| * | 掛け算 | 2 | 左 |
| / | 割り算 | 2 | 左 |
| % | 余り | 2 | 左 |
| + | 足し算 | 1 | 左 |
| - | 引き算 | 1 | 左 |
使い方
- 例を選ぶか、式を入力します。x の値を変えると計算の結果が変わります。
- 「再帰下降法」と「操車場アルゴリズム」を切り替え、再生や ◀ ▶ で 1 手ずつ進めます。キーボードの ← → でも動かせ、Home / End で最初と最後に移ります（入力欄にフォーカスがないとき）。
- 書き間違えた式では、どこで何がおかしいかを ^ で示します。
プログラムが式を理解するまで
コンパイラやインタプリタ、表計算ソフトの数式は、まず文字の並びを意味のあるまとまり（トークン）に切り分け（字句解析）、次にトークンの並びが文法に合っているかを確かめながら木の形にまとめます（構文解析）。この木を構文木（抽象構文木、AST）といい、括弧や優先順位の情報は木の形そのものに表れます。あとは木をたどれば計算でき、コンパイラなら機械語に変換できます。
再帰下降法と操車場アルゴリズム
再帰下降法は、文法の規則 1 つを関数 1 つにして、規則が別の規則を含むところで関数を呼び出す方法です。文法をそのままコードにでき、エラーの説明もしやすいので、多くの言語の処理系が手書きの再帰下降法を使っています。優先順位が増えるたびに規則（関数）が 1 段増えるのが弱点で、これを表で済ませるのが Pratt 法（演算子順位法）です。
操車場アルゴリズムは、ダイクストラが考えた方法で、演算子をスタックで待たせ、後から来た演算子より先に計算すべきものを出力へ送ります。出力は逆ポーランド記法（後置記法）になり、スタックだけで計算できます。名前は、貨車を待避線（スタック）に入れて並べ替える鉄道の操車場にたとえたものです。