読者です 読者をやめる 読者になる 読者になる

JavaScriptでParsecっぽいものを作った

車輪の再発明してみた。Rhinoでしか動作確認してないけど多くのブラウザで動作するんじゃないかな。jsparsec.js
この辺参考にしてます→inforno :: Javascriptでパーサジェネレータを書いてみた
関数名は基本的にParsecのものと合わせています。Parsec.CombinatorとParsec.Charに含まれている関数のほとんどを移植しました。
以下四則演算パーサのサンプル。単項マイナスに対応してないのは書き終わってから気づきました。

var ExprParser = CharCombinator.define(
  function() {
    with(this) {
      this.nat = many1(digit) ['>>='] (function (n) {
        return ret(parseInt(n.join(''), 10)); });
      this.token = function(p) { return between(spaces, spaces, p); };
      this.natural = token(nat);
      this.symbol = function(c) { return token(chr(c)); };

      this.factor = between(
        symbol('('), symbol(')'), lazy(function() { return expr; })
      ) ['<|>'] (natural);
      this.term = chainl1(factor,
        or(symbol('*') ['>>'] (ret(function(x, y) { return x * y; })),
           symbol('/') ['>>'] (ret(function(x, y) { return x / y; }))));
      this.expr = chainl1(term,
        or(symbol('+') ['>>'] (ret(function(x, y) { return x + y; })),
           symbol('-') ['>>'] (ret(function(x, y) { return x - y; }))));
     }
  });

// 以下テスト
function debug(p, input) {
  var result = p.parse(input);
  if (result === null)
    print('(error)');
  else
    print('(' + uneval(result[0]) + ', "' + result[1] + '")');
}

debug(ExprParser.expr, "10 + 4*3 / 10");        // => (11.2, "")
debug(ExprParser.expr, "1 + (2) * 3 - 5 / 5");  // => (6, "")
debug(ExprParser.expr, "2 * (2 + 3)");          // => (10, "")
debug(ExprParser.expr, "1 - 2 - 3");            // => (-4, "")
debug(ExprParser.expr, "5 + 12*3 / 10 asda");   // => (8.6, "asda")
debug(ExprParser.expr, "(12*a3)");              // => (error)

['>>']とか['>>=']とか['<|>']とか使って見た目微妙にHaskellっぽく書けます。あと相互再帰を実現するためにlazyという関数を導入してみました。

式クロージャを使うと多少はスッキリしますがそれでもHaskellほど読みやすくはなりませんね。

var ExprParser = CharCombinator.define(
  function() {
    with(this) {
      this.nat = many1(digit) ['>>='] (function (n) ret(parseInt(n.join(''), 10)));
      this.token = function(p) between(spaces, spaces, p);
      this.natural = token(nat);
      this.symbol = function(c) token(chr(c));

      this.factor = between(symbol('('), symbol(')'), lazy(function() expr)) ['<|>'] (natural);
      this.term = chainl1(factor,
        or(symbol('*') ['>>'] (ret(function(x, y) x * y)),
           symbol('/') ['>>'] (ret(function(x, y) x / y))));
      this.expr = chainl1(term,
        or(symbol('+') ['>>'] (ret(function(x, y) x + y)),
           symbol('-') ['>>'] (ret(function(x, y) x - y))));
     }
  });

Haskellで同等のパーサを書いた例を参考までに。

module Main where

import Text.ParserCombinators.Parsec

nat = many1 digit >>= return . read
token p = between spaces spaces p
natural = Main.token nat
symbol c = Main.token $ char c

factor = between (symbol '(') (symbol ')') expr <|> natural
term = chainl1 factor $ (symbol '*' >> return (*)) <|> (symbol '/' >> return (/))
expr = chainl1 term   $ (symbol '+' >> return (+)) <|> (symbol '-' >> return (-))