From 46fed171c49eee1ffe192e04ba34ec120bc486b0 Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Thu, 17 Dec 2020 14:47:12 +1100 Subject: Indirect left recursion should now work properly --- src/packrat-parsers.adb | 84 +++++++++++++++++++++++++++++++++++-------------- src/packrat-parsers.ads | 2 +- 2 files changed, 62 insertions(+), 24 deletions(-) (limited to 'src') diff --git a/src/packrat-parsers.adb b/src/packrat-parsers.adb index 06a0b00..01c4677 100644 --- a/src/packrat-parsers.adb +++ b/src/packrat-parsers.adb @@ -120,18 +120,29 @@ package body Packrat.Parsers is function Reusable (Result : in Combinator_Result; - Position : in Positive; + Main_Key : in Combo_Key; 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 Leftrecs.Contains (Working_Key) and then - Curtail_Maps.Element (Cursor) > Leftrecs.Element (Working_Key) - then - return False; + 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; end if; end loop; return True; @@ -142,12 +153,14 @@ package body Packrat.Parsers is (Context : in out Parser_Context) return Combinator_Result is - Result : Combinator_Result; + Result, Previous : Combinator_Result; + Combo : Combinator; + Left : Positive; begin if Context.Memotable.Contains (My_Key) then - Result := Context.Memotable.Element (My_Key); - if Reusable (Result, My_Key.Start, Context.Leftrectable) then - return Result; + Previous := Context.Memotable.Element (My_Key); + if Reusable (Previous, My_Key, Context.Leftrectable) then + return Previous; end if; end if; if My_Key.Start < Context.Current_Position then @@ -158,6 +171,28 @@ package body Packrat.Parsers is Context.Needs_More.Include (My_Key.Start); end if; if Context.Memotable.Contains (My_Key) then + for C in Previous.Curtails.Iterate loop + 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 + 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; + end if; + end loop; Context.Memotable.Replace (My_Key, Result); else Context.Memotable.Insert (My_Key, Result); @@ -237,9 +272,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)) > - Add.Element (Curtail_Maps.Key (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 @@ -263,6 +296,7 @@ package body Packrat.Parsers is (Target : in out Combinator_Result; Add : in Combinator_Result) is begin + Merge (Target.Curtails, Add.Curtails); case Target.Status is when Success => case Add.Status is @@ -286,17 +320,22 @@ package body Packrat.Parsers is when Needs_More => case Add.Status is when Success | Optional_More => - Target := Add; + Target.Results.Union (Add.Results); Target.Status := Optional_More; when Needs_More | Failure => null; end case; when Failure => - if Add.Status = Failure then - Merge (Target.Curtails, Add.Curtails); - else - Target := Add; - end if; + case Add.Status is + when Success | Optional_More => + Target.Results.Union (Add.Results); + Target.Status := Add.Status; + when Needs_More => + null; + Target.Status := Add.Status; + when Failure => + null; + end case; end case; end Merge; @@ -589,7 +628,8 @@ package body Packrat.Parsers is Salt.Results := Processed; return Salt; end Actual; - function Memo is new Memoize (To_Key (Start, Stamp'Access), Actual); + function Curt is new Curtailment (To_Key (Start, Stamp'Access), Input, Actual); + function Memo is new Memoize (To_Key (Start, Stamp'Access), Curt); begin return Memo (Context); end Stamp; @@ -617,7 +657,8 @@ package body Packrat.Parsers is Salt.Results := Processed; return Salt; end Actual; - function Memo is new Memoize (To_Key (Start, Ignore'Access), Actual); + function Curt is new Curtailment (To_Key (Start, Ignore'Access), Input, Actual); + function Memo is new Memoize (To_Key (Start, Ignore'Access), Curt); begin return Memo (Context); end Ignore; @@ -727,9 +768,6 @@ package body Packrat.Parsers is is Salt : Combinator_Result; begin - if Params'Length = 0 then - return Empty (Input, Context, Start); - end if; for C of Params loop Merge (Salt, C (Input, Context, Start)); end loop; diff --git a/src/packrat-parsers.ads b/src/packrat-parsers.ads index e11d623..6040f4f 100644 --- a/src/packrat-parsers.ads +++ b/src/packrat-parsers.ads @@ -599,7 +599,7 @@ private function Reusable (Result : in Combinator_Result; - Position : in Positive; + Main_Key : in Combo_Key; Leftrecs : in Leftrectables.Map) return Boolean; -- cgit