next up previous contents
Next: Output Generation Up: The definition of a Previous: Node names, variable instantiation,

Structural Matching

The process of matching lhs with inp can be seen as a recursive procedure for matching trees, starting at their roots and proceeding in a top-down style along with their subtrees. In the explanation of this process that follows we use the term lhs not only to refer to the whole tree that contains the pattern but to any of its subtrees that is being considered in a given recursive step. The same applies to inp. By now we ignore feature equations, which will be accounted for in the next subsection. The process described below returns at the end the set of matches (where an empty set means failure). We first give one auxiliary definition, of valid Mapping, and one recursive function Match, that matches lists of trees instead of trees, and then define the process of matching two trees as a special case of call to Match. Given a list listlhs=[lhs1, lhs2, ..., lhsl] of nodes of lhs and a list listinp=[inp1, inp2, ..., inpi] of nodes of inp, we define a mapping from listlhs to listinp to be a function Mapping, that for each element of listlhs assigns a list of elements of listinp, defined by the following condition:


That is, the elements of listinp are split into sublists and assigned in order of appearance in the list to the elements of listlhs. We say that a mapping is a valid mapping if for all j, (where l is the length of listlhs), the following restrictions apply:
1.
if lhsj is a constant node, then Mapping(lhsj) must have a single element, say, inpg(j), and the two nodes must have the same name and agree on the markers (foot, substitution, head and NA), i.e., if lhsj is NA, then inpg(j) must be NA, if lhsj has no markers, then inpg(j) must have no markers, etc.
2.
if lhsj is a typed variable node, then Mapping(lhsj) must have a single element, say, inpg(j), and inpg(j) must be marker-compatible and type-compatible with lhsj.
inpg(j) is marker-compatible with lhsj if any marker (foot, substitution, head and NA) present in lhsj is also present in inpg(j)27.4.
inpg(j) is type-compatible with lhsj if at least one of the alternative type specifiers for the typed variable lhsj satisfies the conditions below:
3.
if lhsj is a non-typed variable node, then there is no requirement: Mapping(lhsj) may have any length and even be empty.
The following algorithm, Match, takes as input a list of nodes of lhs and a list of nodes of inp, and returns the set of possible matches generated in the attempt of match this two lists. If the result is an empty set, this means that the matching failed.

ps/metarulealgo.eps.gif

{Metarule matching algorithm

 

Finally we can define the process of structurally matching lhs to inp as the evaluation of Match([root(lhs)], [root(inp)]. If the result is an empty set, the matching failed, otherwise the resulting set is the set of possible matches that will be used for generating the new trees (after being pruned by the feature equation matching).


next up previous contents
Next: Output Generation Up: The definition of a Previous: Node names, variable instantiation,
XTAG Project
http://www.cis.upenn.edu/~xtag