Parsing JSON with JavaScript I need to write some JavaScript code that will take a JSON string, parse it, and return the names of the most-deeply nested properties. For example, for this input:

var json = 
"{\
foo: {\
  bar: 'something',\
  baz: {\
    jack: 'other',\
  },\
  bob: {\
    bill: 'hello',\
    bilbo: 11,\
      baggins: {\
        fizz: 'buzz'\
        finger: 'bang'\
      }\
    }\
  }\
}";


it should return ['fizz', 'finger']. There are a couple of caveats:


the parsing must be done "manually"- i.e. I can't use eval or a JS library to parse the JSON
the JSON property values are guaranteed to be strings, numbers, or objects, i.e. no arrays


Here's what I've come up with so far. The main function is findDeepestLeaveNodes. At the moment the code is a bit inefficient as it has to iterate twice over the whole input String. I'd like to improve this if possible, and am also looking for suggestions for improving the code quality.

var constants = {
    BLOCK_START: '{',
    BLOCK_END: '}'
};

function findDeepestLeaveNodes(json) {

    var maxNesting = getMaxNesting(json);
    var currentNestLevel = 0;
    var results = [];
    var jsonLength = json.length;

    for (var currentCharIndex = 0; currentCharIndex &lt; jsonLength; currentCharIndex++) {
        var currentChar = json.charAt(currentCharIndex);        
        //console.log("Nesting level " + currentNestLevel + " at character '" + currentChar + "'");

        if (currentChar == constants.BLOCK_START) {

            // FIXME The following parsing is fairly fragile. It doesn't handle the possibility
            // that a '}' or ',' way occur inside a String and therefore do always close a block or
            // separate sibling JSON properties. To handle this we'd need to write a proper JSON parser.
            if (++currentNestLevel == maxNesting) {             
                // read the content of the current block
                var blockEndIndex = json.indexOf(constants.BLOCK_END, currentCharIndex);
                var currentBlock = json.substring(currentCharIndex + 1, blockEndIndex);

                // Each position in the properties array will contain a property name and it's value
                var properties = currentBlock.split(',');

                for (var i = 0; i &lt; properties.length; i++) {
                    // parse out the property name
                    var property = properties[i];
                    var separatorPosition = properties[i].indexOf(':');
                    var propertyName = property.substring(0, separatorPosition);

                    results.push(propertyName.trim());
                }               
            }           
        } else if (currentChar == constants.BLOCK_END) {            
            --currentNestLevel;
        }                   
    }
    return results;
}

function getMaxNesting(json) {
    var jsonlength = json.length;
    var currentNestLevel = 0;
    var maxNestLevel = 0;

    for (var i = 0; i &lt; jsonlength; i++) {
        var currentChar = json.charAt(i);

        if (currentChar == constants.BLOCK_START) {
            ++currentNestLevel;

        } else if (currentChar == constants.BLOCK_END) {            
            // update maxNestLevel if necessary
            maxNestLevel = Math.max(currentNestLevel, maxNestLevel);
            --currentNestLevel;
        }       
    }   
    return maxNestLevel;
}
I'd write it as a recursive descent parser since this is quite simple:

http://en.wikipedia.org/wiki/Recursive_descent_parser

Actually I already did this a couple of years back, when I wanted to create something that simply formats and highlights JSON a bit. If you can understand it, then you can modify it to your needs:

&lt;html&gt;
    &lt;head&gt;
        &lt;style type="text/css"&gt;
.str
{
    color: green;
}

.obj
{
    font-weight: bold;
}

.num
{
    color: red;
}
        &lt;/style&gt;
        &lt;script language="javascript" type="text/javascript"&gt;

String.prototype.repeat = function(n) {
  result = '';
  for (var i = 0; i &lt; n; i++) result += this;
  return result;
}

