Nested Recursion question

Hi,

Bit of advice/wisdom needed

A personal exercise, I’m having a go at writing a simple parser that will handle a nested script.

I’m currently running some basic tests using a recursive function. Still planning it out, but I intend to eventually populate an object with the various string matches.

The test I have coded appears to be going in the right direction, but it’s bugging me that possibly I’m not making best use of the recursive function and the stack. It process everything and then the complete stack is returned.

Recursion is still a weak point for me and sends my head into meltdown.

My original theory was that matching a closed bracket ‘}’ would somehow be used as a base condition that would return a stack value. Working up through the parents as it were. If an open bracket was matched then again values would be added to the stack. This would to and fro until the end. A bit sketchy I know.

If anyone can make sense of this or offer some advice it would be appreciated. Even some clues would be good.

Thanks

var strg = '{  {  }  {  {  }  }  }', // basic nest
    brakRX = /[}|{]/g, // simple match for { or }
    nest = [],
    nest2 = [];

function walkNest(lvl){

  var found = brakRX.exec(strg);

    if (found == '{') {
      lvl = (lvl == undefined) ? 0 : lvl + 1;
      nest.push(lvl);
      walkNest(lvl); // if +1 -> child
    } else if (found == '}'){
      nest.push(lvl);
      if (lvl != 0) { walkNest(lvl-1) }; // -> parent
    }

  // alternative to pushing. Unshift returned values from stack to array
  nest2.unshift(lvl);
  return nest;

}

console.log(walkNest()); // returned nest array  [0, 1, 1, 1, 2, 2, 1, 0]
console.log(nest2); //  [0, 1, 1, 1, 2, 2, 1, 0]
                    //   {  {  }  {  {  }  }  }

How about trying your hand at some recursion lessons. A good one to try is over at http://www.codecademy.com/courses/javascript-lesson-205/0/1

Fundamentally, you start with the fail condition first, and then build up from there. I saw an excellent video recently by Corey Haimes on using recursion to do a code kata on roman numerals. It is in ruby and not JavaScript, but the thought process that he describes throughout is a remarkably clear example of how things should be approached.

Hi Paul, good to see you are still on here. Thanks for the reply.

Going to check out the ruby link. Sounds good.

Looked at a codecademy tutorial yesterday. The usual factorial example. Pretty simple to understand.

I’ve found the debugger in firefox to be very useful. Gives you a good picture of what is happening with regards the stack etc.

Anyway I think I may have cracked it.

var strg = '{  {  }  {  {  }  }  }', // basic nest
    brakRX = /[}|{]/g, // simple match for { or }
    nest = [];

function walkNest(lvl, found){
  
  found = found || brakRX.exec(strg);
    
    if (found == '{') {
      lvl = (lvl == undefined) ? 0 : lvl + 1;
      nest.push(lvl);
      walkNest(lvl);
    } else if (found == '}') { return; }
  // '}' base condition met. returning stack
  // check next character before returning.
  nest.push(lvl);
  if (brakRX.exec(strg) == '{') { walkNest(lvl-1, '{'); }
  return nest;
  
}

console.log(walkNest()); // returned nest array  [0, 1, 1, 1, 2, 2, 1, 0]

I thought that I would use this recursion piece as an example with which to use test driven development for a recursive program, and found that the resulting program is much simpler than I though it would be.

The testing code using Jasmine has been built up test after test:


describe('recursive braces', function () {
    function expectBracesToEqual(braces, expected) {
        var actual = walkNext(braces);
        return expect(actual).toEqual(expected);
    }

    var braces;
    it('handles an empty string', function () {
        expectBracesToEqual('', []);
    });
    it('starts with 0 for the first opening brace', function () {
        expectBracesToEqual('{', [0]);
    });
    it('adds one for each opening brace', function () {
        expectBracesToEqual('{{{', [0, 1, 2]);
    });
    it('shows the same number for a closing brace', function () {
        expectBracesToEqual('{}', [0, 0]);
    });
    it('handles nested braces', function () {
        expectBracesToEqual(
            '{{}{}}',
            [0, 1, 1, 1, 1, 0]
        );
    });
    it('handles spaces braces', function () {
        expectBracesToEqual(
            '{ { } { } }',
            [0, 1, 1, 1, 1, 0]
        );
    });
    it('handles the example case from Sitepoint', function () {
        expectBracesToEqual(
            '{  {  }  {  {  }  }  }',
            [0, 1, 1, 1, 2, 2, 1, 0]
        );
    })
});

