JavaScriptでパーサコンビネータのコンセプトを理解する(「正規表現だけに頼ってはいけない」の続き)

前回の記事の続き。前回は、正規表現が使えない時はパーサコンビネータを使ってみると良いということを書いた。

パーサコンビネータのためのライブラリは、以下のように各言語ごとにいくつかある。

• JavaScript - Parsimmon
• Ruby - rparsec treetop
• Python - parsy
• PHP - PHPPEG

各言語でいくつかあるのだが、正規表現と違ってパーサコンビネータには統一的な書き方があるわけではないし、ライブラリによって使い方も様々である。なので、今まで正規表現だけ使ってきた開発者がちょっと使ってみようと思っても、使い方がよくわからずに面食らってしまうことがある。

パーサコンビネータはテキストをパースするための非常に強力な仕組みだが、その背後にある考え方を理解しなければこれらのパーサコンビネータのライブラリを使う際の障害になるだろう。逆に言うと、それさえ理解できればどのライブラリでもそれほど苦労せずに使えるようになるだろう。

実は、単純なものであればパーサコンビネータを書くことはそれほど難しくない。この記事では、学習のためにJavaScriptで単純なパーサコンビネータを実際に作りつつ、パーサコンビネータのコンセプトを解説する。

関数としてのパーサ

パーサコンビネータでは、パーサを関数として扱うことが多い。そして、その関数をいくつも加工したり合成したりしていくことで自分が欲しいパーサを構築する。

パーサコンビネータの実装として有名なのが、関数型言語のHaskellのparsecである。パーサコンビネータはHaskellのような関数型言語でよく親しまれている。というのも、パーサを関数として扱うやり方が、関数を値として扱ったり、関数を引数に取る高階関数を作ったり、関数の合成をしたりということをよく行う関数型言語では親しみやすいからだろう。

パーサコンビネータでは、パーサを関数として扱っていくが、その関数はどのような入力と出力を取るのだろうか? どのようなパーサコンビネータのライブラリでも基本的にはパーサは以下のよう入力と出力をベースにしている。

• 入力: パースする文字列、現在の読み取り位置
• 出力: パースが成功したかどうか、パースされた結果、新しい読み取り位置

パーサとしての関数では、当然パースの対象となる文字列をパラメータとして取る。それと、現在どの位置の文字を読み取っているのかという情報も受け取る。

出力では、パーサは文字列のパーサに成功か失敗かを返す。パーサが想定している文字列を受け取れなかったら失敗を返す。パースが成功した場合には、パーサは文字列を解釈(パース)して様々な値を生成するので、パースされた結果を返す。また、どこまでパースし終わったかを伝えるために新しい読み取り位置も同時に返す。

実際にJavaScript風の擬似コードで書くと以下のようになる。

/**
 * @param {String} target パーサの対象となる文字列
 * @param {Number} position 現在の読み取り位置
 * @return {Array} 成功したかどうか、パース結果、新しい読み取り位置の３つの要素を持った配列
 */
function parse(target, position) {
  // ...

  // パース成功したかどうか
  var success = ...; 

  // パース結果(パース失敗の場合はエラー情報など)
  var result = ...; 

  // 新しい読み取り位置
  var newPosition = ...; 
  
  return [success, result, newPosition];
}

パーサコンビネータでは、この関数として定義したパーサを使ってどのように実装されていくのか? 見ていこう。

単純な文字列をパースするパーサを書く

まず初めに、一番簡単なパーサを書くところから始めていく。ここでは 'hoge'という文字列をパースするパーサを書いてみる。

function parseHoge(target, position) {
  if (target.substr(position, 4) === 'hoge') {
    // 成功
    return [true, 'hoge', position + 4];
  } else {
    // 失敗
    return [false, null, position];
  }
}

ごくごく単純なコードだと思う。targetの現在の位置(position)から、4文字読み込んで、それが'hoge'ならパースが成功を返す。そうでなければ失敗を返す。

このパーサを実行してみると以下の様な動作をする。

parseHoge('hoge', 0) // => [true, 'hoge', 4]を返す

parseHoge('ahoge', 1) // => [true, 'hoge', 5]を返す

