//
// Each node in the parse tree can be a list or a symbol.
//
var NodeType = {
    List: 0,
    Symbol: 1
};

//
// Each node is defined by its type and content which in
// turn can be another node (list) or a symbol name.
//
function Node(type, content) {
    this.type = type;
    this.content = content;
}

//
// Helper function that generates a "Node" object given
// a symbol name.
//
function symbol(sym) {
    return new Node(NodeType.Symbol, sym);
}

//
// Helper function that generates a "Node" object given
// a list object.
//
function list(lst) {
    return new Node(NodeType.List, lst);
}

//
// Helper function that trims a string for leading/trailing white space.
//
String.prototype.trim = function() {
    return this.replace(/^\s+|\s+$/g, "");
}

//
// The LISP lexer that can tokenize a string of LISP code.
//
function Lexer(code) {
    this.code = code;
    var current = 0;
    var delims = "( )";

    this.nextToken = function() {
        var token = null;
        //
        // skip all white-space only tokens
        //
        while (((token = internalNextToken.apply(this)) != null) && (token.trim().length == 0));
        return token;
    }

    function internalNextToken() {
        //
        // if we have reached end of code then return null
        //
        if (current >= this.code.length)
            return null;

        //
        // accumulate characters into token till one of
        // the delimiters are encountered
        //
        var token = "";
        for (; current < this.code.length; ++(current)) {
            var ch = this.code.charAt(current);
            if (isDelim(ch)) {
                if (token.length == 0) {
                    token += ch;
                    ++current;
                }

                break;
            }

            token += ch;
        }

        return token;
    }

    function isDelim(ch) {
        return (delims.indexOf(ch) != -1);
    }
}

//
// The LISP parser class that generates a parse tree composed of
// "Node" object given a lexer object.
//
function Parser(lexer) {
    this.lexer = lexer;

    this.parseList = function() {
        var token;
        var lst = [];
        while (((token = this.lexer.nextToken()) != null) && (token != ")")) {
            switch (token) {
                case "(":
                    lst.push(this.parseList());
                    break;
                default:
                    lst.push(symbol(token));
                    break;
            }
        }

        return list(lst);
    };

    this.parse = function() {
        //
        // the first token MUST be a "("
        //
        if (this.lexer.nextToken() != "(")
            return null;
        return this.parseList();
    };
}