Discussion

I presented an abstract specification of a head-corner parser for headed and lexicalized TAGs. The important properties of the parser are that processing proceeds in a bidirectional fashion in two senses: the string is not derived from left to right, but rather from heads outward both to the left and to the right. Furthermore the parser employs both bottom-up and top-down information. For this reason it fully uses the benefits of lexicalized grammars.

The parser has some similarities with the bidirectional parser of [3]. They present a bidirectional parser in which analyses are also discovered from the anchor of a lexicalized tree outward.

An important difference with their approach lies within the way in which auxiliary trees are handled. In our case, an auxiliary tree is traversed from the (known) foot node, rather than from the anchor of the auxiliary tree. This is reflected by our requirement that the head-corner of an auxiliary tree is its foot node. In the parser of [3] the parser proceeds from the lexical anchor of an auxiliary tree. This implies that there is some non-determinism in the case of adjunction: the parser does not take into account the possible analysis of a foot node and jumps over a substring possibly dominated by the foot node.

Furthermore, the bidirectional parser of [3] proceeds bottom-up from the anchor of an elementary tree upward. However, subtrees of an elementary tree that do not lie on this path are recognized in a top-down fashion. In the head-corner parser such subtrees are also processed bottom-up, starting from the head-corner of this subtree.

Finally note that the head-corner parser deals with substitution, whereas [3] do not consider the possibility of substitution.