Eine kontextfreie Grammatik (CFG) setzt sich aus einer endlichen Summe von Regeln zusammen, welche die syntaktische Korrektheit einer über dem Vokabular T gebildeten formalen Sprache festlegen. Bestandteile von CFG: jeweils endliche Mengen von Nicht-Terminal-Symbolen (NT), Terminal-Symbolen (T), Regeln (R) und Startsymbol (S). DCG ist eine spezielle Notation von CFG, die in Prolog implementiert ist; Regeln werden beim Einlesen automatisch in Prolog-Klauseln übersetzt (kann mit listing/1 abgerufen werden)
Beispiel für DCG-Regeln:
syntaktische:
S --> NP VP
NP --> Det N wird z.B zu: np(A,B) :- det(A,C), n(C,B).
VP --> V
lexikalische:
Det --> [the]
N --> [bird]
V --> [sings]
Terminalsymbole müssen in Listen-Form eingegeben werden. Um bei der Satzbildung KNG-Kongruenz (Genus, Kasus, Numerus) zu erreichen, können komplexe NT-Symbole verwendet werden. Bsp: np(Genus) --> det(Genus), n(Genus).
Ob ein Satz aufgrund einer Grammatik gültig ist, kann mit phrase/2 (eingebautes Prädikat) überprüft werden.
'C'/3 (= "connect") ist ein eingebautes Prädikat, das bestimmt, wann ein Wort zwei Knoten verbindet: 'C'([Wort|Rest], Wort, Rest).
Der Satz, der bei einer Anfrage interessiert, ist die Differenz des Inhalts von zwei Listen.
Beispiel einer Anfrage: ?- s([the, bird, sings], [ ]). DCG fungiert dabei als Listendifferenzerkenner.
CFG-Regeln können auch für rein formale Sprachen (a_b_) formuliert werden. Aufgrund einer Grammatik G können Sätze abgeleitet werden, wobei ε (Epsilon)für eine leere Abfolge von Grammatiksymbolen steht.
Der Prolog-Parser (Syntaxanalysierer) für DCG arbeitet top-down und left-right, weshalb linksrekursive Grammatiken problematisch sind (-->endlose Schleife). Um dieses Problem zu umgehen, kann man die Grammatik entweder umwandeln (u.U nimmt man damit linguistisch nicht wünschenswerte Struktur in Kauf ) oder ein anderes Parsing-Verfahren ( z.B "shift reduce parser") verwenden. Bei grossen Lexika ist das "chart parsing Verfahren" eine Alternative zum Standard-Prolog-DCG-Verfahren.