parseHoge('aaa', 0) // => [false, null, 0]を返す

さて、このパーサは'hoge'という文字列しかパースできないので、汎用的ではない。なのでこれを一部変えて、文字列を受け取って先ほどのようなパーサを返す以下の様なtoken関数を定義する。こうすると単純な文字列のパーサを生成する関数として汎用化できる。

/**
 * 単純な文字列のパーサを生成する
 * 
 * @param {String} str
 * @return {Function} strのパーサ
 */
function token(str) {
  var len = str.length;

  return function(target, position) {
    if (target.substr(position, len) === str) {
      return [true, str, position + len];
    } else {
      return [false, null, position];
    }
  };
}

これも試してみよう。

token('foobar')('foobar', 0); // => [true, 'foobar', 6]を返す

token('foobar')('foobar', 1); // => [false, null, 1]を返す

token関数のおかげで、単純な文字列のパーサを簡単に生成できるようになった。

とはいえ、これだけでは単純な文字列をパースできるだけで、パーサコンビネータとしての利用価値はまだ無い。ここからどんどんパーサコンビネータを拡張していこう。

繰り返しを表現するパーサを作る

正規表現で、繰り返しの表現がある。例えば、/(hoge)*/という正規表現は0個以上の'hoge'という文字列にマッチする。ここでは、この繰り返しの処理をパーサコンビネータで実装してみる。

/(hoge)*/という正規表現をそのままパーサとして書くと以下のparseHogeMany()関数になる。

function parseHogeMany(target, position) {
  var result = [];

  for (;;) { 
    if (target.substr(position, 4) === 'hoge') {
      result.push('hoge');
      position += 4;
    } else {
      break;
    }
  }

  return [true, result, position];
}

このパーサも'hoge'という文字列の繰り返ししかパースできないので、これを汎用的にする。

パーサコンビネータでは、パーサを入力に受け取って加工したパーサを返す関数がよくある。ここでは、パーサを受け取ってその繰り返しのパーサを生成する以下のmany関数を書いた。

/**
 * パーサを受け取って、そのパーサの解釈できる文字列を
 * 繰り返した文字列を解釈できるパーサを生成する
 * 
 * @param {Function} parser
 * @return {Function}
 */
function many(parser) {
  return function(target, position) {
    var result = [];

    for (;;) { 
      var parsed = parser(target, position);
      // 受け取ったパーサが成功したら
      if (parsed[0]) {
        result.push(parsed[1]); // 結果を格納して
        position = parsed[2];   // 読み取り位置を更新する
      } else {
        break;
      }
    }

    return [true, result, position];
  }
}

ここで、今まで作った関数(token, many)を試してみよう。なんとなく雰囲気出てきたんじゃなかろうか?

many(token('hoge'))('hogehoge', 0); // => [true, ['hoge', 'hoge'], 8] を返す

many(token('hoge'))('', 0); // => [true, [], 0] を返す

many(token('foobar'))('foo', 0); // => [true, [], 0] を返す

選択を表現するパーサを作る

さらにこのパーサコンビネータの表現力を増やしていこう。

正規表現ではパイプを使って選択を表現できる。例えば、/(foo|bar)/という正規表現は、'foo'もしくは'bar'という文字列にマッチする。

まずは単純に書き下すと以下のようになる。

function parseFooOrBar(target, position) {
  if (target.substr(position, 3) === 'foo') {
    return [true, 'bar', position + 3];
  }

  if (target.substr(position, 3) === 'bar') {
    return [true, 'bar', position + 3];
  }

  return [false, null, position];
}

これも汎用性が無いので、汎用性を持たせて書き直したchoice関数が以下になる。many関数と同様に、このchoice関数も入力としてパーサを受けとって新しい性質を持ったパーサを生成する。

/**
 * @param {Array} parsers... パーサの配列
 * @return {Function} 選択を表現するパーサ
 */
function choice(/* parsers... */) {
  var parsers = arguments;

  return function(target, position) {
    for (var i = 0; i < parsers.length; i++) {
      var parsed = parsers[i](target, position);
      // パース成功したら結果をそのまま帰す
      if (parsed[0]) {
        return parsed;
      }
    }

    return [false, null, position];
  };
}

さて、このchoice関数を作ったことで、正規表現でいう/(hoge|fuga)*/という表現をこのパーサコンビネータで表現できるようになった。

var parse = many(choice(token('hoge'), token('fuga')));

parse('', 0); // => [true, [], 0] を返す
parse('hogehoge', 0); // => [true, ['hoge', 'hoge'], 8] を返す
parse('fugahoge', 0); // => [true, ['fuga', 'hoge'], 8] を返す
parse('fugafoo', 0); // => [true, ['fuga'], 4] を返す

パーサを連結する

上ではchoiceやtokenやmanyなどの関数を作ったが、正規表現でいう/(foo|bar)baz/と同じことができるようにするためには、今度はパーサ同士を結合する関数が必要になってくる。

読んでるひとももうだんだん慣れてきたと思うので一気に以下のseq関数を書いてみた。この関数は複数のパーサを連結する。連結されたパーサが内部で持っているパーサが一つでも失敗すれば全体として失敗する。

/**
 * @param {Array} parsers... 結合するパーサの配列
 * @return {Function} パーサ
 */
function seq(/* parsers... */) {
  var parsers = arguments;
  return function(target, position) {
    var result = [];
    for (var i = 0; i < parsers.length; i++) {
      var parsed = parsers[i](target, position);

      if (parsed[0]) {
        result.push(parsed[1]);
        position = parsed[2];
      } else {
        // 一つでも失敗を返せば、このパーサ自体が失敗を返す
        return [false, null, position];
      }
      
    }
    return [true, result, position];
  };
}

このseq関数を使うことで、先ほどの正規表現/foo(bar|baz)/と同じこともできるようになった。

var parse = seq(token('foo'), choice(token('bar'), token('baz')));

parse('foobar', 0); // => [true, ['foo', 'bar'], 6] を返す

parse('foobaz', 0); // => [true, ['foo', 'baz'], 6] を返す

parse('foo', 0); // => [false, null, 0] を返す

オプションを表現するパーサを作る

失敗しても気にしないパーサというのも必要になってくる。例えば/(hoge)?/という正規表現では、hogeという文字がマッチしてもしなくてもパースしてくれる。これもパーサコンビネータで実装してみよう。

オプションを表現するパーサを生成してくれるoption関数が以下になる。

/**
 * @param {Function} parser
 * @return {Function}
 */
function option(parser) {
  return function(target, position) {
    var result = parser(target, position);
    if (result[0]) {
      return result;
    } else {
      return [true, null, position];
    }
  };
}

これも試してみるとこういうことになる。内部で渡したパーサを実行するのだが、このパーサが失敗を返したとしてもoption関数が生成したパーサは成功を返す。その代わりパース結果にはnullが入り、読み取り位置も更新されない。

var parser = option(token('hoge'));

parser('hoge', 0); // => [true, 'hoge', 4] を返す
parser('fuga', 0); // => [true, null, 0] を返す

正規表現も使えるようにする

パーサコンビネータは、正規表現と違って、そのプログラミング言語のコードで記述、拡張できることが多い。

正規表現を使っている場合、自分でコードを書いてその正規表現エンジンを拡張することは基本的にできない。正規表現エンジンはその言語ではなくCなどで書かれている場合が多いからだ。しかしそのプログラミング言語で記述しているパーサコンビネータであれば拡張は可能だ。

パーサコンビネータを拡張するのは非常に簡単だ。パーサの入出力のインターフェイスさえ守れば内部のロジックを自分で好きなように書けるからだ。

さらにこのパーサコンビネータを使いやすくするために、パーサコンビネータ内で正規表現が使えるようにしてみよう。ここでは、正規表現を使ってパーサを生成する以下のregex関数を書いた。

/**
 * @param {RegExp} regexp
 * @return {Function}
 */
function regex(regexp) {
  if (regexp.source.substring(0, 1) !== '^') {
    regexp = new RegExp(
      '^' + regexp.source,
      (regexp.global ? 'g' : '') +
      (regexp.ignoreCase ? 'i' : '') +
      (regexp.multiline ? 'm' : '')
    );
  }

  return function(target, position) {
    regexp.lastIndex = 0;
    var regexResult = regexp.exec(target.slice(position));

    if (regexResult) {
      position += regexResult[0].length;
      return [true, regexResult[0], position];
    } else {
      return [false, null, position];
    }
  };
}

