This work is licensed under a
Creative Commons Attribution-NonCommercial-ShareAlike 4.0
International License.
Welke van de volgende zinnen is grammaticaal juist?
Antwoord: de laatste twee zijn grammaticaal juist.
Prolog wordt en is gebruikt voor verschillende doeleinden, maar de bedenkers, Alain Colmerauer en Phillipe Roussel (1972), waren geïnteresseerd in computationele linguistiek ofwel het verrichten van taalwetenschap met behulp van de computer. Het doen van taalwetenschap met de computer wordt nog steeds met Prolog gedaan. Ook in meer commerciële toepassingen rond taal wordt gebruik gemaakt van Prolog. Bijvoorbeeld, delen van IBM's QA (vraag en antwoord) supercomputer Watson zijn in Prolog geprogrammeerd. Tegenwoordig kom je op websites waar je vragen kunt stellen vaak in aanraking met "robots" die jouw vraag proberen te beantwoorden, of op zijn minst zo te analyseren dat je direct aan de meest geschikte persoon wordt gekoppeld. De antwoorden die jij ingeeft moeten in dergelijke applicaties worden geanalyseerd. Onze natuurlijke talen (de talen waarmee mensen communiceren) zijn vrij complex. Je kunt niet verwachten dat we in volgende lessen heel diep kunnen gaan, maar we kunnen je een beetje meenemen in de basisideeën. We zetten eerst het idee op, daarna maken we een eerste niet zo optimale aanpak in Prolog. In de volgende zullen we nagaan hoe we in Prolog een efficiënter routine kunnen programmeren.
We beginnen met de introductie van een moeilijke term te weten: Definite Clause Grammar (DCG).
Een Definite Clause Grammar (DCG) is een manier om de grammaticaregels van
natuurlijke (menselijke) of niet natuurlijke (computer) talen om te zetten naar regels in een logische programmeertaal,
waarvan Prolog er één is. De logische regels in een DCG hebben alleen betrekking op (lijsten van) woorden en zijn
gericht op het grammaticaal correct weergeven van zinnen. Dit wil nog niet zeggen dat de zinnen dan zinnig zijn.
B.v. De zin "De man kust de vrouw." is een zinvolle grammaticaal correcte zin. Echter de zin "De hoofdluis programmeert de computer."
is alleen grammaticaal correct of je moet wel een hele slimme hoofdluis hebben of je bent een boek aan het schrijven
waarin dieren het voor het zeggen hebben zoals b.v.
Toon Tellegen dat doet. Grammatica's waarin we alleen
letten op de structuur maar niet op de betekenis noemt men contextvrije grammatica's (CFG = context free grammar).
Om een idee te geven van computergestuurde taalanalyse met behulp van Prolog beperken wij ons tot deze CFG's en we gebruiken
daarin ook een zeer beperkte woordenschat. We gebruiken daarin de Engelse terminologie.
NB: de tekst in het verhaaltje hiernaast is al behoorlijk complex, zo diep gaan wij niet. Nijntje taal is al moeilijk genoeg.
| Term | Vertaling |
|---|---|
| s is de afkorting voor sentence | zin |
| n is de afkorting voor noun | zelfstandig naamwoord |
| v is de afkorting voor verb | werkwoord |
| p is de afkorting voor phrase | uitdrukking |
| det is de afkorting voor determiner | lidwoord |
| → is het teken voor implicatie | impliceert |
| s → np vp | Een zin impliceert (is opgebouwd uit) een noun phrase gevolgd door een verb phrase. |
| np → det n | Een noun phrase impliceert een determiner gevolgd door een noun. |
| vp → v np | verb phrase impliceert een verb gevolgd door een noun phrase. |
| vp → v | Of verb phrase impliceert een verb . |
| det → een | Een determiner impliceert het lidwoord een. |
| det → de | Of een determiner impliceert het lidwoord de. |
| n → hond | Een noun impliceert het zelfstandige naamwoord hond. |
| n → vrouw | Of een noun impliceert het zelfstandige naamwoord vrouw. |
| v → aait | Een verb impliceert de werkwoordsvorm aait. |
Tijd om eens een voorbeeld van een contextvrije grammatica te geven gevormd met een heel klein stukje
van de Nederlandse taal. We gebruiken slechts woorden hond en vrouw,
de en een en de tegenwoordige tijd derde persoon enkelvoud
van het werkwoord aaien aait. Op deze set woorden formuleren we grammaticale regels (zie het voorbeeld hiernaast).
Je ziet dat hond en vrouw de rol van noun (zelfstandig naamwoord) moeten spelen, de en een
zijn de determiners (lidwoord) en aait krijgt de rol verb. Met deze woorden en hun rollen worden combinaties
gedefinieerd.
Een noun phrase moet bestaan uit een lidwoord gevolgd door een zelfstandig naamwoord.
Een verb phrase moet bestaan uit een verb gevolgd door een noun phrase of aleen uit een verb.
Een sentence moet bestaan uit een noun phrase gevolgd door een verb phrase.
Grammaticaal correcte zinnen die met deze regels gevormd kunnen worden zijn bijvoorbeeld:
Met deze grammatica kunnen we een eindig aantal grammaticaal correcte zinnen vormen. Bekijk je het probleem met
de wiskundige bril vanuit de combinatoriek dan hebben we voor de eerste np twee mogelijkheden voor het lidwoord
en twee mogelijkheden voor het zelfstandig naamwoord. In totaal 2 × 2 = 4 mogelijkheden.
Daarna hebben we de keus om alleen de werkwoordsvorm aait te kiezen (blijft 4 mogelijkheden)
of aait gevolgd door een noun phrase (weer 4 mogelijkheden dus totaal 4 × 4 = 16).
Samen geeft dat 20 mogelijke zinnen.
| s → np vp | Een zin impliceert (houdt in) een noun phrase gevolgd door een verb phrase. |
| np → det n | Een noun phrase impliceert een determiner gevolgd door een noun. |
| vp → v np | verb phrase impliceert een verb gevolgd door een noun phrase. |
| vp → v | Of verb phrase impliceert een verb . |
| det → een | Een determiner impliceert het lidwoord een. |
| det → de | Of een determiner impliceert het lidwoord de. |
| n → hond | Een noun impliceert het zelfstandige naamwoord hond. |
| n → vrouw | Of een noun impliceert het zelfstandige naamwoord vrouw. |
| n → poes | Of een noun impliceert het zelfstandige naamwoord poes. |
| v → aait | Een verb impliceert de werkwoordsvorm aait. |
| v → voert | Een verb impliceert de werkwoordsvorm voert. |
zo meteen gaan we ons grammatica voorbeeld naar Prolog overzetten. Voor we dat doen is het zinvol om aandacht te geven aan een grafische representatie van grammatica's. In de figuur hiernaast is een boomstructuur ( tree structure) weergegeven voor de zin "De vrouw aait de hond". De top van de boom is de hele zin zelf. Hoe lager je komt in de boom hoe meer elementair de knoop (splitsing in de boom) een deel van de zin representeert. Uit eindelijk kom je op de individuele worden uit. De boom maakt het makkelijk om te zien hoe een zin opgebouwd dient te worden.
Als we zo in Prolog een programma gaan schrijven dat zinnen in grammatica's moet gaan testen dan volgt de logische controle juist deze structuur van de boom.
| s → np vp | Een zin impliceert (houdt in) een noun phrase gevolgd door een verb phrase. |
| np → det ap | Een noun phrase impliceert een determiner gevolgd door een adjective phrase. |
| np → det n | Een noun phrase impliceert een determiner gevolgd door een noun. |
| ap → a n | Een adjective phrase impliceert een adjective gevolgd door een noun. |
| vp → v np | verb phrase impliceert een verb gevolgd door een noun phrase. |
| vp → v | Of verb phrase impliceert een verb . |
| det → een | Een determiner impliceert het lidwoord een. |
| det → de | Of een determiner impliceert het lidwoord de. |
| a → lieve | Een adjective impliceert de bijvoeglijke bepaling lieve. |
| a → mooie | Of en adjective impliceert de bijvoeglijke bepaling mooie. |
| n → hond | Een noun impliceert het zelfstandige naamwoord hond. |
| n → vrouw | Of een noun impliceert het zelfstandige naamwoord vrouw. |
| v → aait | Een verb impliceert de werkwoordsvorm aait. |
s(Z):- np(X), vp(Y), append(X,Y,Z).
np(Z):- det(X), n(Y), append(X,Y,Z).
vp(Z):- v(X), np(Y), append(X,Y,Z).
vp(Z):- v(Z).
det([de]).
det([een]).
n([vrouw]).
n([hond]).
v([aait]).
Na flink wat theorie zijn we eindelijk zijn we toegekomen bij een implementatie van context vrije grammatica's in Prolog. De opdrachten zijn, gegeven een context vrije grammatica, om een herkenner (recogniser) van de grammatica te ontwerpen en ook een ontleder van zinnen. In dit hoofdstuk maken we eerste een herkenner. Eerst ontwikkelen een niet zo'n heel slimme herkenner, daarna gaan we er een maken die slimmer gebruik maakt van de kracht van Prolog. We gebruiken daar in verschillijsten. Uiteindelijk komen we dan aan bij de in Prolog ingebouwde Definite Clause Grammar. In het volgende hoofdstuk bekijken we meer gedetailleerd naar Definite Clause Grammars en leren we om ontleders te definieren.
Dus gegeven een context vrije grammatica, hoe definiëren we dan een herkenner in Prolog? Om precies te zijn, Prolog biedt ons een recht toe recht aan antwoord op deze vraag: we kunnen eenvoudig Prolog regels gebruiken die corresponderen met de grammatica regels.
Een simpele (maar zoals we straks zullen leren) manier om dit te doen gaat als volgt. We gebruiken lijsten om de woorden in een zin op te slaan. Bij voorbeeld: de lijst [ de, vrouw, aait, de , hond ] voor de zin "De vrouw aait de hond". Je kunt voor de context vrije grammatica's het implicatie teken → lezen als bestaat uit, of als kan worden gevormd uit. De regel s → np vp kan dus worden gezien alsof er wordt geschreven: een lijst van worden is een zin als deze het resultaat is van een samenvoeging van een np lijst met een vp lijst. Je weet al dat we in Prolog lijsten aan elkaar kunnen plakken (concatenate) met het append/3 commando. Ook enkele woorden kunnen we simpel definiëren als een n lijst, b.v. [vrouw] is een n lijst.
Het resultaat is gegeven hiernaast. Kopieer dit naar SWISH en stel eens de volgende vragen:
Je krijgt naar verwachting achtereenvolgens true en false. Je kunt ook op een simpele manier alle mogelijke zinnen laten maken door de vraag ?- s(X). te stellen. Welke antwoorden krijg je op de vraag ?- s([de,X,aait,een,Y]).
s(Z):- np(X), vp(Y), append(X,Y,Z).
np(Z):- det(X), ap(Y), append(X,Y,Z).
np(Z):- det(X), n(Y), append(X,Y,Z).
ap(Z):- a(X), n(Y), append(X,Y,Z).
vp(Z):- v(X), np(Y), append(X,Y,Z).
vp(Z):- v(Z).
det([de]).
det([een]).
a([lieve]).
a([mooie]).
n([vrouw]).
n([hond]).
n([poes]).
v([aait]).
v([voert]).
In het bovenstaande Prolog programma wordt eerst bij een gegeven lijst Z de regel s(Z) append/3 gebruikt om de lijst te splitsen. Dit zorgt ervoor dat vanuit de lijst Z de lijsten X en Y worden aangemaakt. Hierna worden op gelijke wijze de andere regels uitgevoerd. Het programma gebruikt heel vaak append, daarnaast worden eerst niet geïnitialiseerde variabelen aangemaakt. Dit is niet erg wenselijk, zoals je in een eerder hoofdstuk hebtgezien. De werking van deze eerste herkenner is inderdaad niet al te best. Het is verhelderend om het programma eens te tijdens de analyse van de zin "de vrouw aait de hond".
[trace] ?- s([de, vrouw, aait, de, hond]). Call: (8) s([de, vrouw, aait, de, hond]) ? creep Call: (9) np(_3700) ? creep Call: (10) det(_3700) ? creep Exit: (10) det([de]) ? creep Call: (10) n(_3706) ? creep Exit: (10) n([vrouw]) ? creep Call: (10) lists:append([de], [vrouw], _3716) ? creep Exit: (10) lists:append([de], [vrouw], [de, vrouw]) ? creep Exit: (9) np([de, vrouw]) ? creep Call: (9) vp(_3718) ? creep Call: (10) v(_3718) ? creep Exit: (10) v([aait]) ? creep Call: (10) np(_3724) ? creep Call: (11) det(_3724) ? creep Exit: (11) det([de]) ? creep Call: (11) n(_3730) ? creep Exit: (11) n([vrouw]) ? creep Call: (11) lists:append([de], [vrouw], _3740) ? creep Exit: (11) lists:append([de], [vrouw], [de, vrouw]) ? creep Exit: (10) np([de, vrouw]) ? creep Call: (10) lists:append([aait], [de, vrouw], _3746) ? creep Exit: (10) lists:append([aait], [de, vrouw], [aait, de, vrouw]) ? creep Exit: (9) vp([aait, de, vrouw]) ? creep Call: (9) lists:append([de, vrouw], [aait, de, vrouw], [de, vrouw, aait, de, hond]) ? creep Fail: (9) lists:append([de, vrouw], [aait, de, vrouw], [de, vrouw, aait, de, hond]) ? creep Redo: (11) n(_3730) ? creep Exit: (11) n([hond]) ? creep Call: (11) lists:append([de], [hond], _3740) ? creep Exit: (11) lists:append([de], [hond], [de, hond]) ? creep Exit: (10) np([de, hond]) ? creep Call: (10) lists:append([aait], [de, hond], _3746) ? creep Exit: (10) lists:append([aait], [de, hond], [aait, de, hond]) ? creep Exit: (9) vp([aait, de, hond]) ? creep Call: (9) lists:append([de, vrouw], [aait, de, hond], [de, vrouw, aait, de, hond]) ? creep Exit: (9) lists:append([de, vrouw], [aait, de, hond], [de, vrouw, aait, de, hond]) ? creep Exit: (8) s([de, vrouw, aait, de, hond]) ? creep true .
s(X,Z):- np(X,Y), vp(Y,Z).
np(X,Z):- det(X,Y), n(Y,Z).
vp(X,Z):- v(X,Y), np(Y,Z).
vp(X,Z):- v(X,Z).
det([de|W],W).
det([een|W],W).
n([vrouw|W],W).
n([hond|W],W).
v([aait|W],W).
Een efficiëntere implementatie kan worden berijkt door gebruik te maken van verschil lijsten. Dit is een geavanceerde ( en, als je het door hebt, schitterende ) Prolog techniek die voor vele doeleinden kan worden gebruikt.
Het basis idee bij het gebruik van verschil lijsten is dat we de informatie ( in de vorm van de van lijsten in de regels )
niet als een enkelvoudige maar als het verschil tussen twee lijsten. Bijvoorbeeld, in plaats van de zin te representeren
door de lijst [de, vrouw, aait, de, hond] representeren we die door het paar lijsten [de, vrouw, aait, de, hond] en [].
Stel je hierbij voor dat de eerste lijst een bron is waar we informatie uithalen (de invoer lijst ) en de tweede lijst
waarin we de overgebleven informatie achter moeten laten. Bekeken vanuit dit oogpunt representeert de verschil lijst
[de, vrouw, aait, de, hond] [] de zin "de vrouw aait de hond" omdat het "zegt": Als ik al de symbolen in de linker
lijst volgens de juiste regels heb verwijderd en er in de rechterlijst niets over is dan heb ik de zin waarin ik
geïnteresseerd ben. Of wel de zin waarin we geïnteresseerd zijn is het verschil van de twee lijsten.
Dat is voorlopig al we moeten weten van verschil lijsten om onze herkenner te herschrijven. Als we in gedachten houden dat als we iets wegnemen, we ook iets moeten achterlaten, krijgen we de herkenner hiernaast.
De regel s(X,Z):- np(X,Y), vp(Y,Z). test eerst of X begint met een np, als dit waar is test dan of de rest Y ( dus zonder de goed gevormde np ) een vp is. Het paar X,Y is dus een noun phrase en het paar Y,Z een verb phrase.Als je op onderstaande button button klikt krijg je een trace te zien van de nieuwe versie. Hoewel deze versie wat moeilijker te begrijpen is, is het uitvoeren ervan aanzienlijk korter en wordt er geen enkele append meer gebruikt. Bovendien is daar ook een zin getest die geen deel uitmaakt van de grammatica. Je kunt dan zien hoe een fout doorwerkt.
We moeten toegeven dat de tweede methode een herkenner geeft die moeilijker te begrijpen is, zeker de eerste keer dat met deze in aanraking komt, en het is best lastig om al die verschillen tussen lijsten te overzien. Het zou echt prettiger zijn als er een mogelijkheid is om een herkenner te schrijven die net zo makkelijk te begrijpen is als de eerste maar die net zo efficiënt is als de tweede. In het volgende hoofdstuk zien we dat dit mogelijk is met behulp van Definite Clause Grammars.
Een vraag die aan de grammatica voldoet:
[trace] ?- s([de,vrouw,aait,de,hond],[]). Call: (8) s([de, vrouw, aait, de, hond], []) ? creep Call: (9) np([de, vrouw, aait, de, hond], _3750) ? creep Call: (10) det([de, vrouw, aait, de, hond], _3750) ? creep Exit: (10) det([de, vrouw, aait, de, hond], [vrouw, aait, de, hond]) ? creep Call: (10) n([vrouw, aait, de, hond], _3750) ? creep Exit: (10) n([vrouw, aait, de, hond], [aait, de, hond]) ? creep Exit: (9) np([de, vrouw, aait, de, hond], [aait, de, hond]) ? creep Call: (9) vp([aait, de, hond], []) ? creep Call: (10) v([aait, de, hond], _3750) ? creep Exit: (10) v([aait, de, hond], [de, hond]) ? creep Call: (10) np([de, hond], []) ? creep Call: (11) det([de, hond], _3750) ? creep Exit: (11) det([de, hond], [hond]) ? creep Call: (11) n([hond], []) ? creep Exit: (11) n([hond], []) ? creep Exit: (10) np([de, hond], []) ? creep Exit: (9) vp([aait, de, hond], []) ? creep Exit: (8) s([de, vrouw, aait, de, hond], []) ? creep true |
Een vraag die niet aan de grammatica voldoet:
[trace] ?- s([de,man,aait,de,hond],[]). Call: (8) s([de, man, aait, de, hond], []) ? creep Call: (9) np([de, man, aait, de, hond], _3756) ? creep Call: (10) det([de, man, aait, de, hond], _3756) ? creep Exit: (10) det([de, man, aait, de, hond], [man, aait, de, hond]) ? creep Call: (10) n([man, aait, de, hond], _3756) ? creep Fail: (10) n([man, aait, de, hond], _3756) ? creep Fail: (9) np([de, man, aait, de, hond], _3756) ? creep Fail: (8) s([de, man, aait, de, hond], []) ? creep false. |
s(X,Z):- np(X,Y), vp(Y,Z).
np(X,Z):- det(X,Y), ap(Y,Z).
np(X,Z):- det(X,Y), n(Y,Z).
ap(X,Z):- a(X,Y), n(Y,Z).
vp(X,Z):- v(X,Y), np(Y,Z).
vp(X,Z):- v(X,Z).
det([de|W],W).
det([een|W],W).
a([lieve|W],W).
a([mooie|W],W).
n([vrouw|W],W).
n([hond|W],W).
n([poes|W],W).
v([aait|W],W).
v([voert|W],W).