diff options
Diffstat (limited to 'doc/parse_graph_op.html')
| -rw-r--r-- | doc/parse_graph_op.html | 424 |
1 files changed, 424 insertions, 0 deletions
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 @@ + +<!DOCTYPE html> + +<html lang="en"> + <head> + <meta charset="utf-8"> + <title>Parse Graph Operations - Packrat Docs</title> + <link href="default.css" rel="stylesheet"> + </head> + + <body> + + + <h2>Parse Graph Operations</h2> + + <a href="index.html">Return to Contents</a> + + + <p>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 + <em>Packrat.Tokens</em>) that can each have more tokens as children.</p> + + <table> + <tr> +<td><pre> +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); +</pre></td> +<td>Standard assignment operations that are common to most things in the Ada standard Container library.</td> + </tr> + <tr> +<td><pre> +function Is_Empty + (Container : in Parse_Graph) + return Boolean; +</pre></td> +<td>Tests whether a graph is empty.</td> + </tr> + <tr> +<td><pre> +procedure Clear + (Container : in out Parse_Graph); +</pre></td> +<td>Completely clears a graph, leaving it empty afterwards.</td> + </tr> + <tr> +<td><pre> +function Debug_String + (Container : in Parse_Graph) + return String; +</pre></td> +<td>Generate a string that shows a pretty printed structure of the graph in a similar way to page three of +the paper referenced in <a href="credits.html">Further Reading</a>.</td> + </tr> + <tr> +<td><pre> +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; +</pre></td> +<td>Tests for whether a graph contains various things.</td> + </tr> + <tr> +<td><pre> +function Reachable + (Container : in Parse_Graph; + Position : in Traits.Tokens.Finished_Token_Type) + return Boolean +with Pre => Container.Has_Root; +</pre></td> +<td>Checks whether a given finished token is reachable somehow from one or more of the root tokens of +the graph.</td> + </tr> + <tr> +<td><pre> +function All_Reachable + (Container : in Parse_Graph) + return Boolean +with Pre => Container.Has_Root; +</pre></td> +<td>Checks whether all tokens in the graph are reachable from one or more of the root tokens.</td> + </tr> + <tr> +<td><pre> +function Valid_Token + (Fin_Token : in Traits.Tokens.Finished_Token_Type) + return Boolean; +</pre></td> +<td>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..</td> + </tr> + <tr> +<td><pre> +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; +</pre></td> +<td>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 +<em>Valid_Token</em>, 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.</td> + </tr> + <tr> +<td><pre> +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); +</pre></td> +<td>Checks whether adding the given parent and children group connection would introduce a loop into +the graph.</td> + </tr> + <tr> +<td><pre> +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; +</pre></td> +<td>Checks whether various sorts of arrays are sorted.</td> + </tr> + <tr> +<td><pre> +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; +</pre></td> +<td>Checks whether there are any duplicates in various sorts of arrays.</td> + </tr> + <tr> +<td><pre> +procedure Include + (Container : in out Parse_Graph; + Token : in Traits.Tokens.Token_Type) +with Post => Container.Contains (Token); +</pre></td> +<td>Adds a token to the graph. If the graph already contains the token, this does nothing.</td> + </tr> + <tr> +<td><pre> +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); +</pre></td> +<td>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.</td> + </tr> + <tr> +<td><pre> +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); +</pre></td> +<td>Removes various things from a graph. No effort is made to remove anything made unreachable +by these operations.</td> + </tr> + <tr> +<td><pre> +procedure Delete_Unreachable + (Container : in out Parse_Graph) +with Pre => Container.Has_Root, + Post => Container.All_Reachable; +</pre></td> +<td>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 <em>Clear</em>.</td> + </tr> + <tr> +<td><pre> +function Has_Root + (Container : in Parse_Graph) + return Boolean; +</pre></td> +<td>Checks whether a graph contains a root token.</td> + </tr> + <tr> +<td><pre> +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; +</pre></td> +<td>Sets one or more root tokens for a graph.</td> + </tr> + <tr> +<td><pre> +procedure Clear_Root + (Container : in out Parse_Graph) +with Post => not Container.Has_Root; +</pre></td> +<td>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.</td> + </tr> + <tr> +<td><pre> +function Root_Elements + (Container : in Parse_Graph) + return Traits.Tokens.Finished_Token_Array +with Pre => Container.Has_Root; +</pre></td> +<td>Retrieves all the root tokens for a given graph.</td> + </tr> + <tr> +<td><pre> +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); +</pre></td> +<td>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.</td> + </tr> + <tr> +<td><pre> +function Is_Leaf + (Container : in Parse_Graph; + Position : in Traits.Tokens.Finished_Token_Type) + return Boolean +with Pre => Container.Contains (Position); +</pre></td> +<td>Predicate to check whether a finished token is a leaf node in the graph. That is, whether it +has no children.</td> + </tr> + <tr> +<td><pre> +function Is_Branch + (Container : in Parse_Graph; + Position : in Traits.Tokens.Finished_Token_Type) + return Boolean +with Pre => Container.Contains (Position); +</pre></td> +<td>Predicate to check whether a finished token is a branch node in the graph. That is, whether it +has children.</td> + </tr> + <tr> +<td><pre> +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); +</pre></td> +<td>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.</td> + </tr> + <tr> +<td><pre> +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); +</pre></td> +<td>These work as you would expect on an array/vector. <em>Element</em> returns a particular +child token in the given group.</td> + </tr> + <tr> +<td><pre> +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); +</pre></td> +<td>Returns all the children tokens in the group as an array instead of a <em>Token_Group</em>.</td> + </tr> + <tr> +<td><pre> +function Parent + (Grouping : in Token_Group) + return Traits.Tokens.Finished_Token_Type; +</pre></td> +<td>Returns the parent token of the group.</td> + </tr> + <tr> +<td><pre> +function Finish + (Grouping : in Token_Group) + return Traits.Tokens.Finish_Type; +</pre></td> +<td>Returns the finishing position of the group, which is the same as the finish of the parent token.</td> + </tr> + <tr> +<td><pre> +function Is_Root_Ambiguous + (Container : in Parse_Graph) + return Boolean +with Pre => Container.Has_Root; +</pre></td> +<td>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.</td> + </tr> + <tr> +<td><pre> +function Is_Ambiguous + (Container : in Parse_Graph) + return Boolean; +</pre></td> +<td>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.</td> + </tr> + <tr> +<td><pre> +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); +</pre></td> +<td>Gives the parent tokens of all ambiguities in the graph.</td> + </tr> + <tr> +<td><pre> +function Isomorphic + (Left, Right : in Parse_Graph) + return Boolean +with Pre => Left.Has_Root and Right.Has_Root; +</pre></td> +<td>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.</td> + </tr> + <tr> +<td><pre> +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); +</pre></td> +<td>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.</td> + </tr> + </table> + + + </body> +</html> + |