Next: Unification of bottom and Up: Head-driven parsing for TAGs Previous: String concatenation

## Spurious ambiguity

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 n1 prevents adjunction at n1, and hence only adjunction at node n2 is possible (see figure 4.20 for illustration). The derivation (()) produces the other possibility.

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.

Next: Unification of bottom and Up: Head-driven parsing for TAGs Previous: String concatenation
Noord G.J.M. van
1998-09-30