And the resulting program code that passes all of the above tests is:


function walkNext(braces, level) {
    var brace;

    if (!braces) {
        return [];
    }

    brace = braces.substring(0, 1);
    braces = braces.substring(1);
    level = level || 0;

    if (brace === '{') {
        return [level].concat(walkNext(braces, level + 1));
    }
    if (brace === '}') {
        return [level - 1].concat(walkNext(braces, level - 1));
    }
    return walkNext(braces, level);
}

Hi Paul,

Just had a look at your script. More than likely out my depth here, but running it through debugger using ‘{ { } { { } } }’, there are a few things that stand out to me.

In my first example it fills the stack, then after completion offloads the lot. Counting the processes in debugger it was somewhere around 75 processes. As I said it didn’t seem to be really making proper use of the stack to me.

In the second one I did if it finds an open bracket it calls walkNest putting items/variables on the stack. If it then finds a closed bracket it returns the stack, checks for the next match and depending on the bracket found e.g ‘{’ calls walkNest adding to the stack or ‘}’ returns subtracting from the stack. And so on.

In total to completion about 55 processes and at most 5 items on the stack.

Have just run through your code. Much like my first one it fills the stack, 21 items in total, then offloads the lot. In all about 200 processes to completion.

As I say maybe a bit out of my depth, so apologies if I am missing something.

Cheers

RLM

Further improvements could be made by some refactoring, such as to remove everything but braces before processing them. That’s the great thing about having tests, the fear of “what might break” when changing things is completely gone because you have instant feedback.

For example, the following is a nicely improved refactoring of the above, where it sanitises the input before recursing over it.


function walkNext(braces) {
    function recurse(braces, level) {
        var brace;

        if (!braces) {
            return [];
        }

        brace = braces.substring(0, 1);
        braces = braces.substring(1);
        level = level || 0;

        if (brace === '{') {
            return [level].concat(recurse(braces, level + 1));
        }
        return [level - 1].concat(recurse(braces, level - 1));
    }

    braces = braces.replace(/[^{}]/g, '');
    return recurse(braces);
}

Take on board your point about testing. It’s something I need to take the time to look into. I have a few books with chapters on that very subject and I’m usually guilty of skipping over it.

Meanwhile. The reason I’m harping on about the stack is I remember looking over Crockford’s walktheDOM script on here a few years ago. The way the stack was repeatedly added to or removed from was something that stuck in my mind.

Anyway have re-written the function based on his script.

var strg = '{  {  }  {  {  }  }  }',
    brakRX = /[}|{]/g,
    nest = [],
    found;

function walkNest(lvl){
  
  found = brakRX.exec(strg);
  
  while (found == '{') {
    nest.push(lvl = (lvl == undefined) ? 0 : lvl + 1);
    walkNest(lvl);
    found = brakRX.exec(strg);
    nest.push(lvl--);
  }
  return nest;
}

console.log(walkNest()); // returned nest array  [0, 1, 1, 1, 2, 2, 1, 0]

Thought it wouldn’t hurt to post a follow-up to the initial ground work. The idea/exercise was to create a parser to handle nested CSS script much like SASS. A good exercise in getting to grips or more comfortable with recursion. In addition a chance to brush up on regular expressions.

The parser converts the input text into a node-tree object. A check for closed brackets being used as the base condition.

I’m sure improvements can be made to the overall design etc. Error handling would be a good start, but it seems to be working up to a point. I have allowed for dropped semi-colons.

A test example here http://pixel-shack.com/rpgdigit/nestingTest.html

Inprog code below

