diff options
| author | Jed Barber <jjbarber@y7mail.com> | 2021-01-23 02:38:49 +1100 |
|---|---|---|
| committer | Jed Barber <jjbarber@y7mail.com> | 2021-01-23 02:38:49 +1100 |
| commit | c7195329c60123b2363ba13863f6951a21d0ff57 (patch) | |
| tree | 35eb2388650888a4301f326812fa3e5554fff52b /doc/curtailment.html | |
| parent | 0b0c4df3dc7b94c139c5305ea0991a34f0c43238 (diff) | |
Implementation detail docs, some old notes removed
Diffstat (limited to 'doc/curtailment.html')
| -rw-r--r-- | doc/curtailment.html | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/doc/curtailment.html b/doc/curtailment.html new file mode 100644 index 0000000..9999dac --- /dev/null +++ b/doc/curtailment.html @@ -0,0 +1,55 @@ + +<!DOCTYPE html> + +<html lang="en"> + <head> + <meta charset="utf-8"> + <title>Curtailment - Packrat Docs</title> + <link href="default.css" rel="stylesheet"> + </head> + + <body> + + + <h2>Curtailment</h2> + + <a href="index.html">Return to Contents</a> + + + <p><strong>CAUTION:</strong> This is implementation information and should not be + relied upon in any way when using the library.</p> + + <p>A curtailment is information attached to a result denoting one or more + combinator/depth pairs.</p> + + <p>Curtailment in general means that the result for a given combinator at a given + position is only valid when that combinator is next encountered at that position for + left recursion depth counts equal or greater than the curtailment.</p> + + <p>If the left recursion count of a combinator at a particular position exceeds the + number of remaining input tokens plus one, the combinator is curtailed at that count + depth and fails.</p> + + <p>When results are folded upwards, any curtailments are retained.</p> + + <p>When two results are merged as in <em>Sequence</em> and <em>Choice</em>, if the + results share curtailments then the curtailment of greater depth is retained.</p> + + <p>If a result has to be recalculated due to the previous result for a given + combinator at a given position not being valid due to being curtailed at a greater + left recursion depth, then the recalculated result has the previous result's + curtailments applied to it, except with the count depths replaced with the current + left recursion depths.</p> + + <p>When a result is recalculated and the depth of a curtailment plus the number of + remaining tokens after the furthest finish of a result is less than the remaining + tokens at the start of a result, then the curtail can be deleted from the result, + since then it is no longer possible for curtailment to happen due to excessive + left recursion count depth. This is algebraically equivalent to checking if the + furthest finish of a result minus the left recursion depth is greater than the + start position of the result.</p> + + + </body> +</html> + |