Parse Graph Operations

From da389927ddf9240bbba10b819eb782e80a5d6bf7 Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Tue, 19 Jan 2021 02:25:44 +1100 Subject: Basic HTML documentation added --- doc/parse_graph_op.html | 424 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 424 insertions(+) create mode 100644 doc/parse_graph_op.html (limited to 'doc/parse_graph_op.html') diff --git a/doc/parse_graph_op.html b/doc/parse_graph_op.html new file mode 100644 index 0000000..2cc3591 --- /dev/null +++ b/doc/parse_graph_op.html @@ -0,0 +1,424 @@ + + + + + + + Parse Graph Operations - Packrat Docs + + + + + + +

+ + Return to Contents + + +

While this uses a directed graph library with node and edge labels internally, it is rather + different from a usage point of view. A parse graph is designed around tokens (from + Packrat.Tokens) that can each have more tokens as children.

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+procedure Assign + (Target : in out Parse_Graph; + Source : in Parse_Graph); + +function Copy + (Source : in Parse_Graph) + return Parse_Graph; + +procedure Move + (Target, Source : in out Parse_Graph); +	Standard assignment operations that are common to most things in the Ada standard Container library.
+function Is_Empty + (Container : in Parse_Graph) + return Boolean; +	Tests whether a graph is empty.
+procedure Clear + (Container : in out Parse_Graph); +	Completely clears a graph, leaving it empty afterwards.
+function Debug_String + (Container : in Parse_Graph) + return String; +	Generate a string that shows a pretty printed structure of the graph in a similar way to page three of +the paper referenced in Further Reading.
+function Contains + (Container : in Parse_Graph; + Token : in Traits.Tokens.Token_Type) + return Boolean; + +function Contains + (Container : in Parse_Graph; + Position : in Traits.Tokens.Finished_Token_Type) + return Boolean; + +function Contains + (Container : in Parse_Graph; + Grouping : in Token_Group) + return Boolean; + +function Contains + (Container : in Parse_Graph; + Parent : in Traits.Tokens.Finished_Token_Type; + Subtokens : in Traits.Tokens.Finished_Token_Array) + return Boolean; +	Tests for whether a graph contains various things.
+function Reachable + (Container : in Parse_Graph; + Position : in Traits.Tokens.Finished_Token_Type) + return Boolean +with Pre => Container.Has_Root; +	Checks whether a given finished token is reachable somehow from one or more of the root tokens of +the graph.
+function All_Reachable + (Container : in Parse_Graph) + return Boolean +with Pre => Container.Has_Root; +	Checks whether all tokens in the graph are reachable from one or more of the root tokens.
+function Valid_Token + (Fin_Token : in Traits.Tokens.Finished_Token_Type) + return Boolean; +	Checks whether the start and finish values of a token make sense, or in other words that the finish +value is no more than one less than the start value..
+function Valid_Starts_Finishes + (Parent : in Traits.Tokens.Finished_Token_Type; + Subtokens : in Traits.Tokens.Finished_Token_Array) + return Boolean +with Pre => Subtokens'Length > 0; +	Checks whether the various start and finish values of all the tokens make sense for being a parent +and a list of children. All the starts and finishes of individual tokens must make sense as in +Valid_Token, all the children tokens must be in order, the parent start and finish range must +fully cover all the children start and finish ranges, and none of the children start and finish ranges +can overlap each other.
+function Loops_Introduced + (Container : in Parse_Graph; + Parent : in Traits.Tokens.Finished_Token_Type; + Subtokens : in Traits.Tokens.Finished_Token_Array) + return Boolean +with Pre => Subtokens'Length > 0 and + Valid_Starts_Finishes (Parent, Subtokens); +	Checks whether adding the given parent and children group connection would introduce a loop into +the graph.
+function Is_Sorted + (Finishes : in Traits.Tokens.Finish_Array) + return Boolean; + +function Is_Sorted + (Positions : in Traits.Tokens.Finished_Token_Array) + return Boolean; + +function Is_Sorted + (Groupings : in Token_Group_Array) + return Boolean; +	Checks whether various sorts of arrays are sorted.
+function No_Duplicates + (Finishes : in Traits.Tokens.Finish_Array) + return Boolean; + +function No_Duplicates + (Positions : in Traits.Tokens.Finished_Token_Array) + return Boolean; + +function No_Duplicates + (Groupings : in Token_Group_Array) + return Boolean; +	Checks whether there are any duplicates in various sorts of arrays.
+procedure Include + (Container : in out Parse_Graph; + Token : in Traits.Tokens.Token_Type) +with Post => Container.Contains (Token); +	Adds a token to the graph. If the graph already contains the token, this does nothing.
+procedure Connect + (Container : in out Parse_Graph; + Parent : in Traits.Tokens.Finished_Token_Type; + Subtokens : in Traits.Tokens.Finished_Token_Array) +with Pre => Subtokens'Length > 0 and + Valid_Starts_Finishes (Parent, Subtokens) and + not Container.Loops_Introduced (Parent, Subtokens); +	Adds a connection group between a parent token and some children tokens in the graph. If +any of the tokens involved is not in the graph already they are first added. If the connection +already exists in the graph, this does nothing.
+procedure Prune + (Container : in out Parse_Graph; + Token : in Traits.Tokens.Token_Type) +with Post => not Container.Contains (Token); + +procedure Prune + (Container : in out Parse_Graph; + Position : in Traits.Tokens.Finished_Token_Type) +with Post => not Container.Contains (Position); + +procedure Prune + (Container : in out Parse_Graph; + Grouping : in Token_Group) +with Post => not Container.Contains (Grouping); +	Removes various things from a graph. No effort is made to remove anything made unreachable +by these operations.
+procedure Delete_Unreachable + (Container : in out Parse_Graph) +with Pre => Container.Has_Root, + Post => Container.All_Reachable; +	Removes all unreachable tokens, edges, and otherwise from a graph. Note that if the graph has +no root tokens then this will become equivalent to Clear.
+function Has_Root + (Container : in Parse_Graph) + return Boolean; +	Checks whether a graph contains a root token.
+procedure Set_Root + (Container : in out Parse_Graph; + Tokens : in Traits.Tokens.Finished_Token_Array) +with Pre => (for all F of Tokens => Container.Contains (F.Token)), + Post => Container.Has_Root; +	Sets one or more root tokens for a graph.
+procedure Clear_Root + (Container : in out Parse_Graph) +with Post => not Container.Has_Root; +	Removes all root tokens from the graph. Note that the graph will still contain the tokens, +they just won't be considered root tokens anymore.
+function Root_Elements + (Container : in Parse_Graph) + return Traits.Tokens.Finished_Token_Array +with Pre => Container.Has_Root; +	Retrieves all the root tokens for a given graph.
+function Finish_List + (Container : in Parse_Graph; + Token : in Traits.Tokens.Token_Type) + return Traits.Tokens.Finish_Array +with Pre => Container.Contains (Token), + Post => Is_Sorted (Finish_List'Result) and + No_Duplicates (Finish_List'Result); +	For a given unfinished token and a graph, returns all valid finishes that the token could take +such that the finished token is in the graph.
+function Is_Leaf + (Container : in Parse_Graph; + Position : in Traits.Tokens.Finished_Token_Type) + return Boolean +with Pre => Container.Contains (Position); +	Predicate to check whether a finished token is a leaf node in the graph. That is, whether it +has no children.
+function Is_Branch + (Container : in Parse_Graph; + Position : in Traits.Tokens.Finished_Token_Type) + return Boolean +with Pre => Container.Contains (Position); +	Predicate to check whether a finished token is a branch node in the graph. That is, whether it +has children.
+function Subgroups + (Container : in Parse_Graph; + Position : in Traits.Tokens.Finished_Token_Type) + return Token_Group_Array +with Pre => Container.Contains (Position), + Post => Is_Sorted (Subgroups'Result) and + No_Duplicates (Subgroups'Result) and + (for all G of Subgroups'Result => Finish (G) = Position.Finish); +	Returns an array of all the groups of children of a particular token in the graph. There will only +be multiple groups if the graph is ambiguous at this point.
+function First_Index + (Grouping : in Token_Group) + return Positive; + +function Last_Index + (Grouping : in Token_Group) + return Positive; + +function Length + (Grouping : in Token_Group) + return Ada.Containers.Count_Type; + +function Element + (Grouping : in Token_Group; + Index : in Positive) + return Traits.Tokens.Finished_Token_Type +with Pre => Index in First_Index (Grouping) .. Last_Index (Grouping); +	These work as you would expect on an array/vector. Element returns a particular +child token in the given group.
+function Elements + (Grouping : in Token_Group) + return Traits.Tokens.Finished_Token_Array +with Post => Is_Sorted (Elements'Result) and + Valid_Starts_Finishes (Parent (Grouping), Elements'Result); +	Returns all the children tokens in the group as an array instead of a Token_Group.
+function Parent + (Grouping : in Token_Group) + return Traits.Tokens.Finished_Token_Type; +	Returns the parent token of the group.
+function Finish + (Grouping : in Token_Group) + return Traits.Tokens.Finish_Type; +	Returns the finishing position of the group, which is the same as the finish of the parent token.
+function Is_Root_Ambiguous + (Container : in Parse_Graph) + return Boolean +with Pre => Container.Has_Root; +	Checks whether the root tokens for a graph are ambiguous. The root is ambiguous if there are multiple +root tokens, or if there are multiple child groups attached to a root token.
+function Is_Ambiguous + (Container : in Parse_Graph) + return Boolean; +	Checks if the graph is ambiguous. That is, checks whether there are multiple root tokens or if +any token in the graph has multiple child groups attached to it.
+function Ambiguities + (Container : in Parse_Graph; + Ambiguous_Root : out Boolean) + return Traits.Tokens.Finished_Token_Array +with Post => Is_Sorted (Ambiguities'Result) and + No_Duplicates (Ambiguities'Result); +	Gives the parent tokens of all ambiguities in the graph.
+function Isomorphic + (Left, Right : in Parse_Graph) + return Boolean +with Pre => Left.Has_Root and Right.Has_Root; +	Checks whether the two graphs are isomorphic in structure. This means that the tokens and groups +are all the same except for any consistent offset in the start and finish values.
+function Isomorphic_Subgraph + (Left_Graph : in Parse_Graph; + Left_Position : in Traits.Tokens.Finished_Token_Type; + Right_Graph : in Parse_Graph; + Right_Position : in Traits.Tokens.Finished_Token_Type) + return Boolean +with Pre => Left_Graph.Contains (Left_Position) and + Right_Graph.Contains (Right_Position); +	Checks whether the subgraphs formed by the respective positions in each graph and all their connected +children are isomorphic. This means that all the tokens and groups in those subgraphs are all the same +except for any consistent offset in the start and finish values. Note that it is possible to check +for isomorphism between two subgraphs in the same graph.

+ + + + + -- cgit