LINQでParserモナド

はてなダイアリーで解説中。

Program.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

public sealed class FList<T> : IEnumerable<T>
{
  private readonly bool isEmpty;
  private readonly T head;
  private readonly FList<T> tail;

  private FList(bool isEmpty, T head, FList<T> tail)
  {
    this.isEmpty = isEmpty;
    this.head = head;
    this.tail = tail;
  }

  public static readonly FList<T> Empty = new FList<T>(true, default(T), null);

  public FList(T head)
    : this(false, head, Empty)
  {
    if (head == null) throw new ArgumentNullException("head");
  }

  public FList(T head, FList<T> tail)
    : this(false, head, tail)
  {
    if (head == null) throw new ArgumentNullException("head");
    if (tail == null) throw new ArgumentNullException("tail");
  }

  public bool IsEmpty
  {
    get { return this.isEmpty; }
  }

  public T Head
  {
    get
    {
      if (this.isEmpty) throw new InvalidOperationException();
      return this.head;
    }
  }
  public FList<T> Tail
  {
    get
    {
      if (this.isEmpty) throw new InvalidOperationException();
      return this.tail;
    }
  }

  public IEnumerator<T> GetEnumerator()
  {
    return new Enumerator(this);
  }

  IEnumerator IEnumerable.GetEnumerator()
  {
    return this.GetEnumerator();
  }

  public override string ToString()
  {
    StringBuilder sb = new StringBuilder();
    bool empty = true;
    sb.Append("[");
    foreach (T item in this)
    {
      if (empty)
        empty = false;
      else
        sb.Append(", ");
      sb.Append(item);
    }
    sb.Append("]");
    return sb.ToString();
  }

  private class Enumerator : IEnumerator<T>
  {
    private FList<T> list;

    public Enumerator(FList<T> list)
    {
      this.list = new FList<T>(default(T), list);
    }

    public T Current
    {
      get { return this.list.Head; }
    }

    object IEnumerator.Current
    {
      get { return this.Current; }
    }

    public bool MoveNext()
    {
      if (!this.list.isEmpty) this.list = this.list.tail;
      return !this.list.isEmpty;
    }

    public void Reset()
    {
      throw new NotSupportedException();
    }

    public void Dispose()
    {
      this.list = null;
    }
  }
}

public static class FList
{
  public static FList<T> ToFList<T>(this IEnumerable<T> source)
  {
    using (var itor = source.GetEnumerator())
      return itor.ToFList();
  }

  public static FList<T> ToFList<T>(this IEnumerator<T> source)
  {
    return (source.MoveNext())
      ? new FList<T>(source.Current, source.ToFList())
      : FList<T>.Empty;
  }
}

public class Parser<T>
{
  private readonly Func<FList<char>, Tuple<T, FList<char>>> f;

  public Parser(Func<FList<char>, Tuple<T, FList<char>>> f)
  {
    this.f = f;
  }

  public Tuple<T, FList<char>> Parse(FList<char> input)
  {
    return this.f(input);
  }

  public Tuple<T, FList<char>> Parse(string input)
  {
    return this.f(input.ToFList());
  }

  public Parser<T> Where(Func<T, bool> predicate)
  {
    return new Parser<T>(input =>
    {
      var r = this.Parse(input);
      if (r == null) return null;
      if (!predicate(r.Item1)) return null;
      return r;
    });
  }

  public Parser<TResult> Select<TResult>(Func<T, TResult> f)
  {
    return new Parser<TResult>(input =>
    {
      var r = this.Parse(input);
      if (r == null) return null;
      return Tuple.Create(f(r.Item1), r.Item2);
    });
  }

  public Parser<TResult> SelectMany<T1, TResult>(Func<T, Parser<T1>> k, Func<T, T1, TResult> s)
  {
    return new Parser<TResult>(input =>
    {
      var r1 = this.Parse(input);
      if (r1 == null) return null;
      var r2 = k(r1.Item1).Parse(r1.Item2);
      if (r2 == null) return null;
      return Tuple.Create(s(r1.Item1, r2.Item1), r2.Item2);
    });
  }

  public static Parser<T> operator |(Parser<T> x, Parser<T> y)
  {
    return new Parser<T>(input =>
    {
      var r = x.Parse(input);
      return (r == null) ? y.Parse(input) : r;
    });
  }
}

public static class Parser
{
  public static Parser<char> Item()
  {
    return new Parser<char>(x => (x.IsEmpty) ? null : Tuple.Create(x.Head, x.Tail));
  }

  public static Parser<char> Digit()
  {
    return from x in Item()
           where '0' <= x && x <= '9'
           select x;
  }

  public static Parser<char> Char(char c)
  {
    return from x in Item()
           where x == c
           select x;
  }

  public static Parser<FList<char>> Number()
  {
    return (from x in Digit()
            from xs in Number()
            select new FList<char>(x, xs))
            |
           (from x in Digit()
            select new FList<char>(x));
  }

  public static Parser<int> Expr()
  {
    return (from t in Term()
            from _ in Char('+')
            from e in Expr()
            select t + e)
            | Term();
  }

  public static Parser<int> Term()
  {
    return (from f in Factor()
            from _ in Char('*')
            from t in Term()
            select f * t)
            | Factor();
  }

  public static Parser<int> Factor()
  {
    return (from _1 in Char('(')
            from e in Expr()
            from _2 in Char(')')
            select e)
            |
           (from ns in Number()
            select int.Parse(new string(ns.ToArray())));
  }
}