summaryrefslogtreecommitdiff
path: root/doc/parse_graph_op.html
diff options
context:
space:
mode:
Diffstat (limited to 'doc/parse_graph_op.html')
-rw-r--r--doc/parse_graph_op.html424
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>
+