kmizuの日記

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

C#で作るPEGパーザコンビネータ

id:tad0さんのコメント:

C#版きぼんぬ

http://d.hatena.ne.jp/kmizushima/20090226/1235619468#c1235739906

ということで、C#版も書いてみました。C#については時々調べたりするものの、ほとんど全くと言っていいほど使っていないので(たとえば、今回、C# 3.0のラムダ式を初めて使った)、なんか変な点があればご指摘ください。

using System;
using System.Collections.Generic;
public class Pair<A, B> {
  public A _1 { get; private set; }
  public B _2 { get; private set; }
  public Pair(A _1, B _2) {
    this._1 = _1;
    this._2 = _2;
  }
  public override string ToString() { 
    return string.Format("({0}, {1})", _1, _2);
  }
}
public class ParseResult<A> {
  public A Item { get; private set; }
  public string Rest { get; private set; }
  public ParseResult(A item, string rest) {
    Item = item;
    Rest = rest;
  }
  public override string ToString() { 
    return string.Format("(value = {0}, rest = {1})", Item, Rest);
  }
}
public class Parser<A> {
  public Func<string, ParseResult<A>> Target { get; set; }
  public Parser(Func<string, ParseResult<A>> target) {
    Target = target;
  }
  public ParseResult<A> Parse(string input) {
    return Target(input);
  }
  public static Parser<A> Make(Func<string, ParseResult<A>> target) {
    return new Parser<A>(target);
  }
  public static implicit operator Parser<object>(Parser<A> p) {
    return Parser<object>.Make((input) => {
      var r = p.Parse(input);
      return r != null ? new ParseResult<object>(r.Item, r.Rest) : null;
    });
  }
  public Parser<A> Or(Parser<A> p2) {
    return Make((input) => {
      var r = Parse(input);
      return r != null ? r : p2.Parse(input);
    });
  }
  public Parser<Pair<A, B>> Seq<B>(Parser<B> p2) {
    return Parser<Pair<A, B>>.Make((input) => {
      var r1 = Parse(input);
      if(r1 == null) return null;
      var r2 = p2.Parse(r1.Rest);
      if(r2 == null) return null;
      return new ParseResult<Pair<A, B>>(
        new Pair<A, B>(r1.Item, r2.Item), r2.Rest
      );
    });
  }
  public static Parser<object> operator!(Parser<A> p) {
    return p.Not();
  }
  public static Parser<Object> operator~(Parser<A> p) {
    return p.And();
  }
  public Parser<object> Not() {
    return Parser<object>.Make((input) => {
      var r = Parse(input);
      return r == null ? new ParseResult<object>(null, input) : null;
    });
  }
  public Parser<object> And() {
    return this.Not().Not();
  }
  public Parser<A> Opt() {
    return Or(BasicOperations.Str("").Apply<A>((p) => default(A)));
  }
  public Parser<B> Apply<B>(Func<A, B> f) {
    return Parser<B>.Make((input) => {
      var r1 = Parse(input);
      return r1 != null ? new ParseResult<B>(f(r1.Item), r1.Rest) : null;
    });
  }
  public Parser<List<A>> Rep() {
    return Parser<List<A>>.Make((input) => {
      var rs = new List<A>();
      ParseResult<A> r;
      while((r = Parse(input)) != null) {
        rs.Add(r.Item);
        input = r.Rest;
      }
      return new ParseResult<List<A>>(rs, input);
    });
  }
  public Parser<List<A>> Rep1() {
    return this.Seq(this.Rep()).Apply((p) => {
      p._2.Add(p._1);
      return p._2;
    });
  }
}
public class BasicOperations {
  public static Parser<string> Any = Parser<string>.Make((input) => {
    return input.Length > 0 ?
    new ParseResult<string>(input.Substring(0, 1), input.Substring(1)) : null;
  });
  public static Parser<string> Str(string param) {
    return Parser<string>.Make((input) => {
      return input.StartsWith(param) ?
      new ParseResult<string>(param, input.Substring(param.Length)) : null;
    });
  }
  public static Parser<A> Rule<A>(Func<Parser<A>> f) {
    return Parser<A>.Make((input) => f().Parse(input));
  }
}

使い方は以下のような感じ。C#でstaticなメンバをimport(C#だとusing?)する方法がわからない(クラスのメンバをusingしようとしてできなかった)ので、仕方なくクラスを継承してますが、たぶんもっとマシな方法があると思うので、知っている方がおられたら教えていただければと思います。

public class User : BasicOperations {
  public static Parser<object> S = Rule(() => 
    (~A.Seq(!Str("b"))).Seq(Str("a").Rep1()).Seq(B).Seq(!Str("c"))
  );
  public static Parser<object> A = Rule(() =>
    Str("a").Seq(A.Opt()).Seq(Str("b"))
  );
  public static Parser<object> B = Rule(() =>
    Str("b").Seq(B.Opt()).Seq(Str("c"))
  );
  static void Main(string[] args) {
    Console.WriteLine("{0}", S.Parse(args[0]));
  }
}