再帰下降型構文解析 ( LL(1) )

説明

再帰下降型構文解析は BNF で与えられた文法を解析する手法である．与えられた BNF を直接書き下すことでパーシングを行うことができる．ここでは LL(1) パーザの例として四則演算パーザを題材に，作成法を示す．

1. BNF を書く

再帰下降型のパーザを書くためには，まず BNF を書かなければならない．BNF でかける文法は二型文法(文脈自由文法)とよばれるクラスになる．これは実用上最も有用なクラスなので，多くの用途にはこれで足りる．

四則演算の BNF は次のようになる．どうせ自分でパーザを書くので BNF のきちんとしたルールに従っていなくても書ける気がすれば適当なルールを追加してよい．

equation := equation + factor | factor
factor   := factor   * term   | term
term     := (equation) | Number 

2. 左再帰の除去

再帰下降型構文解析を行うためには左再帰は除去しなければならない．しかしこれはたいした手間ではない．任意の左再帰は以下のようにして除去できる．

A := A B | C

iff

A  := C A'
A' := B A' | ε

これを上の四則演算のルールに適用すると次のようになる．

equation  := factor equation'
equation' := + equation' | ε
factor    := term factor'
factor'   := * factor'   | ε
term      := (equation) | Number 

ここで現れた equation', factor' は末尾再帰の形をしているので，ループに書き換えることができる．簡単のために閉包記号 * を導入すれば次のようになる．

equation := factor (+ factor)*
factor   := term (* term)*
term     := (equation) | Number 

これで除去できた．

3. LL(1) かどうかの判定

文法が k 文字の先読みで決定できるとき，それを LL(k) という．1 文字先読みで決定できる LL(1) は非常に実装しやすいので，そうかどうかを希望を持って判定する．そうでない場合は覚悟しなければならない．

四則演算の BNF をにらむと，分岐があるのは equation の閉包の個数，factor の閉包の個数，term の分岐であるが，最初の二つの閉包はそれぞれ *, + を目印にすればよいので 1 文字先読みで決定できる．最後の分岐は ( で始まるかどうかが目印になるのえやはり 1 文字先読みで決定できる．

4. 実装

あとはこれを実装するだけである．実装には幾つかやりかたがあるが，ここではもっとも硬い，副作用の無いものを選ぶ．

まず，解析結果を格納する型 result を定義する．これは解析結果と解析が終了しているインデックスの対である．

typedef pair<int, int> result;
#define value first
#define p second

次に上で定めた三つの関数を定義する．各関数は解析する文字列と解析を開始する位置を引数に取り，そこから解析した結果を返す．使いやすくするためにデフォルト引数として 0 を与えておく．

result equation(const string &s, int p = 0);
result factor(const string &s, int p = 0);
result term(const string &s, int p = 0);

あとは各関数を上の再帰的定義に従って書き下せばよい．全体のプログラムを以下に示す．

#include <iostream>
#include <string>

using namespace std;

typedef pair<int, int> result;
#define value first
#define p second

result equation(const string &s, int p = 0);
result factor(const string &s, int p = 0);
result term(const string &s, int p = 0);

result equation(const string &s, int p) {
  result r = factor(s, p);
  while (s[r.p] == '+') {
    result r_ = factor(s, r.p+1);
    r.value += r_.value;
    r.p      = r_.p;
  }
  return r;
}
result factor(const string &s, int p) {
  result r = term(s, p);
  while (s[r.p] == '*') {
    result r_ = term(s, r.p+1);
    r.value *= r_.value;
    r.p      = r_.p;
  }
  return r;
}
result term(const string &s, int p) {
  if (s[p] == '(') {
    result r = equation(s, p+1);
    r.p += 1; // skip ')'
    return r;
  } else {
    int value = 0;
    while (isdigit(s[p]))
      value = value * 10 + (s[p++] - '0');
    return result(value, p);
  }
}

int main() {
  result r = equation( "(1+2+3)*(4+5+6)" );
  cout << r.value << endl;
}