;!function (win) {

  // Pseudo regex's required to differentiate between CSS properties and pseudo selectors. li:hover ~= display:block
  var pseudos = [
        'active|checked|default|dir\\\\(|disabled|empty|enabled|first|fullscreen|',
        'focus|hover|indeterminate|in-range|invalid|lang\\\\(|last|left|link|not\\\\(|',
        'nth|only|optional|out\\\\-|read|required|right|root|scope|target|valid|visited'
        ].join(''),

      cssRX = new RegExp([
        '(?: *?([.#a-z](?:[^:}{\\\\s]*|:(?:' + pseudos + ')| \\\\b)+))?',   //[1] Selector
        '(?:\\\\s*({))?',                                                 //[2] Open Bracket
        '(?:[ \\\
]*(',                                                  //[3] Vars and Props
        '(?:\\\\$?[-a-z]+ *?:(?!' + pseudos + ')(?:[ -;#\\\\w)(,%]*\\\\s*))*',//
        '))?',                                                          //
        '(?:\\\\s*(})[\\\
 ]*)?'                                           //[4] Closing Bracket
        ].join(''), 'gmi'),

      splitProps = /\\$?[\\-\\w]+ *?:[\\$\\-\\w #)(,%]+(?=[}\\s;]|$)/gi,       // properties and $variables
      cleanUpRX = /\\r|\\/\\*[^\\*]*\\*\\//gm,                                // Carriage returns and comments.

  // ------------------------------------------------------------------------------------------------------------------

      slice = function(obj){ return [].slice.call(obj); },

      // Filters properties using given regex. Returns an array of properties. [{ name: prop, value: value }, { ... ]
      filterMatches = function(matches, reg){

        return slice(matches)
          .filter( function (prop) {
            return ((prop.match(reg)) && prop)
          })
          .map(function (prop) {
            var props = prop.split(/\\s*:\\s*/);
            return {name: props[0], value: props[1]}
          });
      },

  // ---------------------------------- CSS Compiler ------------------------------------------------

  // Returns an array like object tree of CSS text broken down into selectors, properties and variables.
      compileCSS = function (cssInput) {

        cssRX.lastIndex = 0;
        cssInput = cssInput.replace(cleanUpRX,'');

        var mch = null;

        return (function walkCSS(child) {

          var obj, props;

          child = child || Object.create(null, {
            selector: { enumerable: true, value: '' }
          });

          while ((mch = cssRX.exec(cssInput)) && mch[0]) {

            props = (mch[3] && mch[3].match(splitProps));

            if (mch[1] === undefined && mch[4]) break;

            obj = Object.create(null, {
              selector: { enumerable: true, value: (mch[1] !== undefined) ? mch[1] : ''},
              parent: { enumerable: true, value: child },
              props: { enumerable: true, value: filterMatches(props, /^[a-z]/i ) }, // Match a property: value
              variables: { enumerable: true, value: filterMatches(props, /^\\$/) }   // Match a $variable: value
            });

            [].push.call(child, (mch[4] === undefined) ? walkCSS(obj) : obj);
          }
          return child;
        }());

      },

  // ----------------------------------------------------------------------------------------------

  // Parent lookup. Takes an optional context argument to bind callback to.
      parentLookUp = function (child, fn, obj) {

        if (obj) {
          while (child = child.parent) {
            obj = fn.call(obj, child);
          }
          return obj;
        } else {
          while (child = child.parent) fn(child);
        }
      },

  // Checks property values against $variables and replaces matches.
      parseVars = function(child, prop){

        parentLookUp(child, function(child){
          if (child.variables) {
            child.variables.forEach(
              function(vars){
                if (prop.value === vars.name) { prop.value = vars.value; }
              }
            )
          }
        });
        return prop.name + ': ' + prop.value;
      },

  // ---------------------------------- CSS Compiler ------------------------------------------------

      parseCSS = function (cssStrg) {

        var cssRules = compileCSS(cssStrg),
            output = '';

        console.log(cssRules); // Just for reference. See console.

        return (function parse_CSS(cssRule) {
          var parent = cssRule.parent,
              selector = cssRule.selector,
              props = cssRule.props;

          if (parent && props.length) {

            // Empty string passed to lookUp will be our initial 'this' context. Note: an empty string literal"" passes as null.
            output += [ parentLookUp(cssRule, function (child) {
                          return (child.selector) ? this.replace(/^/, child.selector + ' ') : this;
                        }, new String("")),// <-----
                        selector,
                        ' {'
                        ].join('');

            props.forEach(function (prop) { output += '\\r\
  ' + parseVars(cssRule, prop) + ';'; });

            output += '\\r\
}\\r\
\\r\
';
          }
          if (cssRule.length) {
            [].slice.call(cssRule).forEach(function (rule) { parse_CSS(rule); });
          }
          return output.trim();
        }(cssRules));
      };

    win.parseCSS = parseCSS;

}(window);