SitePoint Sponsor

User Tag List

Results 1 to 9 of 9
  1. #1
    SitePoint Addict
    Join Date
    Nov 2008
    Location
    Thailand
    Posts
    329
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)

    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

    PHP Code:
    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) ? 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]
                        //   {  {  }  {  {  }  }  } 

  2. #2
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)
    How about trying your hand at some recursion lessons. A good one to try is over at http://www.codecademy.com/courses/ja...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.
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  3. #3
    SitePoint Addict
    Join Date
    Nov 2008
    Location
    Thailand
    Posts
    329
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    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.

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

    function 
    walkNest(lvlfound){
      
      
    found found || brakRX.exec(strg);
        
        if (
    found == '{') {
          
    lvl = (lvl == undefined) ? 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] 

  4. #4
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)
    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:

    Code javascript:
    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:

    Code javascript:
    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);
    }
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  5. #5
    SitePoint Addict
    Join Date
    Nov 2008
    Location
    Thailand
    Posts
    329
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    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

  6. #6
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)
    Quote Originally Posted by RLM2008 View Post
    As I say maybe a bit out of my depth, so apologies if I am missing something.
    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.
    Last edited by paul_wilkins; Jul 2, 2014 at 18:58. Reason: fix iPad automunge
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  7. #7
    Unobtrusively zen silver trophybronze trophy
    paul_wilkins's Avatar
    Join Date
    Jan 2007
    Location
    Christchurch, New Zealand
    Posts
    14,729
    Mentioned
    104 Post(s)
    Tagged
    4 Thread(s)
    For example, the following is a nicely improved refactoring of the above, where it sanitises the input before recursing over it.

    Code javascript:
    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);
    }
    Programming Group Advisor
    Reference: JavaScript, Quirksmode Validate: HTML Validation, JSLint
    Car is to Carpet as Java is to JavaScript

  8. #8
    SitePoint Addict
    Join Date
    Nov 2008
    Location
    Thailand
    Posts
    329
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    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.

    Code JavaScript:
    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]

  9. #9
    SitePoint Addict
    Join Date
    Nov 2008
    Location
    Thailand
    Posts
    329
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    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

    Code JavaScript:
    ;!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
            '(?:[ \\n]*(',                                                  //[3] Vars and Props
            '(?:\\$?[-a-z]+ *?:(?!' + pseudos + ')(?:[ -;#\\w)(,%]*\\s*))*',//
            '))?',                                                          //
            '(?:\\s*(})[\\n ]*)?'                                           //[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\n  ' + parseVars(cssRule, prop) + ';'; });
     
                output += '\r\n}\r\n\r\n';
              }
              if (cssRule.length) {
                [].slice.call(cssRule).forEach(function (rule) { parse_CSS(rule); });
              }
              return output.trim();
            }(cssRules));
          };
     
        win.parseCSS = parseCSS;
     
    }(window);
    Last edited by paul_wilkins; Jul 21, 2014 at 02:21. Reason: code update


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •