平々毎々（アーカイブ）

はてなダイアリーのアーカイブです。

関数型言語ってこわい？C#erがLINQでパーサーに挑戦(1)

C# Functional

註：この記事は、「ごはんはおかずLINQはモナド」と聞いたことがあるけど、モナドって何なのかは特に知りたくない、でもLINQがモナドだと何ができるのかはちょっとだけ知りたい、という奇特な人向けに、「簡単なパーサーを実装する」というお題でコードを見てみようという、まったくPVの伸びなさそうな記事です。
なので、以下のテーマは対象外。

実装したいのは、ゼロ以上の整数、加算記号(+)、乗算記号(*)、開かっこ、閉かっこから構成される数式を文字列で与えられたときに、パースして結果を計算し、intを返すメソッド。その上、乗算は加算より優先度が高いとする。(プログラミングHaskellの第8章を基にしています)

引数と戻り値の例は以下のような感じ。

"10+2*3"   → 16
"10*2+3"   → 23
"(10+2)*3" → 36
"5*)"      → パース失敗

BNFっぽく書けば、こんな感じ。

expr   (* 式 *)   ::= term '+' expr | term
term   (* 項 *)   ::= factor '*' term | factor
factor (* 因子 *) ::= '(' expr ')' | number
number (* 数 *)   ::= digit number | digit
digit  (* 数字 *) ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

パーサの設計と実装に行く前に、関数型言語の道具を1つだけC#に導入しておきます。それはF#のリスト。今回のネタ元が関数型言語の本なこともあって、データを再帰的に扱うための道具が欲しいのです。

F#のリストだからクラス名はFList<T>としておきます。

  public sealed class FList<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 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();
    }
  }

って、ToStringの中でforeachしてるからコンパイル通らないですね。せっかくだから、IEnumerable<T>と相互変換できるようにしておきましょうか。こんな風に。

  public sealed class FList<T> : IEnumerable<T>
  {
    // 他のメンバーは上に書いた通りなので省略

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

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

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