An example

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 $\alpha_{4}^{}$ 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 $\alpha_{4}^{}$.

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 $\alpha_{3}^{}$ and climbs from its anchor to its root without any adjunctions or substitutions. After the recognition of the substitution node np of $\alpha_{4}^{}$, we now are at the embedded s node of $\alpha_{4}^{}$ 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 $\alpha_{4}^{}$. 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 $\beta_{1}^{}$. If an auxiliary tree $\beta$ is adjoined at a node $\eta$ this implies that we proceed our tree walk from the foot node of $\beta$ up to the root node of $\beta$ after which we return to $\eta$.

In the example we are to climb from the foot node of $\beta_{1}^{}$ 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 $\beta_{1}^{}$, from 1 to 6. Control then returns to the initial tree in which the auxiliary was adjoined. In $\alpha_{4}^{}$ 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.