Property: nodeHits and treeDepth

A well-known problem with recursive-descent parsers is that they may require exponential time. This is also sometimes referred to as catastrophic backtracking. With APG parsers this is less of a problem than with most regular expression pattern-matching engines because they never backtrack on repetitions—only on alternates. And even with alternates, the "first match wins" algorithm^† reduces the amount of backtracking even further. Nonetheless, exponential-time patterns can occur. The nodeHits and treeDepth parameters provide upper limits on the number of unit steps the parser may take and the maximum parse tree depth that the parser can reach, respectively.

^†Note on "first match wins", also sometimes refered to as "prioritized choice": Alternates are tried from left to right. The parser accepts the first successful match and no further alternates are tried.

Syntax

var exp    = new apgExp(pattern, "", nodeHits, treeDepth);
var result = exp.exec(input);

Parameters

• nodeHits: integer > 0: default Infinity: The maximum number of unit steps (parse tree node hits) that the parser is allowed to take. The parser will throw an Error exception if the limit is exceeded.
• treeDepth: integer > 0: default Infinity: The maximum allowed parse tree depth. The parser will throw an Error exception if the limit is exceeded.

Return

• exp.nodeHits - The input value of nodeHits.
• exp.treeDepth - The input value of treeDepth.
• result.nodeHits - The actual number of unit parser steps taken.
• result.treeDepth - The actual maximum parse tree depth reached.

Examples

The following exponential pattern, suggested by Bryan Ford, is used in the following examples.

var pattern;    
pattern  = 'S = *A\n';
pattern += 'A = B / C / "a"\n';
pattern += 'B = "a" S "b"\n';
pattern += 'C = "a" S "c"\n';

Example 1: nodeHits

var pattern, str, exp, result;    
exp = new apgExp(pattern, "", 100000);
str = "aaaaa";
try{
  for (var i = 0; i < 5; i += 1) {
    result = exp.exec(str);
    console.log("input: "+str+" node hits: " + result.nodeHits);
    str += "a";
  }
}catch(e){
  console.log("EXCEPTION: "+e.message);
}
/* result */
input: aaaaa node hits: 1817
input: aaaaaa node hits: 5462
input: aaaaaaa node hits: 16397
input: aaaaaaaa node hits: 49202
EXCEPTION: parser: maximum number of node hits exceeded: 100000

Example 2: treeDepth

var pattern, str, exp, result;    
exp = new apgExp(pattern, "", null, 50);
str = "aaaaa";
try{
  for (var i = 0; i < 5; i += 1) {
    result = exp.exec(str);
    console.log("input: "+str+" tree depth: " + result.treeDepth);
    str += "a";
  }
}catch(e){
  console.log("EXCEPTION: "+e.message);
}
/* result */
input: aaaaa tree depth: 32
input: aaaaaa tree depth: 38
input: aaaaaaa tree depth: 44
input: aaaaaaaa tree depth: 50
EXCEPTION: parser: maximum parse tree depth exceeded: 50