// Parser combinators in Generic C# 
// This program requires .Net version 2.0
// Peter Sestoft (sestoft@itu.dk) * 2001-11-13, 2001-11-19

// Compile GCollections.cs with 
//   csc /t:module GCollections.cs
// Then compile this file with 
//   csc /addmodule:GCollections.netmodule Parsers.cs

// No backtracking in alternatives (Alt) so far.  

// A parser is a function that reads from a source (a stream).  It
// either succeeds in parsing a prefix of the stream and then returns
// a result together with the rest of the stream, or fails.

// A parser returning a result of type T is an object of type
// Parser<T>, which has a function Parse(ISource) that returns a
// Result<T>.  A result is either Succ(result, rest of source) or Fail.

using System;
using System.Text;		// For StringBuilder
using GCollections;		// For LinkedList<T>

// Parser results --------------------------------------------------

interface Result<T> { 
  bool Success { get; }
  T Value { get; }
  ISource Source { get; }
}

class Succ<T> : Result<T> {
  T t;
  ISource src;

  public Succ(T t, ISource src) { 
    this.t = t; this.src = src;
  }

  public bool Success { 
    get { return true; }
  }

  public T Value { 
    get { return t; }
  }

  public ISource Source { 
    get { return src; }
  }
}

class Fail<T> : Result<T> {
 public bool Success { 
    get { return false; }
  }

  public T Value { 
    get { throw new InvalidOperationException(); }
  }

  public ISource Source { 
    get { throw new InvalidOperationException(); }
  }
}

// Results: pairs  -------------------------------------------------

class Pair<T,U> {
  T t;
  U u;
  
  public Pair(T t, U u) { 
    this.t = t; this.u = u;
  }

  public T Fst { 
    get { return t; } 
  }

  public U Snd { 
    get { return u; } 
  }
}

// Results: option type --------------------------------------------

class Option<T> {
  T val;
  bool ok;

  public Option() { 
    this.ok = false; 
  }

  public Option(T val) { 
    this.ok = true; this.val = val;
  }

  public bool Ok { 
    get { return ok; }
  }
  
  public T Value { 
    get { 
      if (ok)
	return val; 
      else 
	throw new InvalidOperationException();
    }
  }
}

// Sources: functional streams -------------------------------------

interface ISource {		
  ISource MoveNext();		// returns null if at end
  char Current { get; }
}

struct StringSource : ISource {
  // invariant: i < s.Length
  readonly string s;
  readonly int i;

  public StringSource(string s) {
    this.s = s; this.i = -1;
  }

  private StringSource(string s, int i) {
    this.s = s; this.i = i;
  }

  public char Current {
    get {
      if (i < 0) 
	throw new InvalidOperationException();
      else
	return s[i]; 
    }
  }

  public ISource MoveNext() {
    if (i+1 < s.Length) 
      return new StringSource(s, i+1);
    else 
      return null;
  }
}

// Parsers ---------------------------------------------------------

interface Parser<T> {
  Result<T> Parse(ISource src);
}

// Always succeeds

class Success<T> : Parser<T> {
  T result;

  public Success(T result) { 
    this.result = result; 
  }

  public Result<T> Parse(ISource src) {
    return new Succ<T>(result, src);
  }
}

// Always fails

class Failure<T> : Parser<T> {
  public Failure() { }

  public Result<T> Parse(ISource src) {
    return new Fail<T>();
  }
}

// Parse a T, then a U, and return the pair (T,U)

class Seq<T,U> : Parser<Pair<T,U> > {
  Parser<T> tp;
  Parser<U> up;

  public Seq(Parser<T> tp, Parser<U> up) { 
    this.tp = tp; this.up = up; 
  }

  public Result<Pair<T,U> > Parse(ISource src) {
    Result<T> tr = tp.Parse(src);
    if (tr.Success) {
      Result<U> ur = up.Parse(tr.Source);
      if (ur.Success) 
	return new Succ<Pair<T,U> >(new Pair<T,U>(tr.Value, ur.Value), 
				    ur.Source);
    }
    return new Fail<Pair<T,U> >();
  }
}

