The way in which adjunction and substitution is defined in previous subsections give rise to spurious ambiguities. For example, given two auxiliary trees and and a derived tree , the parser derives the application of and to twice, corresponding to the applications (()) and (()). But the results of these derivations are clearly completely identical.

As an example, consider the following case in which , and are as in figure 4.18.

The application
(()) gives rise to two possible
derived trees, depending on which node with category `n`, is chosen
for adjunction (see figure 4.19 for an illustration). Clearly, the
application
(()) gives the same two results. The
parser thus delivers four results, where only two results are
desirable.

The first two trees respectively corresponds to () and (). Depending on the adjunction node, these two trees both can be expanded in two ways, by the adjunction of the other auxiliary tree, resulting in two trees corresponding to (()), and two trees corresponding to (()). Four results are derived by the parser, where only two should be derived.

Another spurious ambiguity arises when a tree is substituted in another tree, and afterwards adjunction in this tree is possible. The parser will prove two alternative derivations. The first derivation corresponds to the case in which the auxiliary tree is first adjoined in the derived tree, which then is substituted in the main tree. The second derivation corresponds to the case where the derived tree is substituted in the main tree; the auxiliary tree is afterwards adjoined (deep down) in this main tree.

It is straightforward to solve these problems by the following two principles. Firstly, once a tree is substituted in another tree this sub-tree is regarded `completed'. This means that no adjunctions take place in this tree. Similarly, if an auxiliary tree is adjoined at some node in a derived tree, then the sub-tree dominated by the foot node (in the result of the adjunction) is `completed' as well, and no further adjunctions under this foot node are possible. In the illustration I mark such `completed' sub-trees with the `#' marker.

The example given above is now derived only twice as follows. Firstly,
the application
() gives rise to a derived tree in
which the embedded *n* node is marked completed. For that reason
applying
to it only gives rise to one possibility, because
the marker on the node `n _{1}` prevents adjunction at

In this way, trees are constructed in a bottom up fashion. Once you adjoin at a given node, then everything under (the bottom part) of this node is completed.

The prevention of spurious ambiguity is easily implemented using the
attribute
*mrk* in the data structure representing trees. The node
in a tree representing a substitution node will be marked `completed'.
Note that this marker remains after substitution. Similarly, the
marker of a node representing a foot node will be marked `completed'.
This changes the representation of initial and auxiliary trees.
The adjunction predicate, furthermore, is defined in such a way that
it may only penetrate nodes, which are not marked `completed'. Note
that in the definition of
*adjoin* this is already achieved.

1998-09-30