Next: Output Generation
Up: The definition of a
Previous: Node names, variable instantiation,
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:
-
inpg(j) has the stem defined in the type specifier.
- if the type specifier doesn't have a subscript, then
inpg(j) must have no subscript.
- if the type specifier has a subscript different from `?', then
inpg(j) must have the same subscript as in the type specifier
27.5.
- 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.
- {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: Output Generation
Up: The definition of a
Previous: Node names, variable instantiation,
XTAG Project
http://www.cis.upenn.edu/~xtag