12 - Path expressions and tree-walking automata

Summary

While in Chapter 5 we defined patterns as an approach to subtree extraction, in this chapter we introduce an alternative approach called path expressions. While patterns use structural constraints for matching subtrees, path expressions use “navigation,” which specifies a sequence of movements on the tree and makes checks on the visited nodes. In practice, path expressions tend to be more concise since they do not require conditions to be specified for the nodes not on the path. In theory, however, path expressions are strictly less expressive (i.e., they cannot express all regular tree languages) unless sufficient extensions are made. In this chapter we first review path expressions used in actual XML processing and then consider a refinement called caterpillar expressions. After this, we study the corresponding automata formalism, called tree-walking automata, and compare their expressiveness with tree automata.

Path expressions

Although there are various styles of path expression, the basic idea is to find a node to which there is a “path” from the “current” node obeying the given path expression. When multiple such nodes are found, usually all are returned.

The main differences between the styles lie in which paths are allowed. A path is, roughly, a sequence consisting of either movements between or tests on nodes. In each movement we specify in which direction to go; we call this axis.