Compiler Explorer

Source code

import std.stdio;

import lexer;
// - Lexer. Breaks down the input string into tokens(the string start, end, and token type)
import func;
// - Parser. Root node that will construct your tree recursively.

void main() {
    if (0) {
        writeln("Example 1");
        import expressions;
        auto if_expression_test = "if (1) { 6 } + 3";
        auto l = new lang_lexer(if_expression_test);
        auto f = expression.factory(l);
        writeln(f);
        writeln(f.evaluate());
    }

if (0) {
        // You will have a top level node, "File", "Module", "Class" or "Unit" - Something that represents 
        // a full file that is read in. This is just an example of parsing a function with RDP, along with a Pratt Parser
        // for operator precedence.        
        writeln("Example 2");
        auto source_code = "func main() { return (2 ** 3 ** 2 != 512) ? 10 : (20 * 2 == 4 * 10) ? 42 : 69; }";
        auto l = new lang_lexer(source_code);
        auto f = new funct(l);
        writeln(f);
    }

{ /* Pratt Parser */
        // This is a direct test of the expression parsing, which uses operator precedence
        // Also added evaluation of the AST tree expressions, shouldn't really be done her for a serious project.
        import expressions;
        writeln("Example 3");
        //auto source_code = "(1+2 != 3) ? 0 : (20 * 2 == 4 * 10) ? (7*8-3) : 69";
		auto source_code = "8 + sin(180/100) * (50 * 2)";
        auto l = new lang_lexer(source_code);
        auto f = expression.factory(l);
        writeln("Evaluating: " ~ source_code);
		//writeln(f);
        writeln("Answer is: ", f.evaluate());
    }
    return;
}

Source code

module expressions;

import node;

// --- Binding Power Table ---
// -- bp_lookup defines the binding powers of infix and postfix operators. --
// Smaller binding numbers are stronger binding operators.
struct binding_power { int left_power; int right_power; }
binding_power RightAssociative(int p) { return binding_power(p+1, p); }
binding_power LeftAssociative(int p)  { return binding_power(p - 1, p); }

binding_power bp_lookup(token_type type) {
    switch(type) {
        case token_type.PlusSign: return LeftAssociative(100);
        case token_type.MinusSign: return LeftAssociative(100);
        case token_type.StarSign: return LeftAssociative(200);
        case token_type.DivideSign: return LeftAssociative(200);
        case token_type.PowSign: return RightAssociative(99);
        case token_type.TernaryStart: return RightAssociative(1000);

case token_type.GreaterThan: return LeftAssociative(50);
        case token_type.EqualOrGreaterThan: return LeftAssociative(50);
        case token_type.LessThan: return LeftAssociative(50);
        case token_type.EqualOrLessThan: return LeftAssociative(50);
        case token_type.EqualSign: return LeftAssociative(50);
        case token_type.NotEqualSign: return LeftAssociative(50);

// Postfix is always Right Associative
        case token_type.BangSign: return RightAssociative(400);
		case token_type.LParen: return RightAssociative(500);
        default: return binding_power(0,0);
    }
}

// -- prefix_bp_lookup defines the binding powers of prefix operators --
int prefix_bp_lookup(token_type type) {
    switch(type) {
        case token_type.PlusSign: return 300;
        case token_type.MinusSign: return 300;
        default: return 0;
    }
}

// --- Main Pratt Parser ---
// loop is coded in the factory function.
abstract class expression: branch_node {

static expression factory(lexer_t l, int right_bp = 0) {
        expression result;

// Check to see if this is a prefix or a valid infix left-hand-side.
        if (l.front.type == token_type.Number) {
            result = new number_literal(l);
		} else if (l.front.type == token_type.Identifier) {
			result = new var_expression(l);
        } else if (l.front.type == token_type.LParen) {
            result = new sub_expression(l);
        } else if (l.front.type == token_type.if_keyword) {
            result = new if_expression(l);

// or check for Prefix operator..
        // --- Prefix Operator lookahead ---
        } else if ((l.front.type == token_type.PlusSign) || (l.front.type == token_type.MinusSign)) {
            result = new prefix_expression( l, prefix_bp_lookup(l.front.type) );
        }

// Postfix and Infix operators have binding powers.
        // If the binding power is stronger, the current expression is pushed down the AST tree
        while( right_bp < bp_lookup(l.front.type).left_power ) {
            
            // --- Postfix lookahead ---
            if (l.front.type == token_type.BangSign) {
                // This is performing an AST rotation, current result is made a child of the new expression node
                result = new postfix_expression(l, result);
            } else if (l.front.type == token_type.TernaryStart) {
                result = new ternary_expression(l, result);
			} else if (l.front.type == token_type.LParen) {
				import std.stdio;
				writeln("Creating Function Call");
				result = new function_call(l, result);

// --- Infix lookahead ---
            // It must be an infix operator. Anything that isn't an infix
            // or prefix is an error. (only infix and prefix operators have left binding power)
            // an Assert wouldn't hurt though to catch bugs
            } else {
                result = new infix_expression(l, result, bp_lookup(l.front.type).right_power );
            }         
        }

return result;
    }

abstract float evaluate();
}

