The MatchTree
structure provides a treestructured representation
of the result of a successful regular expression match. The tree structure
corresponds to the nesting of groups
in the regular expression.
Synopsis
signature MATCH_TREE
structure MatchTree : MATCH_TREE
Interface
datatype 'a match_tree = Match of 'a * 'a match_tree list
val root : 'a match_tree > 'a
val nth : ('a match_tree * int) > 'a (* raises Subscript *)
val map : ('a > 'b) > 'a match_tree > 'b match_tree
val app : ('a > unit) > 'a match_tree > unit
val foldl : ('a * 'b > 'b) > 'b > 'a match_tree > 'b
val foldr : ('a * 'b > 'b) > 'b > 'a match_tree > 'b
val find : ('a > bool) > 'a match_tree > 'a option
val num : 'a match_tree > int
Description
datatype 'a match_tree = Match of 'a * 'a match_tree list

The representation of the results of a nested grouping of regular expressions. The type variable
'a
is typically instantiated to information about the particular range of the source that the node covers. For example, it might be the pair of the start position and length of the match. val root : 'a match_tree > 'a

root mt
returns the information about the root (outermost) match in the tree. val nth : ('a match_tree * int) > 'a (* raises Subscript *)

nth (mt, i)
returns the information about thei
'th match in the tree, where matches are labeled in preorder starting with0
for the root. This function raises theSubscript
exception ifi < 0
or there are fewer thani1
nodes in the tree. val map : ('a > 'b) > 'a match_tree > 'b match_tree

map f mt
returns the result of mapping the functionf
overmt
. For example, this function can be used to convert a matchtree of position information to a tree of strings. The function is applied to the tree in preorder. val app : ('a > unit) > 'a match_tree > unit

app f mt
applies the given function to the nodes in the tree in preorder. val foldl : ('a * 'b > 'b) > 'b > 'a match_tree > 'b

foldl f init mt
folds the functionf
overmt
in lefttoright preorder usinginit
as the initial value. val foldr : ('a * 'b > 'b) > 'b > 'a match_tree > 'b

foldr f init mt
folds the functionf
overmt
in righttoleft postorder usinginit
as the initial value. val find : ('a > bool) > 'a match_tree > 'a option

find pred mt
returnsSOME info
whereinfo
is the first information that satisfiespred
in a preorder traversal of the tree. It returnsNONE
if there is no match information that satisfiespred
. val num : 'a match_tree > int

num mt
returns the number of submatches in the tree; i.e., the number of nodes not counting the root.