blob: 9999dac154fd4253ace0c6e8f6c92ee346e20263 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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>
|