ほんの20行程度書くことで、正規表現を利用できるパーサを書くことができた。

これも試してみよう。

var parser = regex(/hoge/);

parser('hoge', 0); // => [true, 'hoge', 4]を返す

parser = regex(/([1-9][0-9]*)/);

parser('2014', 0); // => [true, '2014', 4]を返す
parser('01', 0); // => [false, null, 0]を返す

再帰する文法を扱えるようにする

前回の記事では、正規表現ではできないことの一つに、再帰的な文法を扱うことができないということを書いた。パーサコンビネータでは、どうやって再帰的な文法を記述するのだろう?

パーサコンビネータのライブラリでは、パーサの実装を遅延評価するパーサを生成して再帰的な文法を記述することが多い。あるパーサの実装を遅延評価すると、パーサを再帰的に構築できる。

ちょっとこれはイメージしづらいと思うのでこれも実際にコードを書いてから解説する。

まず、パーサの実装を遅延評価するlazy関数を記述する。lazy関数は受け取った関数をパース時に初めて評価して、その結果返ってきたパーサを内部で利用する。

function lazy(callback) {
  var parse;
  return function(target, position) {
    if (!parse) {
      parse = callback();
    }    
    return parse(target, position);
  };
}

このlazy関数を使って、試しにごく簡単な再帰的な構造のパーサを作ってみよう。プログラム内のループは再帰呼び出しでも記述できることはよく知られているが、パーサコンビネータでもmanyと同じことは実はこのlazy関数を使って再帰的な構造のパーサを作ることでもできる。例えば、many(token('hoge'))は以下の様にも記述することができる。

var parse = option(seq(token('hoge'), lazy(function() {
  return parse;
})));

parse('hoge', 0); // => [true, ['hoge', null], 4]が返る
parse('hogehoge', 0); // => [true, ['hoge', ['hoge', null]], 8]が返る
parse('hogehogehoge', 0); // => [true, ['hoge', ['hoge', ['hoge', null]]], 12]が返る

パーサの結果を加工するパーサを書く

さて、ここまでパーサコンビネータを書いてきてだいぶ強力になってきたのでついでにパーサの結果を加工するパーサを生成するmap関数を書いてみることにする。

これは、実際に複雑なパーサを構築する時にあると便利である。例えば、プログラミング言語のパーサのようなものを構築する際に、パースの途中で必要の無いデータを削ったり、パースした結果を特定のオブジェクトに変換することができるようになるからである。

function map(parser, fn) {
  return function(target, position) {
    var result = parser(target, position);
    if (result[0]) {
      return [result[0], fn(result[1]), result[2]];
    } else {
      return result;
    }
  };
} 

実際にこれを試してみる。helloという文字列をパースできたら、その結果を加工する例が以下である。

var parse = map(token('hello'), function(result) {
  return result + 'という文字列をパースできたよ';
});

parse('hello', 0); // => [true, 'helloという文字列をパースできたよ', 5]が返る
parse('foobar', 0); // => [false, null, 0]が返る

特定の文字のみを受け入れるパーサを書く

正規表現では、[](ブラケット)で文字クラスを表現できる。例えば、/[abc]/という正規表現はabcという文字のいずれかにマッチする。

これと同じものをパーサコンビネータでも作ってみると以下のようになる。

function char(str) {
  var dict = {};
  for (var i = 0; i < str.length; i++) {
    dict[str[i]] = str[i];
  }

  return function(target, position) {
    var char = target.substr(position, 1);
    if (dict[char]) {
      return [true, char, position + 1];
    } else {
      return [false, null, position];
    }
  };
}

実際にこれを試してみる。

// abcdefといういずれかの文字だけを受け入れるパーサを生成する
var parse = char('abcdef');

parse('a', 0); // => [true, 'a', 1]が返る
parse('b', 0); // => [true, 'b', 1]が返る
parse('g', 0); // => [false, null, 0]が返る
parse('', 0); // => [false, null, 0]が返る

