In parsers that proceed from the left the parse predicate typically consists of a category to be parsed, a given start position and an unknown end position. In a bidirectional parser we are given a category, and two pairs of positions: a given pair of indices that indicate the extreme positions between which the category has to be found, and a pair of indices that indicates the exact position of the category once it has been found. Depending on whether we are parsing to the left or to the right, one of the extreme positions matches the actual position.
Suppose that we are given the grammar in figure 2, and the
sentence to parse is:
(1) Who did john say mary saw?
The first goal of the parser is to parse a sentence (assume the top-category
is s)
from position 0 to 6 within the extreme positions 0 to 6. In order to
parse such a sentence, the head-driven parser proceeds as follows. It
predicts an initial tree whose root node matches the top
category and whose anchor occurs somewhere between position 0 and 6.
In the current grammar the initial tree
is the only
candidate.
The head-corner parser then proceeds by a head-driven
bottom-up walk through this initial tree (starting from the
head-corner, i.e. the anchor) by trying to recognize the other parts
of the initial tree, and by applying adjunctions
non-deterministically.
In the current example our goal is to connect the head-corner
saw to the top category s by climbing up in .
During the connect phase there are three possibilities. Firstly, once we arrive at the root of the tree we are done. Secondly, in order to move upward in the tree, we are to recognize the sisters left and right of the current node (the current head). Thirdly, it may also be the case that at the current head node an adjunction occurs. In that case we have to climb from the foot node of the auxiliary tree up to the root node of the auxiliary tree, after which we proceed by climbing up from the node at which this adjunction occurred.
In the current example we proceed by climbing up from saw to the dominating v and vp nodes by two instantiations of the second possibility. As both these nodes are unary branching nothing interesting happens. At this point we want to climb up to the s node, but in order to reach that node we have to recognize a substituted np. This leads to a recursive call of the parse predicate: we have to parse a np within the extreme positions 0 and 5, ending in 5.
In general there are three possibilities to consider in the case of
such an embedded parse-goal. In the example the subtree to be
recognized simply consists of a substitution node with category np. In general such a subtree may be complex. Its head-corner is
either a substitution node, a terminal symbol, or an empty element.
In each case the parser first recognizes this head-corner (recursively
in the first case, and trivially in the second and third case) after
which the parser proceeds to connect this embedded head-corner up to
the root of the subtree. In the example, the subtree to be recognized
consists solely of a substitution node. The head-corner of this
subtree therefore is this substitution node. The path from the
head-corner upward to the root is the empty path. Therefore the parser
proceeds by predicting an initial tree of which the root matches np, after which the anchor of that initial tree must be connected to
that root. In this case the parser predicts the initial tree
and climbs from its anchor to its root without any
adjunctions or substitutions. After the recognition of the
substitution node np of
, we now are at the embedded
s node of
covering positions 4 to 6.
Again we climb up one level, to the sbar node. In order to get
there we need to parse an empty c. This provides an example of
the second possibility of an embedded parse goal. This succeeds
immediately (in general there might be adjunctions at this empty node,
but not in this example). Now we are at node sbar of .
If we were to climb up at this point the tree walk would fail to find
a wh category ending in position 4. However, another
possibility at the current node is to adjoin auxiliary tree
.
If an auxiliary tree
is adjoined at a node
this implies that we
proceed our tree walk from the foot node of
up to
the root node of
after which we return to
.
In the example we are to climb from the foot node of
up to
its root node. We have covered position 4 to 6 and our extreme
positions are 0 and 6. In order to climb up one level we have to parse
the subtree rooted by vp between 0 and 4 and ending in 4.
We start with the head-corner, the terminal symbol say,
after which we have to climb up from this head-corner with positions 3
and 4 up to the vp again. As all this succeeds, we can climb up
to the vp node dominating the foot node, now covering positions
3 to 6. Proceeding in this way we parse `john' as a noun-phrase and
consume the terminal symbol `did' after which we climb up to the root
of
, from 1 to 6. Control then returns to the initial tree in
which the auxiliary was adjoined. In
we are at node sbar from 1 to 6, and now we can climb up successfully because indeed
we find a wh from position 0 to 6. The sentence thus is
well-formed. This completes the example.