lisp.js

const LPAREN = /^\s*\(/;
const RPAREN = /^\s*\)/;
const SPACES = /^\s+/;
const PLUS   = /^\s*\+/;
const MINUS  = /^\s*\-/;
const MULTI  = /^\s*\*/;
const DEVIDE = /^\s*\//;
const NUMBER = /^\s*\d+(\.\d+)?/;
const END    = /^\s*$/;

const TOKEN_REGEX = [
    LPAREN,
    RPAREN,
    PLUS,
    MINUS,
    MULTI,
    DEVIDE,
    NUMBER,
    END,
    SPACES
];

/*
class Lexer {
    constructor(input){
        this.parsed = input;
    }
    
    function next_token(){
    }
}
*/

function Lexer(input) {
    var prev_token, ret_prev_token = false;
    this.next_token = function(){
        if(ret_prev_token){
            ret_prev_token = false;
            return prev_token;
        }
        var token_kind = TOKEN_REGEX.find((regex) => input.match(regex) != undefined);
        ret = {kind: token_kind};
        if(token_kind == NUMBER){
            var value = parseInt(input.match(token_kind)[0]);
            ret["value"] = value;
        }
        if(token_kind !== undefined){
            input = input.replace(token_kind, "");
        }else{
            throw "Unknown Token";
        }
        prev_token = ret;
        return ret;
    }
    
    this.revert = function(){
        ret_prev_token = true;
    }
}

function Parser(input){
    var lexer = new Lexer(input);
    
    function number(){
        var token = lexer.next_token();
        if(token["kind"] == NUMBER){
            return token["value"];
        }else{
            console.log();
            throw "Unexpected Token";
        }
    }
    
    function list_parse(){
        var token = lexer.next_token();
        if(token["kind"] != LPAREN){
            lexer.revert();
            return number();
        }
        var operator = define_operator();
        var ret = number();
        token = lexer.next_token();
        while(token["kind"] != RPAREN && token["kind"] != END){
            lexer.revert();
            ret = operator(ret, number());
            token = lexer.next_token();
        }
        return ret;
    }
    
    function define_operator(){
        var maybe_operator = lexer.next_token(), ret;
        if(maybe_operator["kind"] == PLUS){
            ret = (i, j) => i + j;
        }else if(maybe_operator["kind"] == MINUS){
            ret = (i, j) => i - j;
        }else if(maybe_operator["kind"] == MULTI){
            ret = (i, j) => i * j;
        }else if(maybe_operator["kind"] == DEVIDE){ 
            ret = (i, j) => i / j;
        }else{
            throw "Unexpected Token: Maybe Operator";
        }
        return ret;
    }
    
    return list_parse();
}

console.log(Parser("(+ 1.0 2 3 4)"));
console.log(Parser("(- 1 2)"));
var str = "(+";
for(var i = 1; i <= 100; ++i){
    str += ` ${i}`;
}

str += ")";
console.log(Parser(str));

parse.js

const LPAREN = /^\s*\(/;
const RPAREN = /^\s*\)/;
const SPACES = /^\s+/;
const PLUS   = /^\s*\+/;
const MINUS  = /^\s*\-/;
const MULTI  = /^\s*\*/;
const DEVIDE = /^\s*\//;
const NUMBER = /^\s*\d+(\.\d+)?/;
const MOD    = /^\s*%/;
const POW    = /^\s*\^/;
const END    = /^\s*$/;

const TOKEN_REGEX = [
    LPAREN,
    RPAREN,
    PLUS,
    MINUS,
    MULTI,
    DEVIDE,
    NUMBER,
    MOD,
    POW,
    END,
    SPACES
];

/*
class Lexer {
    constructor(input){
        this.parsed = input;
    }
    
    function next_token(){
    }
}
*/

function Lexer(input) {
    var prev_token, ret_prev_token = false;
    this.next_token = function(){
        if(ret_prev_token){
            ret_prev_token = false;
            return prev_token;
        }
        var token_kind = TOKEN_REGEX.find((regex) => input.match(regex) != undefined);
        ret = {kind: token_kind};
        if(token_kind === NUMBER){
            var value = parseInt(input.match(token_kind)[0]);
            ret["value"] = value;
        }
        if(token_kind !== undefined){
            input = input.replace(token_kind, "");
        }else{
            throw "Unknown Token";
        }
        prev_token = ret;
        return ret;
    }
    
    this.revert = function(){
        ret_prev_token = true;
    }
}

function Parser(input){
    var lexer = new Lexer(input);
    
    const LOWER_OPERATOR = [PLUS, MINUS];
    const MIDDLE_OPERATOR = [MULTI, DEVIDE];
    const HIGH_OPERATOR = [MOD, POW];
    
    function number(){
        var token = lexer.next_token();
        if(token["kind"] === NUMBER){
            return token["value"];
        }else{
            throw "Unexpected Token";
        }
    }
    
    function parse_low_operator(){
        var ret = parse_middle_operator();
        var operator = lexer.next_token()["kind"];
        while(LOWER_OPERATOR.find((kind) => kind == operator) !== undefined){
            if(operator == PLUS){
                ret += parse_middle_operator();
            }else{
                ret -= parse_middle_operator();
            }
            operator = lexer.next_token()["kind"];
        }
        lexer.revert();
        return ret;
    }
    
    function parse_middle_operator(){
        var ret = parse_high_operator();
        var operator = lexer.next_token()["kind"];
        while(MIDDLE_OPERATOR.find((kind) => kind == operator) !== undefined){
            if(operator == MULTI){
                ret *= parse_high_operator();
            }else{
                ret /= parse_high_operator();
            }
            operator = lexer.next_token()["kind"];
        }
        lexer.revert();
        return ret;
    }
    
    function parse_high_operator(){
        var ret = number();
        var operator = lexer.next_token()["kind"];
        while(HIGH_OPERATOR.find((kind) => kind == operator) !== undefined){
            if(operator == MOD){
                ret = ret % number();
            }else{
                ret = Math.pow(ret, number());
            }
            operator = lexer.next_token()["kind"];
        }
        lexer.revert();
        return ret;
    }


    return parse_low_operator();
}

console.log(Parser("1 + 2 ^ 3 + 3 + 4 * 100"));
console.log(Parser("1 - 2"));
var str = "0";
for(var i = 1; i <= 100; ++i){
    str += ` + ${i}`;
}

console.log(Parser(str));