next up previous contents
Next: Head-driven parsing for TAGs Up: Head-corner Parsing Previous: A sample grammar


The head corner parser

This section describes the head-driven parsing algorithm for the type of grammars described above. The parser is a generalization of Kay's head-driven parser, which in turn is a modification of a left-corner parser. The parser, which may be called a `head-corner' parser,4.1 proceeds in a bottom-up way. Because the parser proceeds from head to head it is easy to use powerful top-down predictions based on the usual head feature percolations, and subcategorization requirements that heads impose upon their arguments. In fact, the motivation for this approach to parsing discontinuous constituency is already hinted at by Mark Johnson [38]:

My own feeling is that the approach that would bring the most immediate results would be to adopt some of the ``head driven'' aspects of Pollard's (1984) Head Grammars. In his conception, heads contain as lexical information a list of the items they subcategorize for. This strongly suggests that one should parse according to a ``head-first'' strategy: when one parses a sentence, one looks for its verb first, and then, based on the lexical form of the verb, one looks for the other arguments in the clause. Not only would such an approach be easy to implement in a DCG framework, but given the empirical fact that the nature of argument NP's in a clause is strongly determined by that clause's verb, it seems a very reasonable thing to do.
It is clear from the context that Johnson believes this strategy especially useful for non-configurational languages.

In left-corner parsers [55] the first step of the algorithm is to select the left-most word of a phrase. The parser then proceeds by proving that this word indeed can be the left-corner of the phrase. It does so by selecting a rule of which the leftmost daughter unifies with the category of the word. It then parses other daughters of the rule recursively and then continues by connecting the mother category of that rule upwards, recursively. An illustration of the left-corner parser is provided in figure 4.14. The parser selects the left-most element of the string (1), and proves that this element is the left-corner of the goal. To this end, a rule is selected of which this lexical entry is the left-most daughter. The other daughters of the rule are parsed recursively. The result is a slightly larger left-corner (2). This process repeats itself until a left-corner is constructed which dominates the whole string (3). The string is recognized from left to right.

