檜山正幸のキマイラ飼育記

JavaScriptで言語処理系の勉強をしましょう：構文解析準備編

雑記／備忘 | 16:24 |

次の2つの記事の続き； JavaScriptで実装したごく簡単な仮想機械RAC0（Rudimentary Arithmetic Calculator Level-0）に対して、高級言語とその処理系を作りましょう、というシリーズです。

• JavaScriptで仮想機械の勉強をしましょう
• JavaScriptで言語処理系の勉強をしましょう：字句解析編

トークンスキャナーが出来たので、次はパーザーを作る番です。実際のパーザー（構文解析器）の例を示す前に、方針と方法について説明しておきます。

内容：

1. ソースコードとトークン列
2. パーザーと構文木
3. BNFによる文法記述
4. 再帰降下（下降）法

ソースコードとトークン列

高級言語のソースコード（今回の例では、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）です。詳しく仕様を書いても次の程度。

1. 定数リテラルは、符号なしの整数。03 のように先行する0があってもよい。
2. 負の数を表すリテラルがないので、(0-3) のように引き算で代用。
3. 演算記号は、+, -, *, /, % の5種類。いずれも二項中置演算子。
4. *, /, % は、+, - より優先される。
5. 丸括弧を使って、式のグループ（まとまり）を作ってよい。
6. 同じ優先順位の演算は左結合的。例えば、 5*3/2 は、(5*3)/2 のこと。

これを文法として記述するのですが、BNFを文法記述に用いるのが標準的です。今、BNFの説明はしませんが、昔々僕が書いた解説がまだ残っているようです。

• http://www.atmarkit.co.jp/fxml/ddd/ddd004/ddd004-bnf.html

算術式（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は、実質的に正規表現と同じで、順次結合（記号は空白または「,」）、オプション（「?」）、選択（「|」）、繰り返し（「*」、「+」）の組み合わせで文法を書きます。これらは、プログラムの制御構造と次のように対応します。

if, switch, while, do-while の分岐条件としては、先読みしたトークンを調べた結果を使います。

少し練習すれば、BNFを見て対応するコードを書けるようになります。BNF → JavaScriptコードの実際の翻訳は次回にしましょう。