non-recursive JavaScript JSON parser

Question

I have a very large JSON string that I need to parse with in-browser JavaScript. Right now, in a few browsers, I run out of stack space. Unfortunately, my JSON can contain user strings, so I can't use eval or otherwise let the browser parse it.

I've looked at a few of the standard JavaScript JSON parsers, and they are recursive. Wondering if anyone knows of any JSON parser that is safe and non-recursive. I'd be willing for it to have fewer features -- I just have a giant array of objects.

Alternatively, if someone knows of one that might be easy to modify, that would be a big help too.

EDIT: On closer inspection the stack overflow is thrown by eval() used inside the parser. So, it must be recursive.

Answer 1

If eval throws stackoverflow, you can use this

http://code.google.com/p/json-sans-eval/

A JSON parser that doesn't use eval() at all.

Answer 2

I have written json parsers that are not recursive in several languages, but until now not in javascript. Instead of being recursive, this uses a local array named stack. In actionscript this was substantially faster and more memory efficient than recursion, and I assume javascript would be similar.

This implementation uses eval only for quoted strings with backslash escapes, as both an optimization and simplification. That could easily be replaced with the string handling from any other parser. The escape handling code is long and not related to recursion.

This implementation is not strict in (at least) the following ways. It treats 8 bit characters as whitespace. It allows leading "+" and "0" in numbers. It allows trailing "," in arrays and objects. It ignores input after the first result. So "[+09,]2" returns [9] and ignores "2".

function parseJSON( inJSON ) {
    var result;
    var parent;
    var string;

    var depth = 0;
    var stack = new Array();
    var state = 0;

    var began , place = 0 , limit = inJSON.length;
    var letter;

    while ( place < limit ) {
        letter = inJSON.charCodeAt( place++ );

        if ( letter <= 0x20 || letter >= 0x7F ) {   //  whitespace or control
        } else if ( letter === 0x22 ) {             //  " string
            var slash = 0;
            var plain = true;

            began = place - 1;
            while ( place < limit ) {
                letter = inJSON.charCodeAt( place++ );

                if ( slash !== 0 ) {
                    slash = 0;
                } else if ( letter === 0x5C ) {     //  \ escape
                    slash = 1;
                    plain = false;
                } else if ( letter === 0x22 ) {     //  " string
                    if ( plain ) {
                        result = inJSON.substring( began + 1 , place - 1 );
                    } else {
                        string = inJSON.substring( began , place );
                        result = eval( string );    //  eval to unescape
                    }

                    break;
                }
            }
        } else if ( letter === 0x7B ) {             //  { object
            stack[depth++] = state;
            stack[depth++] = parent;
            parent = new Object();
            result = undefined;
            state = letter;
        } else if ( letter === 0x7D ) {             //  } object
            if ( state === 0x3A ) {
                parent[stack[--depth]] = result;
                state = stack[--depth];
            }

            if ( state === 0x7B ) {
                result = parent;
                parent = stack[--depth];
                state = stack[--depth];
            } else {
                //  error got } expected state {
                result = undefined;
                break;
            }
        } else if ( letter === 0x5B ) {             //  [ array
            stack[depth++] = state;
            stack[depth++] = parent;
            parent = new Array();
            result = undefined;
            state = letter;
        } else if ( letter === 0x5D ) {             //  ] array
            if ( state === 0x5B ) {
                if ( undefined !== result ) parent.push( result );

                result = parent;
                parent = stack[--depth];
                state = stack[--depth];
            } else {
                //  error got ] expected state [
                result = undefined;
                break;
            }
        } else if ( letter === 0x2C ) {             //  , delimiter
            if ( undefined === result ) {
                //  error got , expected previous value
                break;
            } else if ( state === 0x3A ) {
                parent[stack[--depth]] = result;
                state = stack[--depth];
                result = undefined;
            } else if ( state === 0x5B ) {
                parent.push( result );
                result = undefined;
            } else {
                //  error got , expected state [ or :
                result = undefined;
                break;
            }
        } else if ( letter === 0x3A ) {             //  : assignment
            if ( state === 0x7B ) {
                //  could verify result is string
                stack[depth++] = state;
                stack[depth++] = result;
                state = letter;
                result = undefined;
            } else {
                //  error got : expected state {
                result = undefined;
                break;
            }
        } else {
            if ( ( letter >= 0x30 && letter <= 0x39 ) || letter === 0x2B || letter === 0x2D || letter === 0x2E ) {
                var             exponent = -2;
                var             real = ( letter === 0x2E );
                var             digits = ( letter >= 0x30 && letter <= 0x39 ) ? 1 : 0;

                began = place - 1;
                while ( place < limit ) {
                    letter = inJSON.charCodeAt( place++ );

                    if ( letter >= 0x30 && letter <= 0x39 ) {           //  digit
                        digits += 1;
                    } else if ( letter === 0x2E ) {                     //  .
                        if ( real ) break;
                        else real = true;
                    } else if ( letter === 0x45 || letter === 0x65 ) {  //  e E
                        if ( exponent > began || 0 === digits ) break;
                        else exponent = place - 1;
                        real = true;
                    } else if ( letter === 0x2B || letter === 0x2D ) {  //  + -
                        if ( place != exponent + 2 ) break;
                    } else {
                        break;
                    }
                }

                place -= 1;
                string = inJSON.substring( began , place );

                if ( 0 === digits ) break;  //  error expected digits
                if ( real ) result = parseFloat( string );
                else result = parseInt( string , 10 );
            } else if ( letter === 0x6E && 'ull' === inJSON.substr( place , 3 ) ) {
                result = null;
                place += 3;
            } else if ( letter === 0x74 && 'rue' === inJSON.substr( place , 3 ) ) {
                result = true;
                place += 3;
            } else if ( letter === 0x66 && 'alse' === inJSON.substr( place , 4 ) ) {
                result = false;
                place += 4;
            } else {
                //  error unrecognized literal
                result = undefined;
                break;
            }
        }

        if ( 0 === depth ) break;
    }

    return result;
}