class var_expression: expression {
	node_t[] var;
	
	this(lexer_t l) {
		match!(token_type.Identifier)(l, var);
	}
	override float evaluate() {
		return 0;
	}
}

class if_expression: expression {
    node_t[] predicate;
    node_t[] trueBranch;
    node_t[] falseBranch;

this(lexer_t l) {
        match!(token_type.if_keyword)(l);
        match!(expression)(l, predicate);
        match!(token_type.LCurly)(l);
        match!(expression)(l, trueBranch);
        match!(token_type.RCurly)(l);
        // TODO: Support else branch.
    }

override float evaluate() {
        // TODO: Evaluate predicate and then evaluate true or false.
        return (cast(expression)trueBranch[0]).evaluate();
    }
}

// Below are all the expression subtypes that the factory can return
class number_literal: expression {
    node_t[] value;

this(lexer_t l) {
        match!(token_type.Number)(l, value);
    }

override float evaluate() {
        import std.conv: to;
        return to!float(value[0].toString());
    }
}

class sub_expression: expression {
    node_t[] e_body;

this(lexer_t l) {
        match!(token_type.LParen)(l);
        match!(expression)(l, e_body);
        match!(token_type.RParen)(l);
    }

override float evaluate() {
        return (cast(expression)e_body[0]).evaluate();
    }
}

class infix_expression: expression {
    node_t[] lhs;
    token operator;
    node_t[] rhs;

this(lexer_t l, expression _lhs, int min_bp ) {
        lhs ~= _lhs;

operator = l.front;
        l.advance();

match!(expression)(l, rhs, min_bp);
    }

override float evaluate() {
        import std.math.exponential: pow;

auto lhs_res = (cast(expression)lhs[0]).evaluate();
        auto rhs_res = (cast(expression)rhs[0]).evaluate();

switch(operator.type) {
            case token_type.PlusSign: return lhs_res + rhs_res;
            case token_type.MinusSign: return lhs_res - rhs_res;
            case token_type.StarSign: return lhs_res * rhs_res;
            case token_type.DivideSign: return lhs_res / rhs_res;

case token_type.GreaterThan: return (lhs_res > rhs_res);
            case token_type.EqualOrGreaterThan: return (lhs_res >= rhs_res);
            case token_type.LessThan: return (lhs_res < rhs_res);
            case token_type.EqualOrLessThan: return (lhs_res <= rhs_res);
            case token_type.EqualSign: return (lhs_res == rhs_res);
            case token_type.NotEqualSign: return (lhs_res != rhs_res);

case token_type.PowSign: return pow(lhs_res, rhs_res);
            default: assert(0);
        }
    }
}

class prefix_expression: expression {
    token operator;
    node_t[] e_body;

this(lexer_t l, int min_bp) {
        operator = l.front;
        l.advance();

node_t[] tmp;
        match!(expression)(l, e_body, min_bp);
    }

override float evaluate() {
        auto body_res = (cast(expression)e_body[0]).evaluate();

switch(operator.type) {
            case token_type.PlusSign: return 0 + body_res;
            case token_type.MinusSign: return 0 - body_res;
            default: assert(0);
        }
    }
}

class function_call: expression {
	node_t[] func;
	node_t[] args;
	
	this(lexer_t l, expression _func) {
		import std.stdio;
		func ~= _func;
		match!(token_type.LParen)(l);
		match!(expression)(l, args);
		match!(token_type.RParen)(l);
	}
	
