From 6c296b5615699eac0fb569b5cfe29e96986904a5 Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Sat, 28 Nov 2020 14:24:02 +1100 Subject: Skeleton of Packrat.Parsers --- src/packrat-parsers.ads | 436 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 436 insertions(+) create mode 100644 src/packrat-parsers.ads (limited to 'src/packrat-parsers.ads') diff --git a/src/packrat-parsers.ads b/src/packrat-parsers.ads new file mode 100644 index 0000000..8a0f39c --- /dev/null +++ b/src/packrat-parsers.ads @@ -0,0 +1,436 @@ + + +with + + Packrat.Traits, + Packrat.Parse_Graphs; + +private with + + Ada.Containers.Ordered_Maps, + Ada.Containers.Ordered_Sets, + Ada.Containers.Indefinite_Holders; + + +generic + + with package Traits is new Packrat.Traits (<>); + with package Graphs is new Packrat.Parse_Graphs (Traits); + +package Packrat.Parsers is + + + -- Memoize only adds to the Parse_Graph result when it is successful + -- so the Parser_Context will need to keep track of unsuccessful combinator + -- at given positions + + -- If all combinators are memoized in a memotable then no need to keep track of call stack + -- To do that, use start point and function access as the key? + + -- If a combinator at a position is already in the memotable, return result + -- Else run combinator, add/update result in memotable, then return result + -- As a side effect of this, the entry in the memotable will be updated several times + -- while left recursion unwinds + + -- Combinators need to return value strings as well as the finish sets + + -- Two functions, Symbolize and Ignore?, to create a node in the graph and to discard + -- the current return value string + + -- Some way to join tokens-of-tokens into just tokens + + + + + type Parser_Context is private; + + Empty_Context : constant Parser_Context; + + + + + type Combinator_Result is private; + + type Combinator is access function + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + type Combinator_Array is array (Positive range <>) of Combinator; + + + + + type Component_Result is private; + + type Component is access function + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Component_Result; + + + + + type With_Input is access function + return Traits.Element_Array; + + + + + generic + Label : in Traits.Label_Enum; + with function Combo + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + function Root + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Component_Result; + + + + + generic + Root_Component : in Component; + procedure Parse + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Result : out Graphs.Parse_Graph); + + generic + Root_Component : in Component; + function Parse_Only + (Input : in Traits.Element_Array; + Context : in out Parser_Context) + return Graphs.Parse_Graph; + + generic + Root_Component : in Component; + function Parse_With + (Input : in With_Input; + Context : in out Parser_Context) + return Graphs.Parse_Graph; + + + + + generic + Label : in Traits.Label_Enum; + with function Combo + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + function Stamp + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + with function Combo + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + function Ignore + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + + + + generic + Params : in Combinator_Array; + function Sequence + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + Params : in Combinator_Array; + function Choice + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + with function Param + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + Number : in Positive; + function Count + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + with function Param + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + Minimum : in Natural := 0; + function Many + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + with function Param + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + with function Test + (Item : in Traits.Element_Type) + return Boolean; + Minimum : in Natural := 0; + function Many_Until + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + + + + generic + with function Test + (Item : in Traits.Element_Type) + return Boolean; + function Satisfy + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + with function Test + (Item : in Traits.Element_Type) + return Boolean; + with function Change + (From : in Traits.Element_Type) + return Traits.Element_Type; + function Satisfy_With + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + Item : in Traits.Element_Type; + function Match + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + Item : in Traits.Element_Type; + with function Change + (From : in Traits.Element_Type) + return Traits.Element_Type; + function Match_With + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + Items : in Traits.Element_Array; + function Multimatch + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + Number : in Positive := 1; + function Take + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + with function Test + (Item : in Traits.Element_Type) + return Boolean; + function Take_While + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + with function Test + (Item : in Traits.Element_Type) + return Boolean; + function Take_Until + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + + + + generic + EOL_Item : in Traits.Element_Type; + function Line_End + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + generic + EOF_Item : in Traits.Element_Type; + function Input_End + (Input : in Traits.Element_Array; + Context : in out Parser_Context; + Start : in Positive) + return Combinator_Result; + + +private + + + -- refactor Finish_Type from Parse_Graphs into Packrat and use here and in Lexers + + -- does the lexer handle input that doesn't start from 1 at the beginning? + + + -- results need to record what combinators were curtailed, if any, with leftrec count + + -- choice combinators can be curtailed by multiple combinators at once + + -- results need to deal with tokens to put in the graph somehow + + + -- Curtail when leftrec count exceeds number of remaining tokens plus 1 + -- for a given combinator/position + + + package Elem_Array_Holders is new Ada.Containers.Indefinite_Holders + (Element_Type => Traits.Element_Array, + "=" => Traits."="); + + package Token_Array_Holders is new Ada.Containers.Indefinite_Holders + (Element_Type => Traits.Tokens.Token_Array, + "=" => Traits.Tokens."="); + + function "<" + (Left, Right : in Elem_Array_Holders.Holder) + return Boolean; + + function "<" + (Left, Right : in Token_Array_Holders.Holder) + return Boolean; + + + + + type Combo_Key is record + Start : Positive; + Func : Combinator; + end record; + + function "<" + (Left, Right : in Combo_Key) + return Boolean; + + + + + type Combo_Result_Part is record + Finish : Natural; + Value : Elem_Array_Holders.Holder; + Tokens : Token_Array_Holders.Holder; + end record; + + function "<" + (Left, Right : in Combo_Result_Part) + return Boolean; + + package Result_Sets is new Ada.Containers.Ordered_Sets + (Element_Type => Combo_Result_Part); + + + + + function "<" + (Left, Right : in Combinator) + return Boolean; + + package Curtail_Maps is new Ada.Containers.Ordered_Maps + (Key_Type => Combinator, + Element_Type => Positive); + + + + + -- If there's anything in the Curtails, then Results should be empty + -- and vice versa... union? + type Combinator_Result is record + Results : Result_Sets.Set; + Curtails : Curtail_Maps.Map; + Status : Result_Status; + end record; + + type Component_Result is record + Status : Result_Status; + end record; + + + + + package Memotables is new Ada.Containers.Ordered_Maps + (Key_Type => Combo_Key, + Element_Type => Combinator_Result); + + package Leftrectables is new Ada.Containers.Ordered_Maps + (Key_Type => Combo_Key, + Element_Type => Positive); + + + + + type Parser_Context is record + Result_So_Far : Graphs.Parse_Graph; + Position : Positive := 1; + Offset : Natural := 0; + Status : Result_Status := Success; + Pass_Forward : Elem_Array_Holders.Holder; + Memotable : Memotables.Map; + Leftrectable : Leftrectables.Map; + Allow_Incomplete : Boolean := True; + end record; + + Empty_Context : constant Parser_Context := + (Result_So_Far => Graphs.Empty_Graph, + Position => 1, + Offset => 0, + Status => Success, + Pass_Forward => Elem_Array_Holders.Empty_Holder, + Memotable => Memotables.Empty_Map, + Leftrectable => Leftrectables.Empty_Map, + Allow_Incomplete => True); + + +end Packrat.Parsers; + + -- cgit