1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
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();
		}
	}
}