This work is licensed under a
Creative Commons Attribution-NonCommercial-ShareAlike 4.0
International License.
| s --> np,vp. |
| np --> det,n. |
| vp --> v,np. |
| vp --> v. |
| det --> [een]. |
| det --> [de]. |
| n --> [hond]. |
| n --> [vrouw]. |
| v --> [aait]. |
Dit hoofdstuk[trace] ?- s([de,vrouw,aait,een,hond],[]). Call: (8) s([de, vrouw, aait, een, hond], []) ? creep Call: (9) np([de, vrouw, aait, een, hond], _3128) ? creep Call: (10) det([de, vrouw, aait, een, hond], _3128) ? creep Exit: (10) det([de, vrouw, aait, een, hond], [vrouw, aait, een, hond]) ? creep Call: (10) n([vrouw, aait, een, hond], _3128) ? creep Exit: (10) n([vrouw, aait, een, hond], [aait, een, hond]) ? creep Exit: (9) np([de, vrouw, aait, een, hond], [aait, een, hond]) ? creep Call: (9) vp([aait, een, hond], []) ? creep Call: (10) v([aait, een, hond], _3128) ? creep Exit: (10) v([aait, een, hond], [een, hond]) ? creep Call: (10) np([een, hond], []) ? creep Call: (11) det([een, hond], _3128) ? creep Exit: (11) det([een, hond], [hond]) ? creep Call: (11) n([hond], []) ? creep Exit: (11) n([hond], []) ? creep Exit: (10) np([een, hond], []) ? creep Exit: (9) vp([aait, een, hond], []) ? creep Exit: (8) s([de, vrouw, aait, een, hond], []) ? creep true . |
Vorige hoofdstuk[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 . |
Wat zijn Definite Clause Grammars? Simpel gezegd, een mooie manier om grammatica's te schrijven dat de onderliggende verschil lijsten verbergt. we bekijken drie voorbeelden.
Het eerste voorbeeld hiernaast is code die je direct in Swish kunt kopiëren en runnen met de vraag:s([de,vrouw,aait,een,hond],[]).
Deze vraag is dezelfde als in het efficiënte voorbeeld en je de traces vergelijkt zie je geen verschil. Prolog heeft voor ons dus al het meest efficiënte voorbeeld als een standaard geïmplementeerd, met de zeer plezierige mogelijkheid om de grammatica's op een zeer eenvoudige wijze op te schrijven.
De vraag ?- listing(s). geeft:
s(A, B) :-
np(A, C),
vp(C, B).
true.
Zoals je ziet is dit precies de implementatie die we in het vorige hoofdstuk hebben gemaakt.
De vraag ?- s(X,[]) levert weer alle mogelijke zinnen die aan de grammatica voldoet en
de vraag ?- np(X,[]) levert weer alle mogelijke noun phrases.
?- listing(np).
np(A, B) :-
det(A, C),
n(C, B).
true.
?- listing(det). det([een|A], A). det([de|A], A). true.Bij andere Prolog versies kan dit echter anders zijn.
| s → s conj s | Een zin impliceert (is opgebouwd uit) een (bij)zin (s) gevolgd door een conjunction (voegwoord) gevolgd door een (bij)zin. |
| 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. |
| conj → en | Een conjunction impliceert het voegwoord en. |
| conj → of | Of een conjunction impliceert het voegwoord of. |
| conj → maar | Of een conjunction impliceert het voegwoord maar. |
| s --> s, conj, s. |
| s --> np,vp. |
| np --> det,n. |
| vp --> v,np. |
| vp --> v. |
| conj --> [en]. |
| conj --> [of]. |
| conj --> [maar]. |
| det --> [een]. |
| det --> [de]. |
| n --> [hond]. |
| n --> [vrouw]. |
| v --> [aait]. |
Zinnen kunnen vaak samengevoegd worden. Onze simpele grammatica kan slechts 20 zinnen produceren. Het is echter heel eenvoudig om met een heel kleine uitbreiding deze simpele grammatica oneindig veel zinnen te laten genereren. We voegen daartoe aan onze grammatica de volgende regels toe.
s → s conj s
conj → en
conj → of
conj → maar
De complete grammatica is rechts weergegeven. De regel s → s conj s houdt de bewering in dat een zin bestaat uit de samenvoeging van twee zinnen door een in het midden geplaatst voegwoord (conjunction (conj) ). Er zijn natuurlijk meer voegwoorden in de Nederlandse taal, we geven slechts een paar voorbeelden (en of en maar).
Het lijkt dat dit, in navolging van de implementatie van onze kleine grammatica, eenvoudig om deze regels om te zetten met als resultaat het programma hiernaast. Helaas zijn er grote problemen met deze eerste poging.
Wat gaat er mis? Laten we eens afvragen wat Prolog met deze DCG precies doet. Wat gebeurt er als we de vraag ?- s([de,vrouw,aait],[]) stellen? Het antwoord Prolog schiet gelijk in een oneindige lus.
Snap je waarom? Prolog vertaalt de DCG in gewone Prolog regels. Als we de recursieve regel s --> s, conj, s. zoals in het voorbeeld programma voor de niet recursieve regel s --> np,vp. dan wordt de vertaling de volgorde:
s(A, B) :-
s(A, C),
conj(C, D),
s(D, B).
s(A, B) :-
np(A, C),
vp(C, B).
Vanuit de declaratie van regels is dit oké, maar als dit moet worden uitgevoerd gaat het helemaal mis. Als Prolog de eerste regel gaat gebruiken, treft het gelijk het doel s(A,C) wat Prolog er toe zet om gelijk weer de eerste regel aan te roepen, wat weer lijdt tot de aanroep van s(A,C), waarna het weer de eerste regel aanroept, en zo voorts. Kortom we zitten vast in een oneindige lus.
Helpt het dan om de volgorde om te draaien? We beschouwen nu
s --> np,vp. s --> s, conj, s.met vertaling
s(A, B) :-
np(A, C),
vp(C, B).
s(A, B) :-
s(A, C),
conj(C, D),
s(D, B).
Nu wordt altijd eerst de niet recursieve regel aangeroepen. Wat gebeurt er nu met de vraag ?- s([de,vrouw,aait],[]).? Op deze vraag komt een positief resultaat, maar dit gaat helaas niet wanneer we een negatief resultaat verwachten. Als we de foutieve vraag ?- s([vrouw,aait],[]). stellen geeft de niet recursieve regel het antwoord false, waarna de tweede regel wordt aangeroepen, dan gelijk weer de eerste regel aanroept, die dan door de fout weer de tweede regel aanroept, dus weer een oneindige lus.
| s --> simpele_s. |
| s --> simpele_s, conj, s. |
| simpele_s --> np,vp. |
| np --> det,n. |
| vp --> v,np. |
| vp --> v. |
| conj --> [en]. |
| conj --> [of]. |
| conj --> [maar]. |
| det --> [een]. |
| det --> [de]. |
| n --> [hond]. |
| n --> [vrouw]. |
| v --> [aait]. |
Toch is er een weg uit dit probleem. De standaard oplossing in dit soort gevallen is het introduceren van een nieuwe tussenregel. We kunnen bijvoorbeeld kiezen voor de regel simpele_s voor niet samengestelde zinnen. De DCG ziet er dan uit als het voorbeeld hiernaast.
Natuurlijk controleer je nu gelijk dat Prolog niet meer in een oneindige lus terecht komt. Het programma loopt dus niet meer vast, wat vanuit het gezichtspunt van een programmeur veel voldoening geeft. Vanuit taalkundig oogpunt is dit minder attractief. De DCG met de oneindige lus was vanuit taalkundige intuïtie beter te begrijpen. De toevoeging van simpele_s heeft helaas geen taalkundige reden.
De moraal van dit verhaal. Definite Clause Grammar's in Prolog zijn niets magisch. Ze bieden de mogelijkheid om een grammatica makkelijker op te schrijven, maar het is niet altijd mogelijk om precies de grammatica te implementeren. Bekijk goed wat Prolog met een een regel doet, vooral als er recursie in het spel is.
s --> onzin,reep,schommel. onzin --> [hopla]. onzin --> onzin,onzin. reep --> peer,zeep. peer --> me,mijn. me --> [ik]. mijn --> [ben]. zeep --> pees,vervoer. pees --> [een]. vervoer --> [trein]. schommel --> [toet]. schommel --> schommel,schommel.Schrijf de gewone Prolog regels op die gelijk zijn aan deze DCG regels.
s(A,B):- onzin(A,C),reep(C,D),schommel(D,B). onzin( [hopla|B],B). onzin(A,B):- onzin(A,C),onzin(C,B). reep(A,B):- peer(A,C),zeep(C,B). peer(A,B):- me(A,C),mijn(C,B). me([ik|B],B). mijn( [ben|B],B). zeep(A,B):- pees(A,C),vervoer(C,B). pees([een|B],B). vervoer( [trein|B],B). schommel([toet|B],B). schommel(A,B):- schommel(A,C),schommel(C,B).
s(A,B):- onzin(A,C),reep(C,D),schommel(D,B). onzin(A,B):- onzin1(A,B). onzin(A,B):- onzin1(A,C),onzin(C,B). onzin1( [hopla|B],B). reep(A,B):- peer(A,C),zeep(C,B). peer(A,B):- me(A,C),mijn(C,B). me([ik|B],B). mijn( [ben|B],B). zeep(A,B):- pees(A,C),vervoer(C,B). pees([een|B],B). vervoer( [trein|B],B). schommel(A,B):-schommel1(A,B). schommel(A,B):- schommel1(A,C),schommel(C,B). schommel1([toet|B],B).Probeer het maar eens met de volgende vragen:
| s → ∅ |
| s → l s r |
| l → a |
| r → b |
Ons laatste voorbeeld van een DCG is een DCG voor een formele taal. Een formele taal is geen natuurlijke taal (de taal waarmee mensen communiceren), maar meestal een verzameling van tekenreeksen die wetenschappers binnen de informatica, logica en wiskunde gebruiken voor verscheidene doeleinden (b.v. programmeertalen).
Een simpel voorbeeld van een formele taal is de taal bestaande uit de woorden an bn, met n een natuurlijk getal (0,1,2,3,...). De woorden bestaan dus uit tekenreeksen waarin een gelijk aantal a's en b's in voorkomen en wel zo dat er eerst een ononderbroken reeks van a's is die wordt gevolgd door en even lange ononderbroken reeks van b's bijvoorbeeld ab, aabb, aaabbb en aaaaaaabbbbbbb. Echter abba en aaabbbaabb voldoen niet hoewel deze evenveel a's als b's bevatten.
De context vrije grammatica die deze formele taal genereert is hiernaast weergegeven. Het symbool ∅ staat voor in het geheel geen woord ofwel het empty (=lege) woord. Dus s kan een leeg woord zijn (eerste regel) of een woord dat gevormd is uit een linkerzijde l een eerder gevormd woord s en een rechterzijde r. De linkerzijde verwijst naar een letter a en de rechterzijde naar een b. Het zou duidelijk moeten zijn dat deze grammatica alle en alleen elementen van an bn genereert, inclusief het lege woord.
| s --> []. |
| s --> l, s, r. |
| l --> [a]. |
| r --> [b]. |
Deze context vrije grammatica is simpel om te zetten naar de DCG die hiernaast is weergegeven. De tweede regel is recursief maar, omdat l en r geen oneindige lus genereren, geeft deze geen probleem. De DCG werkt precies zo als we willen. Stel maar eens de vragen:
| s --> [p. |
| s --> l, s. |
| l --> [a]. |