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