summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJed Barber <jjbarber@y7mail.com>2021-01-12 20:33:53 +1100
committerJed Barber <jjbarber@y7mail.com>2021-01-12 20:33:53 +1100
commit703a09c135d04b37be34d95915c32d70d730894c (patch)
tree4395fc75fd97593dec7380a99e6583d055ec6674
parent7c2ecebc8f68320fd159e1a9b810fa74daab7ca4 (diff)
Memoize and curtailment for left recursion should be correct now
-rw-r--r--curtail.txt2
-rw-r--r--src/packrat-parsers.adb132
-rw-r--r--src/packrat-parsers.ads2
3 files changed, 61 insertions, 75 deletions
diff --git a/curtail.txt b/curtail.txt
index 38fd238..b9c88b1 100644
--- a/curtail.txt
+++ b/curtail.txt
@@ -20,5 +20,7 @@ when depth of a curtail is less than or equal to remaining tokens of input after
when depth of curtail plus remaining tokens after furthest finish of a result is less than or equal to total input tokens plus one, curtail can be deleted from a result
+when depth of curtail plus remaining tokens after furthest finish of a result is less than or equal to remaining tokens at the start of a result, then curtail can be deleted from result, because in that case it is no longer possible for curtail to happen due to excessive combinator recursion
+
diff --git a/src/packrat-parsers.adb b/src/packrat-parsers.adb
index 7c89984..e4fa97d 100644
--- a/src/packrat-parsers.adb
+++ b/src/packrat-parsers.adb
@@ -120,29 +120,18 @@ package body Packrat.Parsers is
function Reusable
(Result : in Combinator_Result;
- Main_Key : in Combo_Key;
+ Position : in Positive;
Leftrecs : in Leftrectables.Map)
return Boolean
is
- Position : Positive := Main_Key.Start;
Working_Key : Combo_Key;
begin
for Cursor in Result.Curtails.Iterate loop
Working_Key := To_Key (Position, Curtail_Maps.Key (Cursor));
- if Working_Key = Main_Key then
- if not Leftrecs.Contains (Working_Key) then
- if Curtail_Maps.Element (Cursor) > 1 then
- return False;
- end if;
- elsif Curtail_Maps.Element (Cursor) > Leftrecs.Element (Working_Key) + 1 then
- return False;
- end if;
- else
- if not Leftrecs.Contains (Working_Key) or else
- Curtail_Maps.Element (Cursor) > Leftrecs.Element (Working_Key)
- then
- return False;
- end if;
+ if not Leftrecs.Contains (Working_Key) or else
+ Curtail_Maps.Element (Cursor) > Leftrecs.Element (Working_Key)
+ then
+ return False;
end if;
end loop;
return True;
@@ -159,7 +148,7 @@ package body Packrat.Parsers is
begin
if Context.Memotable.Contains (My_Key) then
Previous := Context.Memotable.Element (My_Key);
- if Reusable (Previous, My_Key, Context.Leftrectable) then
+ if Reusable (Previous, My_Key.Start, Context.Leftrectable) then
return Previous;
end if;
end if;
@@ -175,22 +164,17 @@ package body Packrat.Parsers is
Combo := Curtail_Maps.Key (C);
if Context.Leftrectable.Contains (To_Key (My_Key.Start, Combo)) then
Left := Context.Leftrectable.Element (To_Key (My_Key.Start, Combo));
- if Combo = My_Key.Func then
- Left := Left + 1;
- end if;
- if Result.Curtails.Contains (Combo) then
+ if not Result.Results.Is_Empty and then
+ Result.Results.Last_Element.Finish - Left > My_Key.Start
+ then
+ Result.Curtails.Exclude (Combo);
+ elsif Result.Curtails.Contains (Combo) then
Result.Curtails.Replace (Combo, Left);
else
Result.Curtails.Insert (Combo, Left);
end if;
else
- if Combo = My_Key.Func then
- if Result.Curtails.Contains (Combo) then
- Result.Curtails.Replace (Combo, 1);
- else
- Result.Curtails.Insert (Combo, 1);
- end if;
- end if;
+ Result.Curtails.Exclude (Combo);
end if;
end loop;
Context.Memotable.Replace (My_Key, Result);
@@ -272,7 +256,7 @@ package body Packrat.Parsers is
begin
for Curse in Add.Iterate loop
if Target.Contains (Curtail_Maps.Key (Curse)) then
- if Target.Element (Curtail_Maps.Key (Curse)) > Curtail_Maps.Element (Curse) then
+ if Target.Element (Curtail_Maps.Key (Curse)) < Curtail_Maps.Element (Curse) then
Target.Replace (Curtail_Maps.Key (Curse), Curtail_Maps.Element (Curse));
end if;
else
@@ -631,10 +615,10 @@ package body Packrat.Parsers is
Salt.Results := Processed;
return Salt;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Stamp'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Stamp'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Stamp'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Stamp'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Stamp;
@@ -660,10 +644,10 @@ package body Packrat.Parsers is
Salt.Results := Processed;
return Salt;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Ignore'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Ignore'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Ignore'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Ignore'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Ignore;
@@ -726,10 +710,10 @@ package body Packrat.Parsers is
Complete_Status (Salt, Context.Allow_Incomplete);
return Salt;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Sequence'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Sequence'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Sequence'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Sequence'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Sequence;
@@ -752,10 +736,10 @@ package body Packrat.Parsers is
Salt := Cont_Param (Salt, Input, Context);
return Salt;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Sequence_2'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Sequence_2'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Sequence_2'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Sequence_2'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Sequence_2;
@@ -777,10 +761,10 @@ package body Packrat.Parsers is
Complete_Status (Salt, Context.Allow_Incomplete);
return Salt;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Choice'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Choice'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Choice'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Choice'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Choice;
@@ -799,10 +783,10 @@ package body Packrat.Parsers is
(Choice_One (Input, Context, Start),
Choice_Two (Input, Context, Start));
end Actual;
- function Curt is new Curtailment (To_Key (Start, Choice_2'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Choice_2'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Choice_2'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Choice_2'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Choice_2;
@@ -836,10 +820,10 @@ package body Packrat.Parsers is
Complete_Status (Salt, Context.Allow_Incomplete);
return Salt;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Count'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Count'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Count'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Count'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Count;
@@ -883,10 +867,10 @@ package body Packrat.Parsers is
Complete_Status (Salt, Context.Allow_Incomplete);
return Salt;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Many'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Many'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Many'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Many'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Many;
@@ -917,10 +901,10 @@ package body Packrat.Parsers is
end return;
end case;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Followed_By'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Followed_By'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Followed_By'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Followed_By'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Followed_By;
@@ -955,10 +939,10 @@ package body Packrat.Parsers is
end if;
end case;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Not_Followed_By'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Not_Followed_By'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Not_Followed_By'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Not_Followed_By'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Not_Followed_By;
@@ -981,10 +965,10 @@ package body Packrat.Parsers is
begin
return Sep_End_By (Input, Context, Start);
end Actual;
- function Curt is new Curtailment (To_Key (Start, Many_Until'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Many_Until'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Many_Until'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Many_Until'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Many_Until;
@@ -1005,10 +989,10 @@ package body Packrat.Parsers is
Complete_Status (Salt, Context.Allow_Incomplete);
return Salt;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Optional'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Optional'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Optional'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Optional'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Optional;
@@ -1034,10 +1018,10 @@ package body Packrat.Parsers is
return Full_Seq (Input, Context, Start);
end if;
end Actual;
- function Curt is new Curtailment (To_Key (Start, Separate_By'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Separate_By'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Separate_By'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Separate_By'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Separate_By;
@@ -1056,10 +1040,10 @@ package body Packrat.Parsers is
begin
return End_Seq (Input, Context, Start);
end Actual;
- function Curt is new Curtailment (To_Key (Start, Separate_End_By'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Separate_End_By'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Separate_End_By'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Separate_End_By'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Separate_End_By;
@@ -1080,10 +1064,10 @@ package body Packrat.Parsers is
begin
return Full_Seq (Input, Context, Start);
end Actual;
- function Curt is new Curtailment (To_Key (Start, Between'Access), Input, Actual);
- function Memo is new Memoize (To_Key (Start, Between'Access), Curt);
+ function Memo is new Memoize (To_Key (Start, Between'Access), Actual);
+ function Curt is new Curtailment (To_Key (Start, Between'Access), Input, Memo);
begin
- return Memo (Context);
+ return Curt (Context);
end Between;
diff --git a/src/packrat-parsers.ads b/src/packrat-parsers.ads
index 6040f4f..e11d623 100644
--- a/src/packrat-parsers.ads
+++ b/src/packrat-parsers.ads
@@ -599,7 +599,7 @@ private
function Reusable
(Result : in Combinator_Result;
- Main_Key : in Combo_Key;
+ Position : in Positive;
Leftrecs : in Leftrectables.Map)
return Boolean;