// Parse a T, then a U, and return the T

class SeqFst<T,U> : Parser<T> {
  Parser<T> tp;
  Parser<U> up;

  public SeqFst(Parser<T> tp, Parser<U> up) { 
    this.tp = tp; this.up = up; 
  }

  public Result<T> Parse(ISource src) {
    Result<T> tr = tp.Parse(src);
    if (tr.Success) {
      Result<U> ur = up.Parse(tr.Source);
      if (ur.Success) 
	return new Succ<T>(tr.Value, ur.Source);
    }
    return new Fail<T>();
  }
}

// Parse a T, then U, and return the U

class SeqSnd<T,U> : Parser<U> {
  Parser<T> tp;
  Parser<U> up;

  public SeqSnd(Parser<T> tp, Parser<U> up) { 
    this.tp = tp; this.up = up; 
  }

  public Result<U> Parse(ISource src) {
    Result<T> tr = tp.Parse(src);
    if (tr.Success) {
      Result<U> ur = up.Parse(tr.Source);
      if (ur.Success) 
	return new Succ<U>(ur.Value, ur.Source);
    }
    return new Fail<U>();
  }
}

// Parse a T and succeed with result, or else succeed without

class Opt<T> : Parser< Option<T> > {
  Parser<T> tp;

  public Opt(Parser<T> tp) {
    this.tp = tp;
  }

  public Result< Option<T> > Parse(ISource src) {
    Result<T> tr = tp.Parse(src);
    if (tr.Success) 
      return new Succ< Option<T> >(new Option<T>(tr.Value), tr.Source);
    else
      return new Succ< Option<T> >(new Option<T>(), src);
  }
}

// Parse a T in one of several ways

class Alt<T> : Parser<T> {
  Parser<T>[] ps;

  public Alt(Parser<T> tp, Parser<T> up) { 
    this.ps = new Parser<T>[] { tp, up };
  }

  public Alt(Parser<T>[] ps) { 
    this.ps = ps;
  }

  public Result<T> Parse(ISource src) {
    foreach (Parser<T> p in ps) {
      Result<T> res = p.Parse(src);
      if (res.Success)
	return new Succ<T>(res.Value, res.Source);
    }
    return new Fail<T>();
  }
}

// Parse zero or more T's, return list

class Star<T> : Parser<LinkedList<T> > {
  Parser<T> tp;

  public Star(Parser<T> tp) { 
    this.tp = tp; 
  }

  public Result<LinkedList<T> > Parse(ISource src) {
    LinkedList<T> res = new LinkedList<T>();
    Result<T> tr = tp.Parse(src);
    while (tr.Success) {
      res.AddLast(tr.Value);
      src = tr.Source;
      tr = tp.Parse(src);
    }
    return new Succ<LinkedList<T> >(res, src);
  }
}

// Parse one or more T's, return list

class Plus<T> : Star<T> {
  public Plus(Parser<T> tp) : base(tp) { }

  public new Result<LinkedList<T> > Parse(ISource src) {
    Result<LinkedList<T> > res = base.Parse(src);
    if (res is Succ<LinkedList<T> > && res.Value.Count >= 1)
      return res;
    else
      return new Fail<LinkedList<T> >();
  }
}

// Parse a character satisfying Ok(c)

abstract class ParseTestChar : Parser<char> { 
  public Result<char> Parse(ISource src) {
    ISource src1 = src.MoveNext(); 
    if (src1 != null) 
      if (Ok(src1.Current)) 
	return new Succ<char>(src1.Current, src1);
    return new Fail<char>();
  }
  
  public abstract bool Ok(char c);
}

// Parse a digit / parse a comma

class Digit : ParseTestChar { 
  public override bool Ok(char c) {
    return System.Char.IsDigit(c);
  }
}

