summaryrefslogtreecommitdiff
path: root/doc/curtailment.html
diff options
context:
space:
mode:
authorJed Barber <jjbarber@y7mail.com>2021-01-23 02:38:49 +1100
committerJed Barber <jjbarber@y7mail.com>2021-01-23 02:38:49 +1100
commitc7195329c60123b2363ba13863f6951a21d0ff57 (patch)
tree35eb2388650888a4301f326812fa3e5554fff52b /doc/curtailment.html
parent0b0c4df3dc7b94c139c5305ea0991a34f0c43238 (diff)
Implementation detail docs, some old notes removed
Diffstat (limited to 'doc/curtailment.html')
-rw-r--r--doc/curtailment.html55
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>
+