summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJed Barber <jjbarber@y7mail.com>2020-12-17 14:47:12 +1100
committerJed Barber <jjbarber@y7mail.com>2020-12-17 14:47:12 +1100
commit46fed171c49eee1ffe192e04ba34ec120bc486b0 (patch)
tree77bfee54332d4e91eb40f0e3bc9d68309ccdcd30
parent286eec82878639a13102542d5e37ae9f9acdb0ca (diff)
Indirect left recursion should now work properly
-rw-r--r--src/packrat-parsers.adb84
-rw-r--r--src/packrat-parsers.ads2
2 files changed, 62 insertions, 24 deletions
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;