fxgrep - The Functional XML Querying Tool

-----------------

Contents

0 What is fxgrep?
0 The Processing Model of fxgrep
0 The Pattern Language of fxgrep
0 The Grammar Formalism of fxgrep
0 Text Patterns
0 fxgrep Options
0 fxgrep's Graphical User Interface

-----------------

The Processing Model of fxgrep

fxgrep parses the input document according to the given parsing options and constructs a document forest from it. This forest is constructed from nodes corresponding to the logical structure of the document:

There are three kinds of nodes: text nodes, PI nodes and element nodes:

A text node represents one or more adjacent pieces of character data. Two pieces of character data are considered adjacent if they are in the content of the same element and there is no other text, processing instruction or element between them. Note that this ignores comments: Two pieces of text separated by a comment are merged into a single text node. Moreover, the physical representation of the character data is irrelevant: A text node has no information about whether a piece of text was present literally in the XML source, or made up from entity references and CDATA sections.

A PI node represents a processing instruction and is annotated with the target name of the processing instruction. It has a single child: a text node giving the text of the processing instruction.

An element node represents an element and is annotated with the element type and the attributes specified for the element, including the defaulted ones. Each attribute value is given by the normalized text of the attribute value literal specified in the start-tag or in the attribute declaration. The children of an element node are a sequence of nodes constructed from the content of the element, in the same order as in the XML document source. Keep in mind that comments are ignored and adjacent pieces of text are merged into a single text node. In order to keep the representation independent from validation, white space in element content is represented by a text node.

The document forest is a sequence of nodes. It consists of a single element node representing the document element, preceded or followed by a processing instruction node for each processing instruction which precedes or follows it in the XML document, including those processing instructions that occur within the DTD.

For a node in the forest, the other children of its parent node are called its siblings; those which precede it are the left siblings and those that follow the right siblings. A descendant of a node is either a child of the node or a descendant of one of its children. Similarly, an ancestor of a node is either its parent or an ancestor of its parent. A node together with its descendants form the subtree rooted at that node. For brevity, when the context is clear, we sometimes identify a node with the element it represents or with the subtree rooted at that node.

Normally, fxgrep implements a query by consecutive runs of two forest automata, the first traversing from right to left and the second traversing from left to right. The second pass reports all matches of the query in document order.

If the query is simple enough, a single run of an automaton suffices. In this case fxgrep offers two processing modes: Either the automaton is run on the constructed document forest (default), or it is run during parsing, without explicitly constructing the forest. The second method might be slower because it requires demand-driven construction of only those parts of the document forest that might match the query, but it has the advantage of avoiding in-memory construction of the possibly huge document forest. This behavior is controlled by command-line options.

-----------------