Next: Output Generation
Up: The definition of a
Previous: Node names, variable instantiation,
The process of matching lhs and inp can be seen as a recursive
procedure for matching trees, starting at their roots and proceeding in a
topdown style along with their subtrees.
In the explanation of this process that
follows we have used 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 the same
as 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
list_{lhs}=[lhs_{1}, lhs_{2}, ..., lhs_{l}] of nodes of lhs
and a list
list_{inp}=[inp_{1}, inp_{2}, ..., inp_{i}] of nodes of inp,
we define a mapping from
list_{lhs} to
list_{inp} to be a function
Mapping,
that for each element of
list_{lhs} assigns a list of elements of
list_{inp}, defined by the following condition:
,
i.e., the elements of
list_{inp} are split into sublists and assigned in
order of appearance in the list to the elements of
list_{lhs}.
We say that a mapping is a valid mapping if for all j,
(where l is the length of
list_{lhs}), the following restrictions apply:
 1.
 if lhs_{j} is a constant node, then
Mapping(lhs_{j}) must have a
single element, say,
rhs_{g(j)}, and the two nodes must have the same
name and agree on the markers (foot, substitution, head and NA), i.e.,
if lhs_{j} is NA, then
rhs_{g(j)} must be NA,
if lhs_{j} has no markers, then
rhs_{g(j)} must have no markers, etc.
 2.
 if lhs_{j} is a type variable node, then
Mapping(lhs_{j}) must have a
single element, say,
rhs_{g(j)}, and
rhs_{g(j)} must be
markercompatible and
typecompatible with lhs_{j}.
rhs_{g(j)} is
markercompatible with lhs_{j} if any marker
(foot, substitution, head and NA) present in lhs_{j} is also
present in
rhs_{g(j)}^{25.4}.
rhs_{g(j)} is typecompatible with lhs_{j}
if there is at least one of the alternative
type specifiers for the typed variable that satisfies
the conditions below.

rhs_{g(j)} has the stem defined in the type specifier.
 if the type specifier doesn't have subscript, then
rhs_{g(j)} must have no subscript.
 if the type specifier has a subscript different of `?', then
rhs_{g(j)} must have the same subscript as in the type specifier
^{25.5}.
 3.
 if lhs_{j} is a nontyped variable node, then there's actually no
requirement:
Mapping(lhs_{j}) 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.
Function Match (
list_{lhs},
list_{rhs})
Let MAPPINGS be the list of all valid mappings from
list_{lhs} to
list_{rhs}
Make
For each mapping
do:
Make
For each j,
,
where
l=length(list_{lhs}), do:
if lhs_{j} is a constant node, then
let
children_{lhs} be the list of children of lhs_{j}
lhr_{g(j)} be the single element in
Mapping(lhs_{j})
children_{rhs} be the list of children of
lhr_{g(j)}
Make
Match
if lhs_{j} is a typed variable node, then
let
children_{lhs} be the list of children of lhs_{j}
lhr_{g(j)} be the single element in
Mapping(lhs_{j})
children_{rhs} be the list of children of
lhr_{g(j)}
Make
Match
if lhs_{j} is a nontyped variable node, then
let
children_{lhs} be the list of children of lhs_{j}
sl be the number of nodes in
children_{lhs}
DESC_{s} be the set of ssize lists given by:
for every
,
dr_{k} is a descendant
of some node in
^{25.6}
for every
,
dr_{l} is to the right of dr_{k1}^{25.7}.
For every list
do:
Let TreeMaterial be the list of subtrees dominated
by the nodes in
Mapping(lhs_{j}), but, with the
subtrees dominated by the nodes in DESC_{s}
cut out from these trees
Make
Match
Make
Return MATCHES
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: Output Generation
Up: The definition of a
Previous: Node names, variable instantiation,
XTAG Project
19980914