Parser Combinator in Dart

parser_combinator.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)
);

parser_usage.dart

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'));
}