プッシュダウンオートマトンでS式の作成

先日教えてもらったアルゴリズムで字句の列からS式を構築するパーザを作ってみた。ここに恥を晒しておく。

// 字句の列からS式を作る
public SExp Parse(IEnumerable<LexerToken> tokens)
{
  IEnumerator<LexerToken> itor = tokens.GetEnumerator();
  SExp exp = null;
  if (itor.MoveNext())
  {
    LexerToken token = itor.Current;
    exp =
      itor.Current is TokenLeftParen ?
      CreateList(tokens) :
      CreateAtom(token);
  }
  else
  {
    const string MSG = "Empty S-Expression.";
    throw new ParserException(MSG);
  }
  return exp;
}

// 字句からアトムを作る
SExp CreateAtom(LexerToken token)
{
  SExp atom = null;
  if (token is TokenLeftParen)
  {
    atom = new __LeftParen();
  }
  else if (token is TokenInteger)
  {
    int n = 0;
    // 成功するはず
    int.TryParse(token.Value, out n);
    atom = new Integer(n);
  }
  else if (token is TokenString)
  {
    atom = new String(token.Value);
  }
  else if (token is TokenIdentifier)
  {
    atom = new Identifier(token.Value);
  }
  else
  {
    string msg =
      string.Format("failed to create atom from token '{0}'.", token.Value);
    throw new ParserException(msg);
  }
  return atom;
}

// コンスリストを作る
public SExp CreateList(IEnumerable<LexerToken> tokens)
{
  IEnumerator<LexerToken> itor = tokens.GetEnumerator();

  if (!itor.MoveNext())
  {
    const string MSG = "Empty S-Expression.";
    throw new ParserException(MSG);
  }
  if (Lexer.IsAtomToken(itor.Current))
  {
    string msg =
      string.Format("Unexpected token '{0}' was detected.", itor.Current.Value);
    throw new ParserException(msg);
  }

  itor = tokens.GetEnumerator();
  Stack<SExp> stkExp = new Stack<SExp>();
  SExp list = new Nil();
  bool consing = false;

  while (true)
  {
    if (consing)
    {
      SExp exp = null;
      try { exp = stkExp.Pop(); }
      catch
      {
        const string MSG = "Unexpected EOF detected.";
        throw new ParserException(MSG);
      }

      if (exp is __LeftParen)
      {
        stkExp.Push(list);
        list = new Nil();
        consing = false;
      }
      else
      {
        list = new Cell(exp, list);
      }
    }
    else
    {
      if(!itor.MoveNext()) break;
      else if (itor.Current is TokenRightParen)
      {
        consing = true;
      }
      else
      {
        SExp exp = CreateAtom(itor.Current);
        stkExp.Push(exp);
      }
    }
  }
  SExp ret = stkExp.Pop();
  return ret;
}

正しいS式かどうかとかのチェックは不十分。あと、トップレベルがアトムかリストかで分けてるけど、分ける必要ないのかもしれない。
アトムとして使えるデータ型は

• 文字列（字句の型はTokenString, S式の型はString）
• 正の整数（字句の型はTokenInteger、S式の型はInteger）
• シンボル（字句の型はTokenIdentifier、S式の型はIdentifier）

のみ（オートマトン - チキン煮込みチーズミックス4辛参照）。字句の型は全てLexerTokenを継承してて、S式の型も全てSExpを継承している。
CreateListでスタックを利用するために、__LeftParenというSExpを継承した型を使っているけど、これはS式を表すものではなく、スタックにS式と字句を混在させなければならないという状況*1に対する、苦し紛れの解決策。evalの段階では、リスト内に__LeftParenオブジェクトが含まれることはない。もしこうしなければ、Stack