class Comma : ParseTestChar { 
  public override bool Ok(char c) {
    return c == ',';
  }
}

// Check for a particular character

class ParseChar : ParseTestChar {
  char c;

  public ParseChar(char c) {
    this.c = c;
  }

  public override bool Ok(char c) {
    return this.c == c;
  }
}

// Parse the longest (possibly empty) prefix of characters satisfying Ok

abstract class ParseChars0 : Parser<string> { 
  public virtual Result<string> Parse(ISource src) {
    StringBuilder sb = new StringBuilder();
    ISource src1 = src;
    ISource src2 = src1.MoveNext();
    while (src2 != null && Ok(src2.Current)) {
      sb.Append(src2.Current);
      src1 = src2;
      src2 = src1.MoveNext();
    }
    return new Succ<string>(sb.ToString(), src1);
  }
  
  public abstract bool Ok(char c);
}

// Parse zero or more whitespace characters

class ParseWS : ParseChars0 { 
  public override bool Ok(char c) {
    return System.Char.IsWhiteSpace(c);
  }
}

// Skip initial whitespace, then parse a T

class SkipWS<T> : SeqSnd<string,T> {
  static readonly Parser<string> parseWS = new ParseWS();

  public SkipWS(Parser<T> tp) : base(parseWS, tp) { } 
}

// Parse the longest non-empty prefix of characters satisfying Ok

abstract class ParseChars1 : ParseChars0 { 
  public override Result<string> Parse(ISource src) {
    Result<string> res = base.Parse(src);
    if (res.Success && res.Value.Length > 0)
      return res;
    else
      return new Fail<string>();
  }
}

// Parse an integer; note the combination of ParseChars1 and Transform

class ParseInt : Transform<string, int> /* , Parser<int> */ {
  public ParseInt() : base(new ParseIntString()) { }

  public override int Trans(string s) {
    return int.Parse(s);
  }

  private class ParseIntString : ParseChars1 { 
    public override bool Ok(char c) {
      return System.Char.IsDigit(c);
    }
  }
}

// Parse the given string lit

class ParseLit : Parser<string> { 
  string lit;

  public ParseLit(string lit) {
    this.lit = lit;
  }

  public Result<string> Parse(ISource src) {
    ISource src1 = src;
    ISource src2 = src1.MoveNext(); 
    int i=0;
    while (i < lit.Length && src2 != null && src2.Current == lit[i]) {
      src1 = src2;
      src2 = src1.MoveNext();
      i++;
    }
    if (i >= lit.Length) 
      return new Succ<string>(lit, src1);
    else
      return new Fail<string>();
  }
}

// Parse a T and transform it to a U

abstract class Transform<T,U> : Parser<U> {
  Parser<T> tp;

  public Transform(Parser<T> tp) {
    this.tp = tp;
  }
  
  public Result<U> Parse(ISource src) {
    Result<T> tr = tp.Parse(src);
    if (tr.Success) 
      return new Succ<U>(Trans(tr.Value), tr.Source);
    return new Fail<U>();
  }
  
  public abstract U Trans(T t);
}

// A protoparser, or recursive parser builder

interface IProtoParser<T> {
  Parser<T> Build(Parser<T> parser);
} 

// Create a recursive parser from a protoparser by `tying the knot'

class ParseRec<T> : Parser<T> {
  Parser<T> tp;
  
  public ParseRec(IProtoParser<T> pp) {
    tp = pp.Build(this);
  }

  public Result<T> Parse(ISource src) {
    return tp.Parse(src);
  }
}

// Parse an int as a pair (digit, list of digits), and transform to int
// Possible, but not the right way to do it.

class ToInt : Transform<Pair<char, LinkedList<char> >, int> {
  public ToInt(Parser<Pair<char, LinkedList<char> > > p) : base(p) { }

  public override int Trans(Pair<char, LinkedList<char> > p) {
    int res = p.Fst - '0';
    IEnumerator<char> rest = p.Snd.GetEnumerator();
    while (rest.MoveNext()) 
      res = 10 * res + rest.Current - '0';
    return res;
  }
}

