次の2つの記事の続き； JavaScriptで実装したごく簡単な仮想機械RAC0（Rudimentary Arithmetic Calculator Level-0）に対して、高級言語とその処理系を作りましょう、というシリーズです。
トークンスキャナーが出来たので、次はパーザーを作る番です。実際のパーザー（構文解析器）の例を示す前に、方針と方法について説明しておきます。
内容：
ソースコードとトークン列
高級言語のソースコード（今回の例では、1 + 2, (5 - 2)*4 のような算術式です）は、なんらかのテキストストリームから言語処理系に入力されます。ファイル、キーボード、文字列データなどが入力源となるテキストストリームですね。
入力テキストストリームは、トークンスキャナーによりトークンの列に変換されます。トークンとは、それ以上は分解できない構文的な“かたまり”のことです。今回扱う算術式では、加減乗除の演算記号と丸括弧と整数リテラルがトークンです。演算記号と丸括弧は、区切り記号（デリミタ）と呼ばれる記号で、1文字で1トークンとなります。整数リテラルは連続した何文字かでトークとなります。空白類も区切り記号*1ですが、区切る以外の意味を持たないので捨てられます。
パーザーと構文木
ソースコードがトークンに区切られて、それがパーザーの入力になるのです。トークン列を読み込み、文法規則に従ってデータ構造を組み立てるのがパーザーの役割です。パーザーの成果物であるデータ構造は、構文木、構文解析木、抽象構文木（AST; abstract syntax tree)などと呼ばれます。
JavaScriptなら、入れ子になったオブジェクトや配列を使って構文木を容易に表現できます。今回は算術式を表現すればいいので、例えば [引数1, 引数2, 演算子] という配列を入れ子にした形でもいいでしょう。演算子（+, -, *, /, %）を後に配置したのは、RAC0仮想機械がスタックマシンなので、逆ポーランド記法のほうがコード生成が楽だからです。
BNFによる文法記述
「文法規則に従ってデータ構造を組み立てるのがパーザーの役割」と書きました。算術式の構文仕様を復習しておきます。
「JavaScriptで言語処理系の勉強をしましょう：字句解析編」より：
高級言語といっても、1 + 2, (5 - 2)*4 のような算術式（arithmetic expression）です。詳しく仕様を書いても次の程度。
これを文法として記述するのですが、BNFを文法記述に用いるのが標準的です。今、BNFの説明はしませんが、昔々僕が書いた解説がまだ残っているようです。
算術式（expression）は、項（term）と因子（factor）から組み立てられるとして、BNFにより記述してみると次のようになります。
expr ::= term (('+'|'-') term)*term ::= factor (('*'|'/'|'%') factor)*
factor ::= NUMBER | '(' expr ')'
トークンの定義も含めてもう少し詳しく書けば次のよう。
// トークンの定義 （記号「:=」を用いる）
PLUS := '+'
MINUS := '-'
STAR := '*'
SLASH := '/'
PERC := '%'
LPAR := '('
RPAR := ')'
NUMBER:= [0-9]+// 算術式の文法
expr ::= term ((PLUS|MINUS) term)*
term ::= factor ((STAR|SLASH|PERC) factor)*
factor ::= NUMBER | LPAR expr RPER
再帰降下（下降）法
BNFで記述された文法を見ながら手書きでパーザーを書くなら、再帰降下法（再帰下降法；recursive descent parsing）が便利です。
BNFは、実質的に正規表現と同じで、順次結合（記号は空白または「,」）、オプション（「?」）、選択（「|」）、繰り返し（「*」、「+」）の組み合わせで文法を書きます。これらは、プログラムの制御構造と次のように対応します。
| BNF (正規表現) | プログラム |
|---|---|
| 順次結合: a b | 順次実行: A; B |
| オプション: a? | if文: if(p) A |
| 選択: a | b | switch文: switch(x){case a:A; case b:B} |
| 繰り返し: a* | while文: while(p) A |
| 繰り返し: a+ | do-while文: do A while(p) |
if, switch, while, do-while の分岐条件としては、先読みしたトークンを調べた結果を使います。
少し練習すれば、BNFを見て対応するコードを書けるようになります。BNF → JavaScriptコードの実際の翻訳は次回にしましょう。
*1:空白を区切り記号とは呼びたくない人もいるでしょうが。
