import std.stdio, std.ascii, std.conv;

alias ParserBase!(int) b;

/// Program entry point.
void main() {
    b.Parser p = new b.Parser();

	MyLexer l = new MyLexer("5+3-4");

	l.Add(new b.InfixOperator("+", 10, function int(int left, int right) {
		return left + right;
	}));

	l.Add(new b.InfixOperator("-", 10, function int(int left, int right) {
		return left - right;
	}));

	l.Add(new b.Token("(end)", -1));

	assert(p.Parse(l) == 4);
}

/// Simple lexer that reads tokens from a string
class MyLexer : b.ILexer {
	string input;
	b.Token[string] Symbols;

	/// Intialises the lexer using the given string.
	this(string inp) {
		this.input = inp;
	}

	/// Adds a standard token to the lexer.
	void Add(b.Token t) {
		this.Symbols[t.Name] = t;
	}

	/// Gets the next token from the string.
	b.Token Next() {
		if (this.input.length == 0) {
			return this.Symbols["(end)"];
		} else if (this.input[0] == '+') {
			this.input = this.input[1 .. $];
			return this.Symbols["+"];
		} else if (this.input[0] == '-') {
			this.input = this.input[1 .. $];
			return this.Symbols["-"];
		} else if (isDigit(this.input[0])) {
			return new b.Literal(parse!int(this.input));
		} else {
			throw new Exception("Not really a token.");
		}
	}
}

/// Parser base template.
/// T is the type returned. This can be a numeric type or similar to have the
/// functions computed as they are parsed, or an AST class.
template ParserBase(T) {
	alias T function(T) UnaryOp;
	alias T function(T, T) BinaryOp;

	/// Base Token class. It is generally more appropriate to use one of its
	/// child classes instead.
	class Token {
		string Name;
		int Lbp;
		Parser parent;

		this(string name, int lbp) {
			this.Name = name;
			this.Lbp = lbp;
		}

		/// Called when the token appears at the beginning of an expression.
		/// Not handled by default.
		T Nud() {
			throw new Exception("Token used prefix.");
		}

		/// Called when the token appears in the middle of an expression.
		/// Not handled by default.
		T Led(T left) {
			throw new Exception("Token used infix.");
		}
	}

	/// Literal token class.
	/// Stores a value of type T and can only appear at the start of expressions,
	///   where it returs itself.
	class Literal : Token {
		T Value;

		this(T val) {
			super("(literal)", 0);
			this.Value = val;
		}

		T Nud() {
			return this.Value;
		}
	}

	/// Infix operator class.
	/// Handles basic Led handling and then calls the user set function on the
	///   two sides of the expression.
	class InfixOperator : Token {
		BinaryOp Op;

		this(string name, int lbp, BinaryOp op) {
			super(name, lbp);
			this.Op = op;
		}

		T Led(T left) {
			T right;
			assert(this.parent !is null, "Token has no parent parser");
			right = this.parent.Expression(this.Lbp);
			return this.Op(left, right);
		}
	}

	/// Handles basic Nud handling and calls the user set function on the right
	///   hand side.
	class PrefixOperator : Token {
		UnaryOp Op;

		this(string name, int lbp, UnaryOp op) {
			super(name, lbp);
			this.Op = op;
		}

		T Nud() {
			T right;
			assert(this.parent !is null, "Token has no parent parser");
			right = this.parent.Expression(this.Lbp);
			return this.Op(right);
		}
	}

	/// Uses Led to create a basic Postfix operator.
	class PostfixOperator : Token {
		UnaryOp Op;

		this(string name, int lbp, UnaryOp op) {
			super(name, lbp);
			this.Op = op;
		}

		T Led(T left) {
			return this.Op(left);
		}
	}

	/// Basic lexer interface.
	interface ILexer {
		Token Next();
	}

	/// Base parser class. Shouldn't need to be modified as most functionality
	///   can be created by creating specialised token types.
	class Parser {
		Token token;
		ILexer lexer;

		/// Parses an expression from the given lexer.
		T Parse(ILexer lex) {
			this.lexer = lex;

			this.Step();
			return this.Expression(0);
		}

		/// Parses an expression using the given right binding power (rbp).
		///   Don't call unless from within the Led or Nud token methods,
		///   the user must call Parser.Parse instead.
		T Expression(int rbp) {
			T left;
			Token t;

			t = this.token;
			this.Step();

			left = t.Nud();

			while (rbp <= token.Lbp) {
				t = this.token;
				this.Step();

				left = t.Led(left);
			}

			return left;
		}

		/// Utility function that steps to the next token, updates this.token
		/// and sets the Token.parent property. This should always be used
		/// instead of advancing in the lexer manually.
		void Step() {
			this.token = this.lexer.Next();
			this.token.parent = this;
		}

		/// Steps to the next token, making sure that the current token is of the
		///   correct type. This is useful when you are expecting a token to
		///   appear such as when parsing a group (<expression> you can use
		///   Parser.Step(Token(")")). Comparison is based on names, so two
		///   literals of different values would be considered equal.
		void Step(Token t) {
			if (this.token.Name != t.Name) {
				throw new Exception("Expected something else.");
			}

			this.Step();
		}
	}
}