Gramatyka bezkontekstowa to skończony zbiór reguł, mówiących, czy dane wyrażenia są poprawne gramatycznie (poprawne składniowo) oraz jaka jest ich struktura gramatyczna. Poniżej przedstawiony został prosty przykład gramatyki dla fragmentu języka angielskiego.
s -> np vp np -> det n vp -> v np vp -> v det -> a det -> the n -> womaneasy n -> man v -> shoots
Składniki reguł gramatyk bezkontekstowych można podzielić na 2 grupy:
Każda reguła gramatyki bezkontekstowej składa sie z symbolu nieterminalnego (będącego lewą częścią reguły) i z symbolu terminalnego, lub nieterminalnego (lub kombinacji dwóch typów symboli), który stanowi prawą stronę reguły.
Rozważając przypadek z powyższego listingu i zasady budowania reguł z sekcji Symbole terminalne i nieterminalne można wysnuć wniosek, że reguły tworzą pewnego rodzaju drzewo, którego liśćmi są symbole terminalne, a poszczególnymi węzłami symbole nieterminalne.
Takie drzewo dla zdania a woman shoots a man, bazujące na gramatyce z powyższego listingu miałoby następującą postać.
DCG jest zapisem pozwalającym tworzyć pasery bazujące na CFG; innymi słowy jest to zapis będący prologową reprezentacją formalnej notacji CFG. Przykład z sekcji Gramatyki bezkontekstowe zapisany za pomocą DCG wyglądałby następująco:
s --> np,vp. np --> det,n. vp --> v,np. vp --> v. det --> [the]. det --> [a]. n --> [woman]. n --> [man]. v --> [shoots].
Zakładając, że chcemy sprawdzić czy zdanie a man shoots a woman jest zgodne z gramatyką, wywołujemy następujący predykat:
s([a,woman,shoots,a,man],[]).
s([a,woman,shoots,a,man],[shoots]).
zakończy sie niepowodzeniem (ponieważ zdanie bez czasownika nie jest poprawne według gramatyki przedstawionej w DCG (Definite clause Grammars)), ale wywołanie s([a,man,shoots,a,woman],[a,woman]).</code> da pozytywny wynik, ponieważ zdanie a man shoots jest zgodne z gramatyką.
DCG to tak naprawdę syntactic sugar dla list różnicowych. Zapis podany w listingu z sekcji DCG (Definite clause Grammars) jest interpretowany przez Prolog identycznie jak ten poniżej:
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([the|W],W). det([a|W],W). n([woman|W],W). n([man|W],W). v([shoots|W],W).
W celu budowania bardziej skomplikowanych gramatyk, bardzo przydatne jest parametryzowanie niektórych reguł. Przykładowo, chcąc rozbudować gramatykę z podrozdziału (XXX) tak aby zamiast rzeczowników woman oraz man można było stosować również zaimki, należy określić w którym miejscu zdania jaki zaimek może zostać użyty. Można to osiągnąć albo poprzez dodanie nowych reguł, lub poprzez sprarametryzowanie istniejących.
W przykładzie poniżej określamy, że zaimki he oraz she mogą stać na początku zdania pełniąc rolę podmiotu, natomiast zaimki her oraz him mogą występować w zdaniu jedynie jako dopełnienie.
s --> np(subject),vp. np(_) --> det,n. np(X) --> pro(X). vp --> v,np(object). vp --> v. det --> [the]. det --> [a]. n --> [woman]. n --> [man]. pro(subject) --> [he]. pro(subject) --> [she]. pro(object) --> [him]. pro(object) --> [her]. v --> [shoots].
Ponieważ każdy składnik reguły DCG traktowany jest w sposób przedstawiony w (Jak to działa), nie jest możliwe bezpośrednie wykorzystywanie predykatów prologowych w ciele reguły. Aby dodać kod Prolog do reguły DCG należy umieścić go w nawiasach klamrowych.
s --> np,vp, {write('Zdanie poprawne')}.
Przykład użycia wstawki prologowej do sprawdzenia, czy podstawowy składnik wyrażenia matematycznego jest liczbą.
expr --> term, addterm. addterm --> []. addterm --> [+], expr. term --> factor, multfactor. multfactor --> []. multfactor --> [*], term. factor --> [I], {integer(I)}. factor --> ['('], expr, [')'].