Curtailment

From c7195329c60123b2363ba13863f6951a21d0ff57 Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Sat, 23 Jan 2021 02:38:49 +1100 Subject: Implementation detail docs, some old notes removed --- doc/curtailment.html | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 55 insertions(+) create mode 100644 doc/curtailment.html (limited to 'doc/curtailment.html') 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 @@ + + + + + + + Curtailment - Packrat Docs + + + + + + +

+ + Return to Contents + + +

CAUTION: This is implementation information and should not be + relied upon in any way when using the library.

+ +

A curtailment is information attached to a result denoting one or more + combinator/depth pairs.

+ +

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.

+ +

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.

+ +

When results are folded upwards, any curtailments are retained.

+ +

When two results are merged as in Sequence and Choice, if the + results share curtailments then the curtailment of greater depth is retained.

+ +

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.

+ +

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.

+ + + + + -- cgit