NLP 02/03 Opgave 4

OPGAVE 4: Chart Parsing

Deadline: vrijdag 13 juni

In deze opgave maak je een hulpmiddel voor het zoeken naar taalkundige patronen in een tekst die reeds voorzien is van `part of speech tags' (Gsearch is een voorbeeld van zo'n pakket). Als voorbeeld gebruiken we het Eindhoven corpus. Materiaal in dit corpus ziet er als volgt uit:

Dit                                      Pron(aanw,neut,zelfst)
in                                       Prep(voor)
verband                                  N(soort,ev,neut)
met                                      Prep(voor)
de                                       Art(bep,zijd_of_mv,neut)
gemiddeld                                Adj(adv,stell,onverv)
langere                                  Adj(attr,vergr,verv_neut)
levensduur                               N(soort,ev,neut)
van                                      Prep(voor)
de                                       Art(bep,zijd_of_mv,neut)
vrouw                                    N(soort,ev,neut)
.                                        Punc(punt)

Een gebruiker wil in tekst van deze vorm bijvoorbeeld alle NPs vinden. Hiervoor zou je een grammatica kunnen schrijven die bijvoorbeeld een Art gevolgd door een N als een NP herkent. Met een chart-parser kun je vervolgens alle constituenten vinden in de input die een NP vormen. Met behulp van de chart kun je de input vervolgens aan de gebruiker tonen met haakjes om de NPs.....

Het corpus

Het corpus is voor deze opgave omgezet in Prolog. Zinnen zijn gecodeerd als zin(Nr,LijstTags), waar LijstTags een lijst van (Part of Speech) Tags is, gecodeerd als Prolog termen, met als laatste argument altijd het woord zelf.

zin(1,[art(bep,zijd_of_mv,neut,'De'),
       n(soort,mv,neut,verzekeringsmaatschappijen),
       v(trans,ott,of_123,mv,verhelen),
       adv(gew,geen_func,stell,onverv,niet),
       ....]).

Het corpus (1000 zinnen) staat in cdb.pl. In cdb.tag en cdb.zinnen vind je delen van hetzelfde materiaal in een formaat dat beter leesbaar is voor mensen.

De grammatica

De chart-parser (zie beneden) werkt voor grammatica's waar regels de vorm rule(Moeder,LijstDochters) hebben, bv.

rule(np, [det,n]).

Omdat de input al voorzien is van categorieen hoef je niet een echt woordenboek te maken. Het enige wat je moet definieren (als lex(Categorie,Woord)) is welke categorieen uit de grammatica met welke POS tags corresponderen, bv.

lex(det,art(_,_,_,_)).

Een determiner kan dus een POS tag art (voor artikel) met 4 argumenten zijn.

De Parser

De parser is een shift-reduce chart-parser die met behulp van assert een chart opbouwt. Items in de chart hebben de vorm constituent(Begin,End,Category), bv

constituent(0, 2, np).

Je roept de parser aan met

 :- bf_shift_reduce(Input)

waar Input een lijst Tags is.
Je kunt een overzicht krijgen van alle constituenten door na parsing

:- listing(constituent).

te doen.

De parser staat in parser.pl

De Opdracht

Voeg enkele regels en een `lexicon' voor constituenten van de categorie NP en PP toe aan de voorbeeldregels in parser.pl.
Voeg een predicaat find(Cat,Nr) aan de parser toe, dat de begin- en eindposities van alle constituenten van categorie Cat in zin Nr naar het scherm schrijft.
Voeg een predicaat match(Cat,Nr) toe, dat de zin Nr op het scherm zet, met haakjes rond de constituenten van categorie Cat. Bv.
```
[Het loodswezen] ressorteert onder [de Marine] waardoor [de loodsen] ambtenaren zijn .
```
1. N.b. Wanneer op positie N 2 constituenten met categorie Cat beginnen, geef je alleen de haakjes voor de langste constituent (longest match).
Voeg een predicaat search(Cat) toe, dat voor iedere zin in het corpus onderzoekt of er constituenten van categorie Cat aanwezig zijn. Zo ja, dan produceer je output zoals match/2, maar nu geef je ook het zinsnummer.

N.b. Wanneer een zin geen matching constituent bevat, schrijf je die zin ook niet naar het scherm.

Test je programma nu door regels en lex-predicaten toe te voegen die met PPs matchen die een enkelvoudige NP bevatten zonder lidwoord (voorbeelden zijn naast zanger, door Japan, van formaat, in zee, maar niet in het oerwoud, van vragen) en zoek hiernaar met search.
1. N.b. je kunt natuurlijk lex-definities schrijven die naar kenmerken van de Tag verwijzen.

Tips

Gebruik write(Cat), write(' '), etc, en nl, om naar het scherm te schrijven.
Het predicaat extract_word(Tag,Word), kun je gebruiken om het laatste argument van Tag te unificeren met Word (handig voor het printen van de string).
Negatie in Prolog is \+ (bv \+ ( constituent(_,_,np) ).

Inleveren

Lever de aangepaste parser-code in, waar nodig voorzien van commentaar.
Geef een voorbeeld van de output die je krijgt bij opdracht 5.