asdf

cst.js

Object.defineProperty(Array.prototype, "top", {
    get: function(){ return this[this.length - 1]; },
    set: function(v){ return this[this.length - 1] = v; }
});

class Operator {
    constructor(symbol, monad, dyad, precedence, assoc){
        this.symbol = symbol;
        this.monad = monad;
        this.dyad = dyad;
        this.precedence = precedence;
        this.assoc = !!assoc;
    }
    
    get left(){
        return !this.assoc;
    }
    
    get right(){
        return this.assoc;
    }
    
    copy(){
        return new Operator(this.symbol, this.monad, this.dyad, this.precedence, this.assoc);
    }
    
    toString(){
        return `${this.symbol}`
    }
}

class Value {
    constructor(value, type){
        this.value = value;
        this.type = type;
    }
    
    toString(){
        return `${this.value}`;
    }
}

class Func {
    constructor(name, effect){
        this.name = name;
        this.effect = effect;
    }
    
    copy(){
        return new Func(this.name, this.effect);
    }
}

class OperatorNode {
    constructor(operator, children){
        this.operator = operator;
        this.children = children;
    }
    
    toString(){
        
    }
}

const disp = (token) => token.value || token.symbol || token;

class ConcreteSyntaxTree {
    constructor(props){
        Object.assign(this, props);
    }
    
    parse(str){
        let tokens = [];
        let ops = [...this.operators.keys()];
        for(let i = 0; i < str.length; i++){
            let cur = str[i];
            // console.log(cur, i);
            if(ops.some(e => e[0] === cur)){
                let build = cur;
                while(ops.some(e => e.indexOf(build + str[i + 1]) === 0)){
                    build += str[++i];
                }
                tokens.push(this.operators.get(build).copy());
            } else if(cur === "," || cur === "(" || cur === ")"){
                tokens.push(cur);
            } else if(/[0-9]/.test(cur)){
                let build = "";
                while(/[0-9]/.test(str[i])){
                    build += str[i++];
                }
                tokens.push(new Value(build, "number"));
                i--;
            } else if(/\w/.test(cur)){
                let build = "";
                while(/\w/.test(str[i]) && str[i]){
                    build += str[i++];
                }
                if(this.funcs.has(build)){
                    tokens.push(this.funcs.get(build).copy());
                } else {
                    tokens.push(new Value(build, "variable"));
                }
                i--;
            }
        }
        return tokens;
    }
    
    // TODO: error handling
    shunt(str){
        let tokens = this.parse(str);
        console.log(tokens.map(disp));
        let queue = [];
        let stack = [];
        let fArity = [];
        let previous = null;
        while(tokens.length){
            let token = tokens.shift();
            if(token instanceof Value){
                queue.push(token);
            } else if(token instanceof Func){
                fArity.push(1);
                stack.push(token);
            } else if(token instanceof Operator){
                if(!previous || previous instanceof Operator){
                    token.arity = 1;
                } else {
                    token.arity = 2;
                }
                while(stack.top instanceof Operator &&
                    token.arity === 2 && (
                    token.left  && token.precedence <= stack.top.precedence || 
                    token.right && token.precedence <  stack.top.precedence
                )){
                    queue.push(stack.pop());
                }
                stack.push(token);
            } else if(token === ","){
                fArity.top++;
                while(stack.top !== "(")
                    queue.push(stack.pop());
            } else if(token === "("){
                stack.push(token);
            } else if(token === ")"){
                while(stack.top !== "(")
                    queue.push(stack.pop());
                
                stack.pop();
                if(stack.top instanceof Func){
                    let func = stack.pop();
                    func.arity = fArity.pop();
                    queue.push(func);
                }
            }
            previous = token;
            console.log(disp(token), queue.map(disp), stack.map(disp));
        }
        
        return queue.concat(stack.reverse());
    }
    
    // convert to an CST
    convert(str){
        let tokens = this.shunt(str);
        let stack = [];
        for(let token of tokens){
            if(typeof token.arity !== "undefined"){
                let args = stack.splice(-token.arity);
                stack.push(new OperatorNode(token, args));
            } else {
                stack.push(token);
            }
        }
        return stack.shift();
    }
    
    compile(str){
        let tree = this.convert(str);
        let vrn = 0;
        let compiled = "";
        let traverse = (node) => {
            if(!(node instanceof OperatorNode)) return node.value;
            // console.log("CHILDREN", node.children[1]);
            let vr = this.allocator(vrn++);
            console.log(vr, node);
            if(node.operator instanceof Operator){
                if(node.operator.arity === 2){  // dyad
                    let leftSide = traverse(node.children[0]);
                    let rightSide = traverse(node.children[1]);
                    compiled += `${vr} = ${leftSide};\n`;
                    compiled += `${vr} = ${node.operator.dyad(vr, rightSide)};\n`;
                } else {
                    let side = traverse(node.children[0]);
                    compiled += `${vr} = ${node.operator.monad(side)};\n`;
                }
                return vr;
            } else if(node.operator instanceof Func){
                // TODO
            }
        }
        traverse(tree);
        return compiled;
    }
}

ConcreteSyntaxTree.NO_CASE = Symbol("no case is defined");

// compiles to javascript
let test = new ConcreteSyntaxTree({
    allocator: (index) => `_${index.toString(36)}`,
    operators: new Map([
        ["+", new Operator(
            "+",
            (x) => `Math.abs(${x})`,
            (x, y) => `${x}+${y}`,
            2000
        )],
        ["-", new Operator(
            "-",
            (x) => `-${x}`,
            (x, y) => `${x}-${y}`,
            2000
        )],
        ["*", new Operator(
            "*",
            (x) => `x*x`,
            (x, y) => `${x}*${y}`,
            4000
        )],
        ["/", new Operator(
            "/",
            (x) => `1/x`,
            (x, y) => `${x}/${y}`,
            4000
        )],
        ["//", new Operator(
            "//",
            ConcreteSyntaxTree.NO_CASE,
            (x, y) => `Math.floor(${x}/${y})`,
            4000
        )],
        ["^", new Operator(
            "^",
            ConcreteSyntaxTree.NO_CASE,
            (x, y) => `Math.pow(${x},${y})`,
            6000,
            true
        )]
    ]),
    funcs: new Map([
        ["print", new Func("print", (a, b) => `console.log(${a},${b}),${b}`)]
    ])
});

// TODO: figure out why this doesn't work
let str = "1 * -2 / 3 + 4";

// console.log(test.parse(str));
console.log(str);
console.log(test.shunt(str).map(e=>e+""));
// console.log();
// console.log(test.convert(str));
// console.log();
// console.log(test.compile(str));