	override float evaluate() {
		import std.math;
		import std.conv;
		auto arg_res = to!float((cast(expression)args[0]).evaluate());
		import std.stdio;
		writeln("Sin = ", sin(arg_res));
		return sin(arg_res);
	}
}

class postfix_expression: expression {
    node_t[] e_body;
    token operator;

this(lexer_t l, expression _lhs) {
        e_body ~= _lhs;
        operator = l.front;
        l.advance();
    }

override float evaluate() {
        auto body_res = (cast(expression)e_body[0]).evaluate();

switch(operator.type) {
            case token_type.BangSign:
                int res = 1;
                for(int i = 1; i <= body_res; ++i) res *= i;
                return res;

default: assert(0);
        }
    }
}

class ternary_expression: expression {
    node_t[] predicate;
    node_t[] true_path;
    node_t[] false_path;

this(lexer_t l, expression _pred) {
        predicate ~= _pred;
        match!(token_type.TernaryStart)(l);
        match!(expression)(l, true_path, 0);
        match!(token_type.TernaryMiddle)(l);
        match!(expression)(l, false_path, 0);
    }

override float evaluate() {
        auto pred_res = (cast(expression)predicate[0]).evaluate();
        if (pred_res == 1) {
            return (cast(expression)true_path[0]).evaluate();
        } else {
            return (cast(expression)false_path[0]).evaluate();
        }
    }
}

Source code

module lexer;

import node;
import std.string : toStringz;
import std.ascii: isAlpha, isDigit;
import std.stdio;
import std.conv: to;

// The streaming lexer. There is a "token_type front" inherited from lexer_t.
// Which holds the current lexed token for lookahead purposes.

// Advance() reads in the next token into "front", one at a time.
class lang_lexer: lexer_t {
    char* current_pos;

public:

this(ref string source) {
        current_pos = cast(char*) toStringz(source);
        advance();
    }

override void advance() {
        // Remove Leading Whitespace
        while(*current_pos == ' ') current_pos += 1;

switch(*current_pos) {
            case 'a': .. case 'z':
                auto start_pos = current_pos;

while(*current_pos != '\0') {
                    if (!isAlpha(*current_pos)) break;
                    current_pos += 1;
                }
                char[] r = start_pos[0 .. (current_pos - start_pos)];
                
                // Is this identifier a keyword?
                if (r == "func") {
                    front = new token(start_pos, current_pos, token_type.func_keyword);
                } else if (r == "return") {
                    front = new token(start_pos, current_pos, token_type.return_keyword);
                } else if (r == "if") {
                    front = new token(start_pos, current_pos, token_type.if_keyword);
                } else {
                    front = new token(start_pos, current_pos, token_type.Identifier);
                }
                return;

case '0': .. case '9':
                auto start_pos = current_pos;

while(*current_pos != '\0') {
                    if (!isDigit(*current_pos)) break;
                    current_pos += 1;
                }
                front = new token(start_pos, current_pos, token_type.Number);
                return;

case ';':
                front = new token(current_pos, current_pos+1, token_type.semicolon);
                current_pos += 1;
                return;

case '(':
                front = new token(current_pos, current_pos+1, token_type.LParen);
                current_pos += 1;
                return;

case ')':
                front = new token(current_pos, current_pos+1, token_type.RParen);
                current_pos += 1;
                return;

case '+':
                front = new token(current_pos, current_pos+1, token_type.PlusSign);
                current_pos += 1;
                return;

case '*':
                switch(*(current_pos+1)) {
                    case '*':
                        front = new token(current_pos, current_pos+2, token_type.PowSign);
                        current_pos += 2;
                        return;
                    default:
                        front = new token(current_pos, current_pos+1, token_type.StarSign);
                        current_pos += 1;
                        return;
                }

case '-':
                front = new token(current_pos, current_pos+1, token_type.MinusSign);
                current_pos += 1;
                return;

case '/':
                front = new token(current_pos, current_pos+1, token_type.DivideSign);
                current_pos += 1;
                return;
            
            case '!':
                switch(*(current_pos+1)) {
                    case '=':
                        front = new token(current_pos, current_pos+2, token_type.NotEqualSign);
                        current_pos += 2;
                        return;
                    default:
                        front = new token(current_pos, current_pos+1, token_type.BangSign);
                        current_pos += 1;
                        return;
                }

case '>':
                switch(*(current_pos+1)) {
                    case '=':
                        front = new token(current_pos, current_pos+2, token_type.EqualOrGreaterThan);
                        current_pos += 2;
                        return;
                    default:
                        front = new token(current_pos, current_pos+1, token_type.GreaterThan);
                        current_pos += 1;
                        return;
                }

case '<':
                switch(*(current_pos+1)) {
                    case '=':
                        front = new token(current_pos, current_pos+2, token_type.EqualOrLessThan);
                        current_pos += 2;
                        return;
                    default:
                        front = new token(current_pos, current_pos+1, token_type.LessThan);
                        current_pos += 1;
                        return;
                }
            
            case '=':
                switch(*(current_pos+1)) {
                    case '=':
                        front = new token(current_pos, current_pos+2, token_type.EqualSign);
                        current_pos += 2;
                        return;
                    default:
                        front = new token(current_pos, current_pos+1, token_type.AssignmentSign);
                        current_pos += 1;
                        return;
                }

case '?':
                front = new token(current_pos, current_pos+1, token_type.TernaryStart);
                current_pos += 1;
                return;

case ':':
                front = new token(current_pos, current_pos+1, token_type.TernaryMiddle);
                current_pos += 1;
                return;

case '\0':
                front = new token(current_pos, current_pos+1, token_type.EndOfFile);
                return;

case '{':
                front = new token(current_pos, current_pos+1, token_type.LCurly);
                current_pos += 1;
                return;
            case '}':
                front = new token(current_pos, current_pos+1, token_type.RCurly);
                current_pos += 1;
                return;

default: 
                writeln("Unknown token");
                string r = to!string(current_pos);
                writeln(r);
                assert(0);
        }
    }
}

