next up previous contents
Next: Omkeerbaar automatisch vertalen Up: Omkeerbaarheid in natuurlijke-taalverwerking Previous: `Semantic-head-driven' generatie

`Head-corner' parseren

In hoofdstuk 4 bespreek ik een aantal voorstellen voor het combineren van zinsdelen die uitgaan boven concatenatie, zoals bijvoorbeeld Pollard's `head-wrapping' operaties binnen een GPSG; Joshi's Tree Adjoining Grammars, Reape's incorporatie van `sequence-union constraints' binnen een HPSG, of `liberation' binnen een categoriale grammatica.

Ik definieer een parseerprocedure, `head-corner parsing' genaamd, voor een klasse van grammatica's waarbij zinsdelen geconstrueerd worden op een `non-erasing' en lineaire manier. Een grammaticaregel is lineair wanneer de regel slechts een constant aantal terminale symbolen introduceert. Een regel is `non-erasing' wanneer de terminale symbolen geassocieerd met de dochterknopen een deelverzameling is van de terminale symbolen geassocieerd met de moederknoop. De genoemde voorstellen behoren tot deze klasse van grammatica's. De head-corner parser is dus bruikbaar voor een verzameling grammatica's die de concatenatieve grammatica's omvat.

Head-corner parsing is een parseertechniek die zowel hoofdgestuurd als bidirectioneel te werk gaat (niet van links naar rechts, noch top-down of bottom-up). Omdat de parser hoofdgestuurd te werk gaat is het mogelijk de gebruikelijke percolatie van eigenschappen tussen de moederknoop en het hoofd uit te buiten, om zodoende de doelgerichtheid van de parser te vergroten. Daarnaast gebruikt deze parseervolgorde het feit dat het hoofd normaliter bepaalt uit welke andere onderdelen een zinsdeel kan bestaan. Als je weet wat het hoofd van een zinsdeel is, weet je dus welke andere onderdelen je nog moet tegenkomen.

Om de head-corner parser bruikbaar te laten zijn voor lineaire en `non-erasing' grammatica's wordt de invoerzin als een `gids' gebruikt tijdens het parseren. Echter, de manier waarop elementen uit de gids geconsumeerd worden is niet van links naar rechts, maar onbepaald. De gids is dus geen stapel maar een verzameling.

Om te begrijpen hoe de parser werkt nemen we aan dat regels als volgt gedefinieerd zijn. Alle terminale symbolen worden geintroduceerd op een regel zonder dochter (`lexical entry'), en elke regel met dochters heeft ook een hoofd (in hoofdstuk 4 worden deze aannames niet gemaakt). Een regel met een hoofd wordt gerepresenteerd als:

\begin{displaymath}\mbox{\it cr}(\mbox{\rm Hoofd},\mbox{\rm Moeder},\langle \mbox{\rm D}_{1} \dots \mbox{\rm D}_{n}\rangle) \mbox{\tt :-} \phi.
\end{displaymath}
Lexicale elementen worden gerepresenteerd als:

\begin{displaymath}
\mbox{\it lex}(\mbox{\rm Woord},\mbox{\rm Moeder})\mbox{\tt :-} \phi.
\end{displaymath}
Daarnaast definieert het predikaat hoofd/2 de informatie die hoofden gemeen hebben met hun moederknoop. Een simpele versie van de head-corner parser kan nu gedefinieerd worden zoals in figuur 6.2.

Figure 6.2: Een eenvoudige variant van de head-corner parser. In hoofdstuk 4 wordt een algemenere variant gedefinieerd, en worden enkele verbeteringen besproken.
\begin{figure}
\par\pr\pred
\head{\mbox{\it parse}(\mbox{\rm Doel},\mbox{\rm P}_...
...m Mid},\mbox{\rm Groot},\mbox{\rm P}_{1},\mbox{\rm P}).}
\epred\epr
\end{figure}

Het vervolg van hoofdstuk 4 bespreekt enkele uitbreidingen en verbeteringen van de head-corner parser. Bij wijze van uitgewerkt voorbeeld laat ik zien hoe Lexicalized Tree Adjoining Grammars geparseerd kunnen worden met behulp van een variant van de head-corner parser. Een belangrijke reductie van de zoekruimte kan worden bereikt voor grammatica's waarbij de operaties op strings monotoon zijn met betrekking tot de volgorde van de terminale symbolen. TAG's bezitten deze monotonieeigenschap bijvoorbeeld. Ik laat zien hoe door middel van een simpele uitbreiding de head-corner parser deze eigenschap kan benutten, om zo de efficiëntie van de parser te vergroten.


next up previous contents
Next: Omkeerbaar automatisch vertalen Up: Omkeerbaarheid in natuurlijke-taalverwerking Previous: `Semantic-head-driven' generatie
Noord G.J.M. van
1998-09-30