再帰下降構文解析で電卓プログラムを実装する

パーサ入門として式解析の一つである再帰下降構文解析をTypescriptで実装してみたのでまとめました。

構文解析の基礎

構文解析入門にあたって基本的な語句を整理します。

構文の規則を図式化したもの。構文の構成要素とその関係性を図式で表します。例えばある言語のルールとして「英字で始まりで英字と数字で構成されるもの」が識別子とされている場合、その識別子は下記のような構文図で表されます。下記の例だとab0, b01aなどが該当します。

f:id:sue71:20180201023554p:plain

構文図を文字列で表現したもの。例えば前述の例を表す場合

<識別子> ::= <英字> (<数字> | <英字>)
<英字> ::= a | b | c| ... | z 
<数字> ::= 0 | 1 | 2 | ... | 9

のようになります。<>で囲まれているものは非終端記号、それ以外を終端記号といいます。

構文解析する前に、文字列を構文規則に従って意味を持つ集合(トークン)に分割する必要があります。トークンは例えば以下のようなものが該当します。

ここで取得されたトークンを元に構文解析を行います。構文解析の手法は色々ありますが今回はよく使用されている再帰下降構文解析を実装します。

BNFに出現した非終端記号に対応する関数を用意し、末端から値を決定していく方法です。

四則演算を実装する場合、演算子の優先度を考慮する必要がありますが再帰下降構文を用いた場合は構文規則そのものに演算子優先度が含まれます。式をexpression, 項をterm, 因子をfactorとした場合、四則演算の構文規則は

<expression> ::= <term> [ ('+'|'-') <term> ]*
<term>   ::= <factor> [ ('*'|'/') <factor> ]*
<factor> ::= <number> | '(' <expression> ')'

のようになります。expressionを根としたツリー構造を考えるとexpressionから下向きに処理が実行されてていき、factorは必要に応じてexpressionを呼び出すので再帰的な性質も持っています。

下記仕様で簡易電卓プログラムを実装しました。

といった流れで実装しています。

今回は代入される値が数値であることが決まっているのでシンプルに配列を定義していますが実際は型情報などを保持する必要があります。これを記号表と呼ぶのですがこちらに関しては別記事で紹介します。

a = 10 + 5
b = a + 10
? b
25