Source code

module node;
import std.conv: to;
import std.stdio;

enum token_type {
    EndOfFile = 0,
    Number,
    Identifier,
        func_keyword,
        return_keyword,
        if_keyword,
    LParen,
    RParen,
    LCurly,
    RCurly,
    PlusSign,
    MinusSign,
    StarSign,
    DivideSign,
    BangSign,
    PowSign,
    semicolon,

LessThan,
    GreaterThan,
    EqualSign,
    NotEqualSign,
    EqualOrGreaterThan,
    EqualOrLessThan,

TernaryStart,
    TernaryMiddle,

AssignmentSign,

//Unknown
}

abstract class lexer_t {
    token front;

void advance();
}

abstract class node_t {
}

class token: node_t {
    immutable(char)* start_ptr;
    immutable(char)* end_ptr;
    token_type type;

this(char* s, char* e, token_type t) {
        start_ptr = cast(immutable(char)*) s;
        end_ptr = cast(immutable(char)*) e;
        type = t;
    }

override string toString() {
        string r = start_ptr[0..(end_ptr - start_ptr)];
        return r;
    }
}

abstract class branch_node: node_t {
    node_t[] children;

void match(token_type lookFor)(lexer_t l) {
        if (l.front.type != lookFor) {
            writeln("Expected " ~ to!string(lookFor) ~ " Found " ~ to!string(l.front.type));
            assert(l.front.type == lookFor);
        }
        children ~= l.front;
        l.advance();
    }
    void match(token_type lookFor)(lexer_t l, ref node_t[] storeTo) {
        if (l.front.type != lookFor) {
            writeln("Expected " ~ to!string(lookFor) ~ " Found " ~ to!string(l.front));
            assert(l.front.type == lookFor);
        }
        auto tmp = l.front;
        storeTo ~= tmp;
        children ~= tmp;
        l.advance();
    }

void match(T: branch_node, S: node_t[])(lexer_t l, ref S storeTo) {
        static if( __traits(isAbstractClass, T )) {
            auto tmp = T.factory(l);
            children ~= tmp;
            storeTo ~= tmp;
        } else {
            auto tmp = new T(l);
            children ~= tmp;
            storeTo ~= tmp;
        }
    }

void match(T: branch_node, A)(lexer_t l, ref node_t[] storeTo, A v) {
        static if( __traits(isAbstractClass, T )) {
            auto tmp = T.factory(l, v);
            children ~= tmp;
            storeTo ~= tmp;
        } else {
            auto tmp = new T(l, v);
            children ~= tmp;
            storeTo ~= tmp;
        }
    }    
}

Source code