Figure 4.14: The left-corner parser.
\begin{figure}
\par\begin{picture}
(120,140)(-100,0)
\par\multiput(0,0)(5,10){12...
...{\line(-1,2){50}}
\put(120,0){\line(-1,2){60}}
\end{picture}\par\par\end{figure}

A head-driven algorithm can be defined analogously ([46]), if we replace the notion `left' with `head'. Thus, to prove a given goal, the parser selects a lexical entry (the head). Then the parser continues to prove that this lexical entry indeed is the head of the goal, by selecting a rule of which this lexical entry can be head. The other daughters of the rule are parsed recursively, and the result constitutes a slightly larger head. This process can be applied iteratively, until the head dominates all words in the string. This is illustrated in figure 4.15.

The parser selects the head of the string (1), and proves that this element is the head-corner of the goal. To this end, a rule is selected of which this lexical entry is the head daughter. The other daughters of the rule are parsed recursively. The result is a slightly larger head-corner (2). This process repeats itself until a head-corner is constructed which dominates the whole string (3). The string is recognized bidirectionally.

Figure 4.15: The head-corner parser for concatenative grammars.
\begin{figure}
\par\begin{picture}
(120,140)(-100,0)
\par\multiput(0,0)(5,10){12...
...{\line(1,0){120}}
\put(120,0){\line(-1,2){60}}
\end{picture}\par\par\end{figure}

A head-corner chart-parser for context-free grammars is defined in [88]. They show that the worst-case complexity of the algorithm is the same as for conventional context-free parsing algorithms such as [19]. The method is comparable to that of [79,80].

The head-driven variant of the left-corner algorithm can be adapted to the class of grammars under consideration. Again, the first step of the algorithm consists of the prediction step: which lexical entry is the head corner of the phrase? The first thing to note is that the words introduced by this lexical entry should be part of the input string, because of the non-erasure requirement. Therefore we use the bag of words as a `guide' [18] as in a left-corner parser, but we change the way in which lexical entries `consume the guide'. For the moment I assume that the bag of words is simply represented by the string, but I introduce a better data-structure for bags later in this chapter. The predicates guide and $\mbox{\it consume\_guide}$ are defined as:

\pr\pred
\head{\mbox{\it guide}(\mbox{\rm String},\mbox{\rm String},\langle\rang...
...\body{ \mbox{\it del}(\mbox{\rm El},\mbox{\rm T},\mbox{\rm T}_{2}).}
\epred\epr

To instantiate the guide properly, I define the predicate $\mbox{\it start\_parse}/2$ as follows:

\pr\pred
\head{\mbox{\it start\_parse}(\mbox{\rm String},\mbox{\rm Sign}) \mbox{...
...uide}),}
\body{\mbox{\it yield}(\mbox{\rm Sign},\mbox{\rm String}).}
\epred\epr

The interesting predicate is the parse predicate. This predicate predicts, for a given goal, its possible head-corner, and then shows that this predicted head-corner, indeed is the head-corner of the goal. As we discussed earlier, in most linguistic theories, it is assumed that certain features are shared between the mother and the head. I assume that the predicate head/2 defines these feature percolations; for the grammar of the foregoing section this predicate simply is defined as:

\pr\pred
\head{\mbox{\it head}(\avm{ \mbox{\it syn}: \mbox{\rm Syn}},\avm{ \mbox{\it syn}: \mbox{\rm Syn}}).}
\epred\epr
Because of the definition of `head corner', these features will also be shared between a node and its head corner; hence we can use this definition to restrict lexical lookup by top-down prediction. 4.2 The first step in the algorithm is defined as:

\pr\pred
\head{\mbox{\it parse}(\mbox{\rm Goal},\mbox{\rm P}_{0},\mbox{\rm P}) \...
...{\mbox{\it parse\_ds}(\mbox{\rm T},\mbox{\rm P}_{1},\mbox{\rm P}).}
\epred
\epr
The relation $\mbox{\it parse\_ds}$ simply calls the parse predicate, for each element of a list of daughters. The second clause of the parse predicate is applicable, if one of these daughters is the extra relation call -- written between {,}.

The predicates $\mbox{\it predict\_ncr}$ predicts for a given goal, a possible head-corner. It is defined as follows:

\pr\pred
\head{\mbox{\it predict\_ncr}(\mbox{\rm Goal},\mbox{\rm Head},\mbox{\rm...
...t consume\_guide}(\mbox{\rm Words}, \mbox{\rm P}_{0},\mbox{\rm P}).}
\epred\epr
Instead of selecting the first word from the current input string, the parser selects a lexical entry dominating a subbag of the words occurring in the input string, provided this lexical entry can be the head-corner of the current goal.

The second step of the algorithm, the $\mbox{\it head\_corner}$ part, is identical to the $\mbox{\it left\_corner}$ part of the left-corner parser, but instead of selecting the leftmost daughter of a rule the head-corner parser selects the head of a rule.

\pr\pred
\head{\mbox{\it head\_corner}(\mbox{\rm X},\mbox{\rm X},\mbox{\rm P},\m...
...t consume\_guide}(\mbox{\rm Words},\mbox{\rm P}_{0},\mbox{\rm P}).}
\epred
\epr

Example.

To parse the sentence `dat jan ontwaakt', the head corner parser will proceed as indicated in figure 4.16. Each of the steps will now be clarified as follows. The integers associated with the arrows indicate the order of the steps of the parsing process. Prediction steps are indicated with a framed integer, `head_corner' steps are indicated with a bold face integer, and recursive parse steps are indicated with a slanted integer. The nodes represent (some of) the information available at the moment this step is performed. The left-most daughter of each local tree corresponds to the head daughter.

Figure 4.16: Trace of the parse `dat jan ontwaakt'.
\begin{figure}
\setlength{\unitlength}{1pt}\begin{center}
\leavevmode
\unitlengt...
...put(257,315){\fbox{7}}\put(272,330){\vector(0,-1){35}}
\end{picture}\end{figure}

After the construction of the guide, in the predicate $\mbox{\it start\_parse}$, the first call to parse is:

\query{\mbox{\it parse}(\avm{ \mbox{\it syn}: \mbox{\rm comp}\\
\mbox{\it sc}:...
...n,ontwaakt \rangle } ,\langle dat,jan,ontwaakt\rangle,\langle\rangle).}
\equery
This is the root node in figure 4.16.

The prediction step (1) selects the lexical entry `dat' (recall that lexical entries are non-chain-rules with an empty list of daughters), because its syntactic features are the same as the syntactic features of this goal, and because the word occurs in the input string. The next goal is to show that this lexical entry is the head corner of the top goal; furthermore the words that still have to be covered are now $ \langle$jan, ontwaakt$ \rangle$. The $\mbox{\it head\_corner}$ clause looks, essentially, as follows (step 2):

\query{\mbox{\it head\_corner}(
\avm{ \mbox{\it syn}: \mbox{\rm comp}\\
\mbox...
...tem{\langle \mbox{\rm jan},\mbox{\rm ontwaakt}\rangle,\langle\rangle).}
\equery
The hypothesized head-corner, the lexical entry `dat', has to be matched with the head of a rule. Notice that `dat' subcategorizes for a sign with syntactic category V, hence the next goal (3) is to parse the V; the guide is instantiated as the bag `jan, ontwaakt':

\query{\mbox{\it parse}(\avm{ \mbox{\it syn}: \mbox{\rm v}\\
\mbox{\it sc}: \l...
...it rule}: \mbox{\rm right}},\langle jan,ontwaakt\rangle,\mbox{\rm P}).
}\equery
For this goal, the prediction step selects the word ontwaakt (4). Next, the word ontwaakt has to be shown to be the head corner of the V goal, by the $\mbox{\it head\_corner}$ predicate (5):

\query{\mbox{\it head\_corner}(\avm{ \mbox{\it syn}: \mbox{\rm v}\\
\mbox{\it ...
...rule}: \mbox{\rm right}},\langle \mbox{\rm jan}\rangle,\mbox{\rm P}). }
\equery
In order to prove this predicate, the next parse goal consists in parsing a NP (for which ontwaakt subcategorizes, step 6); the guide is the bag consisting of the element jan. This goal succeeds: predict a possible head corner (7), the lexical entry `jan', which is a trivial head corner of the NP (8). After the successful parse of the NP, this NP is combined with the V, with the cp predicate. Note that the verb selected an NP with rule-feature `left', and hence the phonology of the NP is appended to the left of `ontwaakt'. As the verb does not select any other elements, the resulting verb phrase is indeed a possible head-corner of the parse goal above (9), instantiating this goal to:

\query{\mbox{\it parse}(\avm{ \mbox{\it syn}: \mbox{\rm v}\\
\mbox{\it sc}: \l...
...t}},\langle \mbox{\rm jan},\mbox{\rm ontwaakt}\rangle,\langle\rangle).}
\equery
and therefore we now have found the V for which dat subcategorizes. The next task is to combine this verb phrase with the lexical entry `dat', by means of the `cp' predicate. The verb phrase is selected by `dat', with rule feature `right'. Therefore the phonology of the verb phrase is appended to the right of the phonology of this complementizer. The next goal (10) is to connect the complementizer with an empty subcat list up to the top-goal, with trivial success. Hence the first call to parse will succeed, yielding:

\query{\mbox{\it parse}(\avm{ \mbox{\it syn}: \mbox{\rm comp}\\
\mbox{\it sc}:...
...x{\rm dat},\mbox{\rm jan},\mbox{\rm ontwaakt}\rangle,\langle\rangle).
}\equery

A slightly more complex example is shown in figure 4.17, for the sentence

\begin{exam}
Hoort Arie Bob sla bestellen?\\
Hears Arie Bob salad order\\
{\it Does Arie hear that Bob orders salad?}
\end{exam}

Figure 4.17: Parsing `Hoort Arie Bob sla bestellen'
\begin{figure}
\setlength{\unitlength}{1pt}\begin{center}
\leavevmode
\unitlengt...
...ut(285,270){\fbox{19}}\put(305,290){\vector(0,-1){35}}
\end{picture}\end{figure}




next up previous contents
Next: Head-driven parsing for TAGs Up: Head-corner Parsing Previous: A sample grammar
Noord G.J.M. van
1998-09-30