kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Hello, Dart (2) - パーザコンビネータ

いつだったか、新しい言語を学ぶときのHello, Worldはパーザコンビネータを書くことにしてる、といった事を言った覚えがあります。実際、これまで学んできたたいていの言語でミニパーザコンビネータライブラリを書いてきました。というわけで、Dartでもパーザコンビネータライブラリを書いてみました。

もう何度も何度も書いてきたコードのため、考えるのは、その言語での標準的なデータ構造と関数に落とし込む方法だけです。というわけで、次のような感じになりました。クラスの定義方法とかコンストラクタの扱い、無名関数の文法、文字列の取り扱い、など基本的なことを一度に学べるので、パーザコンビネータという題材はやはり良いなと思います（自画自賛）。

感想：

  • 色々な面でかなりJavaプログラマフレンドリ。
    • 適当にJavaっぽい文法で書くとそれなりにパーズしてくれる可能性が高い。
  • 関数/メソッドの本体が式であるときに使える、 => 記法は便利。というか、これがないと不便。
  • 多相オペレータを定義できないのはちょっと不便。
    • Parser<Pair<T, U>> operator &<U>(Parser<U> that) みたいなのを書きたいが、これはDartでは許されないようだ。
  • Javaと違って、プリミティブ型を意識せずに済むのは楽。
  • コンストラクタの略記法が中途半端。フィールドへの代入コードを手動で書くよりは楽だが…
  • 関数の型の文法が、Cっぽい微妙さ。 Ret funArg(Arg1 arg1, ...) のように書くのだが、これだと関数を返す関数の型が綺麗に書けない…
    • typedef すればいいのだけど。
  • Javaでメソッドの型パラメタの宣言の位置がヘンテコだった問題は解決されている。

全体的に、Dartは、今の時代の言語としては平凡な感じがぬぐえませんが、その分、変な癖がないとも言えそうです。また、JavaプログラマがDartを学ぶのはかなり簡単であるという 感想を持ちました。

abstract class ParseResult<T> {
  String next;
  ParseResult(this.next) {}

  T get value;
  bool get successful;
}

class Pair<T1, T2> {
  T1 item1;
  T2 item2;
  Pair(this.item1, this.item2);

  String toString() {
    return '(${item1}, ${item2})';
  }
}

class ParseSuccess<T> extends ParseResult<T> {
  T value;
  ParseSuccess(this.value, String next) : super(next);
  @override bool get successful => true;
  @override String toString() => 'ParseSuccess(${value}, ${next})';
}

class ParseFailure<T> extends ParseResult<T> {
  T value = null;
  ParseFailure(String next) : super(next);
  @override bool get successful => false;
  @override String toString() => 'ParseFailure(${next})';
}

typedef ParseResult<T> ParserFunction<T>(String input);

typedef U BiFunction<T1, T2, U>(T1 t1, T2 t2);

class Parser<T> {
  ParserFunction<T> fun;
  Parser(this.fun);
  ParseResult<T> call(String input) => fun(input);

  Parser<T> operator |(Parser<T> that) => parserOf(
    (input) {
      var r1 = this.fun(input);
      if(r1.successful) {
        return r1;
      } else {
        return that.fun(input);
      }
    }
  );

  Parser<Pair<T, U>> then<U>(Parser<U> that) => parserOf(
    (input) {
      var r1 = this.fun(input);
      if(r1.successful) {
        var r2 = that.fun(r1.next);
        return r2.successful ? 
          new ParseSuccess<Pair<T, U>>(new Pair<T, U>(r1.value, r2.value), r2.next) :
          new ParseFailure<Pair<T, U>>(r1.next);
      } else {
        return new ParseFailure<Pair<T, U>>(input);
      }
    }
  );

  Parser<U> map<U>(U f(T result)) => parserOf(
    (input) {
      var r = this.fun(input);
      if(r.successful) {
        return new ParseSuccess<U>(f(r.value), r.next);
      } else {
        return new ParseFailure<U>(r.next);
      }
    }
  );

  Parser<T> chain(Parser<BiFunction<T, T, T> > q) =>
    this.then(q.then(this).many()).map((t) {
      var init = t.item1;
      var list = t.item2;
      return list.fold(init, (a, fb) {
        var f = fb.item1;
        var b = fb.item2;
        return f(a, b);
      });
    });

  Parser<List<T>> many() => parserOf(
    (input) {
      var rest = input;
      List<T> values = [];
      while(true) {
        var r = this.fun(rest);
        if(!r.successful) return new ParseSuccess(values, rest);
        values.add(r.value);
        rest = r.next;
      }
    }
  );

  Parser<List<T>> many1() => this.then(this.many()).map((t) {
    List<T> result = [];
    result.add(t.item1);
    result.addAll(t.item2);
    return result;
  });
}

Parser<String> range(String from, String to) => parserOf((input) {
  var f = from.codeUnitAt(0);
  var t = to.codeUnitAt(0);
  if(input.length < 1) {
    return new ParseFailure<String>(input);
  } else {
    var c = input.codeUnitAt(0);
    if(f <= c && c <= t) {
      return new ParseSuccess<String>(input[0], input.substring(1));
    } else {
      return new ParseFailure<String>(input);
    }
  }
});

Parser<T> rule<T>(Parser<T> body()) => parserOf((input) =>
  body()(input)
);

Parser<T> parserOf<T>(ParserFunction<T> fun) => new Parser<T>(fun);

Parser<String> s(String literal) => parserOf((input) =>
  input.startsWith(literal) ? 
    new ParseSuccess<String>(literal, input.substring(literal.length)) : 
    new ParseFailure<String>(input)
);

使う側はこんな感じです。

import 'dart:core';
import 'parser_combinator.dart';

Parser<int> expression() => rule(
  () => additive()
);

Parser<int> additive() => rule(
  () {
    Parser<BiFunction<int, int, int>> Q = s('+').map((op) => (int lhs, int rhs) => lhs + rhs);
    Parser<BiFunction<int, int, int>> R = s('-').map((op) => (int lhs, int rhs) => lhs - rhs);
    return multitive().chain(Q | R);
  }
);


Parser<int> multitive() => rule(
  () {
    Parser<BiFunction<int, int, int>> Q = s('*').map((op) => (int lhs, int rhs) => lhs * rhs);
    Parser<BiFunction<int, int, int>> R = s('/').map((op) => (int lhs, int rhs) => lhs ~/ rhs);
    return primary().chain(Q | R);
  }
);

Parser<int> primary() => rule(
  () => number() | (s('(').then(expression()).then(s(')'))).map((t) => t.item1.item2)
);

Parser<int> number() => rule(
  () => range('0', '9').many1().map((digits) => int.parse(digits.join()))
);

void main() {
  var e = expression();
  print(e('1+2*(3/4)'));
  print(e('(1+2)*3/4'));
  print(e('10+20*30'));
}

$ dart parser_usage.dart
ParseSuccess(1, )
ParseSuccess(2, )
ParseSuccess(610, )