// ----------------------------------------------------------------------

public class TestParser {
  static void Main(string[] args) {
    if (args.Length != 1)
      Console.WriteLine("Usage: Parsers <s-expression>\n");
    else
      TestTree(args[0]);
    // IntParse(args);
  }

  static void IntParse(string[] args) {
    // Seq(Digit, Star(Digit)) --> int
    Parser<int> intparser = 
      new ToInt(new Seq<char, LinkedList<char> >
		(new Digit(), new Star<char>(new Digit())));
    ISource src1 = new StringSource(args[0]);
    Console.WriteLine(2 * intparser.Parse(src1).Value);
    Console.WriteLine(2 * new ParseInt().Parse(src1).Value);
    
    Parser<LinkedList<int> > commaintparser = 
      new Star<int>(new SeqSnd<char,int>(new Comma(), intparser));
    ISource src2 = new StringSource(args[1]);
    LinkedList<int> ints = commaintparser.Parse(src2).Value;
    int sum = 0;
    foreach (int i in ints)
      sum += i;
    Console.WriteLine(sum);
  }

  // Parsing Lisp trees:    tree ::= atom | number | ( tree * )

  static void TestTree(string s) {
    ISource src = new StringSource(s);
    Parser<Tree> tparse = new ParseRec<Tree>(new TreeProtoParser());
    Result<Tree> res = tparse.Parse(src);
    if (res.Success) 
      Console.WriteLine(res.Value);
    else
      Console.WriteLine("Parse failure");
  }
}

// Tree protoparser; we use ParseRec to make it recursive (in fact, to
// find its fixed-point)

class TreeProtoParser : IProtoParser<Tree> {
  public Parser<Tree> Build(Parser<Tree> tparse) {
    Parser<Tree> parseList = 
      new SeqSnd<char,Tree>(
	  new ParseChar('('), 
	      new SeqFst<Tree,char>(new ParseList(tparse),
				    new SkipWS<char>(new ParseChar(')'))));
    return 
      new SkipWS<Tree>(
	new Alt<Tree>(
	  new Parser<Tree>[] { new ParseNumber(), 
			       new ParseAtom(), 
			       parseList }));
  }
}

// Parsing the three kinds of trees

class ParseNumber : Transform<int, Tree> { 
  public ParseNumber() : base(new ParseInt()) { }
  
  public override Tree Trans(int i) {
    return new Number(i);
  }
}

class ParseAtom : Transform<string, Tree> { 
  public ParseAtom() : base(new ParseSymbol()) { }
  
  public override Tree Trans(string s) {
    return new Atom(s);
  }

  private class ParseSymbol : ParseChars1 { 
    public override bool Ok(char c) {
      return System.Char.IsLetterOrDigit(c);
    }
  }
}

class ParseList : Transform<LinkedList<Tree>, Tree> { 
  public ParseList(Parser<Tree> tparser) : base(new Star<Tree>(tparser)) { }
  
  public override Tree Trans(LinkedList<Tree> trees) {
    return new List(trees);
  }
}

// Representing trees

abstract class Tree { }

class Number : Tree {
  private readonly int v;

  public Number(int v) {
    this.v = v;
  }

  public override string ToString() {
    return v.ToString();
  }
}

class Atom : Tree { 
  private string atom;
  
  public Atom(string atom) {
    this.atom = atom;
  }

  public override string ToString() {
    return atom;
  }
}

class List : Tree {
  protected readonly LinkedList<Tree> elems;

  public List(LinkedList<Tree> elems) {
    this.elems = elems;
  }

  public override string ToString() {
    StringBuilder sb = new StringBuilder();
    sb.Append("(");
    bool first = true;
    foreach (Tree t in elems) {
      if (!first)
	sb.Append(" ");
      first = false;
      sb.Append(t);
    }
    sb.Append(")");
    return sb.ToString();
  }
}