non-recursive JavaScript JSON parser
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 looke开发者_如何学JAVAd 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.
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.
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;
}
I recommend you to divide JSON string in chunks, and bring them on demand. May be using AJAX too, you can have a recipe that just fit your needs. Using a "divide and conquer" mechanism, I think you can still use common JSON parsing methods.
Hope that helps,
JSON parsing in browser is usually done with just eval, but preceding the eval with a regular expression "lint", that is supposed to make it safe to evaluate the JSON.
There is an example on this on wikipedia:
- http://en.wikipedia.org/wiki/JSON#Security_issues
精彩评论