数式のパーサを構築する

さて、ここまで幾つかパーサを生成する関数を作ってきたが、そろそろ強力になってきたので実際に簡単な数式のパーサを書いてみよう。対象とする数式は、演算子は+と-だけで、利用できる数値は整数のみで、括弧を使うことはできるが、式の間にスペースを入れることもできない以下の様な数式だ。

1+1
2-10+5
10+(0-30)+4

まず整数のパーサを書くと以下のようになる。

var number = map(regex(/[0-9]|[1-9][0-9]*/), function(parsed) {
  // パースした文字列を整数に変換する
  return parseInt(parsed, 10);
});

number('0', 0); // => [true, 0, 1]が返る
number('10', 0); // => [true, 10, 2]が返る
number('a1', 0); // => [false, null, 0]が返る

パーサコンビネータの利点のひとつに、パーサを関数として扱えるので、個別の文法のテストが記述できる点がある。ここでは、数値だけをパースするnumber関数を定義しているが、これはただの関数なので、これをそのままユニットテストなどでテストできる。

次は演算子のパーサを書こう。演算子はここでは単に'+'か'-'にマッチすれば良いので簡単だ。

var operator = char('+-');

次は括弧のついた式のパーサを書こう。括弧の中に入る式のパーサ(以下のコードではexpressionという変数を使っている)はまだ定義していないので、lazy関数で囲って遅延評価することにする。

var parenthesis = lazy(function() {
  var parser = seq(token('('), expression, token(')'));
  return map(parser, function(parsed) {
    // 括弧の文字列はいらないので中の数式のパース結果だけを取り出す
    return parsed[1];
  });
});

次に、演算の対象となる数値や式のパーサを書く。この数式では、演算の対象となるのは整数か括弧つきの式かのどちらかであるので、choice()関数を使って以下のようになる。

var atom = choice(num, parenthesis);

次に演算子を使った計算の式を書こう。この数式では、利用できる演算子は全て二項演算子であるので、計算式を表す文字列は、計算の対象、演算子、計算の対象という風に並ぶことになる。従って以下のように記述できる。

var expression = map(seq(atom, many(seq(operator, atom))), function(parsed) {
  // パースの結果を整形する
  // 例えば1+2-3は[1, '+', 2, '-', 3]というような形にする
  return [parsed[0]].concat(parsed[1].reduce(function(result, item) {
    return result.concat(item);
  }, []));
});

最後に、実際にパーサとして試しやすいように以下のようなラッパを作る。パースが失敗した時や、文字列を最後までパースしきれない時にはメッセージを出すようにした。

var parse = function(target) {
  var result = expression(target, 0);

  if (!result[0]) {
    console.log('パース失敗');
  } else if (target.length !== result[2]) {
    console.log((1 + result[2]) + '文字目でパース失敗');
  }

  return result[1];
};

実際に使ってみよう。

var result = parse('1+2-(3+1-(4))');
console.log(JSON.stringify(result));

これを実行すると以下のように表示される。

[1,"+",2,"-",[3,"+",1,"-",[4]]]

文字列がきちんとパースされているようだ。他にも色々な文字を試してみよう。

parse('1+2-(3+1'); // => "4文字目でパース失敗"と表示される
parse('hoge'); // => "パース失敗"と表示される
parse('0-3+(((3)))'); // => [0, '-', 3, '+', [[[3]]]]が返る

数式ではない文字列や一部間違っている数式を与えた時にはきちんとパース失敗していることがわかる。

終わりに

この記事で作成したJavaScript製のパーサコンビネータは、fnparse.jsとしてgithubで公開している。短いコードながらも普通のパーサコンビネータとしても一応利用できるようになっている。

正規表現は便利だが、正規表現が本質的にパースできない文法にはパーサコンビネータを使うとよい。パーサコンビネータのライブラリの利用は、一見すると難しく見えるが、背後のコンセプトさえ理解できればそれほど難しいわけではない。この記事では、実際にJavaScriptで簡単なパーサコンビネータを作ることによって、その背後のコンセプトや仕組みを説明した。