function jsonFormater() {
  this.reset = function() {
    this.txt = '';
    this.pos = 0;
    this.result = '';
    this.indent = 0;
    this.classes = Array();
  };

  this.undoindent = function() {
    this.indent -= 4;
    this.nline();
  };

  this.doindent = function() {
    this.indent += 4;
    this.nline();
  };

  this.nline = function() {
    this.result += '&lt;br /&gt;' + '&amp;nbsp;'.repeat(this.indent);
  };

  this.chClass = function(neu) {
    if (this.classes.length &gt; 0) this.result += '&lt;/span&gt;';
    this.result += '&lt;span class="' + neu + '"&gt;';
    this.classes.push(neu);
  };

  this.endClass = function() {
    this.classes.pop();
    this.result += '&lt;/span&gt;';
    if (this.classes.length &gt; 0) this.result += '&lt;span class="' + this.classes[this.classes.length - 1] + '"&gt;';
  };

  this.formatJson = function(txt) {
    this.txt = txt;
    this.pos = 0;
    this.result = '';
    while (this.pos &lt; this.txt.length) {
      if (this.txt[this.pos] == '{') this.parseObj();
      else if (this.txt[this.pos] =='[') this.parseArray();
      this.pos++;
    }

    return this.result;
  }

  this.parseObj = function(ende) {
    if (typeof ende =='undefined') var ende = '}';
    this.chClass('obj');

    do {
      if ((this.txt[this.pos] == '{') || (this.txt[this.pos] == '[')) this.nline();
      this.result += this.txt[this.pos];
      if (this.txt[this.pos] == ',') this.nline();
      if ((this.txt[this.pos] == '{') || (this.txt[this.pos] == '[')) this.doindent();
      this.pos++;
      if (this.txt[this.pos] == '{') this.parseObj();
      if (this.txt[this.pos] == '[') this.parseArray();
      if (this.txt[this.pos] == '"') this.parseString();
      if (/\d/.test(this.txt[this.pos])) this.parseNum();
      if ((this.txt[this.pos] == '}') || (this.txt[this.pos] == ']')) this.undoindent();
    } while ((this.pos &lt; this.txt.length) &amp;&amp; (this.txt[this.pos] != ende));

    this.result += this.txt[this.pos];
    this.pos++;
    this.endClass();
  };

  this.parseArray = function() {
    this.parseObj(']');
  };

  this.parseString = function() {
    this.chClass('str');
    do {
      this.result += this.htmlEscape(this.txt[this.pos]);
      this.pos++;
    } while ((this.pos &lt; this.txt.length) &amp;&amp; ((this.txt[this.pos] != '"') || (this.txt[this.pos - 1] == '\\')));

    this.result += this.htmlEscape(this.txt[this.pos]);
    this.pos++;
    this.endClass();
  };

  this.parseNum = function() {
    this.chClass('num');
    do {
      this.result += this.txt[this.pos];
      this.pos++;
    } while ((this.pos &lt; this.txt.length) &amp;&amp; (/[\d\.]/.test(this.txt[this.pos])));

    this.endClass();
  };

  this.htmlEscape = function(txt) {
    return txt.replace(/&amp;/,'&amp;amp;').replace(/&lt;/g, '&amp;lt;').replace(/&gt;/g, '&amp;gt;').replace(/"/g, '&amp;quot;');
  };

  this.reset();
}

var parser = new jsonFormater();

function go(txt) {
  document.getElementById('ausgabe').innerHTML = parser.formatJson(txt);
  parser.reset();
}

        &lt;/script&gt;
    &lt;/head&gt;
    &lt;body onLoad="go(document.getElementById('thetextarea').value);"&gt;
        &lt;textarea id="thetextarea" rows="25" cols="70" onKeyUp="go(this.value);"&gt;[{"Dies":"Ist ein Beispiel...","mit":["Arrays","und","so"]},{"alles":"sch&amp;ouml;n verschachtelt..."},"tippt einfach json-zeugs in dem grossen Feld.","Die Anzeige aktualisiert sich sofort...","Die Formatierungen sind als &amp;lt;style&amp;gt; gespeichert. Ihr k&amp;ouml;nnt sie so beliebig &amp;auml;ndern.",{"Zahlen":1,"sind":[1,4,55.67],"auch":"sch&amp;ouml;n"}]&lt;/textarea&gt;
        &lt;div id="ausgabe"&gt;&lt;/div&gt;
    &lt;/body&gt;
&lt;/html&gt;