embryo

エンジニアの備忘録

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

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

構文解析の基礎

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

構文図

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

f:id:sue71:20180201023554p:plain

BNF記法

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

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

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

  • 非終端記号: 他の文字列で代替されるもの
  • 終端記号: 他の文字列で代替されないもの

字句解析

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

  • if
  • else
  • (
  • )

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

再帰下降構文解析

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

再帰下降構文で四則演算

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

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

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

Node.jsによる実装

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

  • 変数には[a-z]が使用可能
  • 四則演算が使用可能
  • ?はPrint文として扱う

gist.github.com

  1. 入力を受け付け
  2. statement関数で1文(1行)ずつ処理
  3. expression, term, factorで式を解析、stackに値を詰める
  4. Print文が呼び出された場合はstackから値を取り出して出力する

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

識別子の扱いについて

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

実行結果

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

参考