Structural Matching

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 top-down 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₁, lhs₂, ..., lhs_l] of nodes of lhs and a list list_inp=[inp₁, inp₂, ..., 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 marker-compatible and type-compatible with lhs_j.
rhs_g(j) is marker-compatible 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 type-compatible 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 non-typed 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 (

listlhs, 

listrhs)
				 Let MAPPINGS be the list of all valid mappings from 

listlhs to         

listrhs 
				 Make 


				 For each mapping 


do:
						 Make 


						 For each j, 

,
where 

l=length(listlhs), do:
								 if lhsj is a constant node, then
										 let 		

childrenlhs be the list of children of lhsj 
										 		

lhrg(j) be the single element in 

Mapping(lhsj) 
										 		

childrenrhs be the list of children of 

lhrg(j) 
										 Make 


																		 


Match


								 if lhsj is a typed variable node, then
										 let 		

childrenlhs be the list of children of lhsj 
										 		

lhrg(j) be the single element in 

Mapping(lhsj) 
										 		

childrenrhs be the list of children of 

lhrg(j) 
										 Make 


																		 


Match


								 if lhsj is a non-typed variable node, then
										 let 		

childrenlhs be the list of children of lhsj 
										 		 sl be the number of nodes in 

childrenlhs 
												 DESCs be the set of s-size lists given by:
																 


																				 for every 

,
drk is a descendant
																								 of                         some node in 

25.6
																				 for every 

,
drl is to the right of                         drk-125.7.
												 For every list 


do:
														 Let Tree-Material be the list of subtrees dominated
																		 by the nodes in 

Mapping(lhsj), but, with the
																		 subtrees dominated by the nodes in DESCs 
																		 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).