From 703a09c135d04b37be34d95915c32d70d730894c Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Tue, 12 Jan 2021 20:33:53 +1100 Subject: Memoize and curtailment for left recursion should be correct now --- curtail.txt | 2 + src/packrat-parsers.adb | 132 +++++++++++++++++++++--------------------------- src/packrat-parsers.ads | 2 +- 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; -- cgit