Definite-Clause Grammars (DCG) Gramatiky uspořádaných klauzulí
Syntaktická analýza
Významná aplikace Prologu: syntaktická analýza <M sentence --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun. noun_phrase --> noun.
verb_phrase --> verb, noun_phrase. verb_phrase --> verb.
determiner --> [the], determiner --> [a].
noun --> [student]. noun --> [dcg].
verb --> [1 i kes].
3 I ?- sentence([a, student, likes, dcg]). yes
Hana Rudová, Logické programování I, 20. dubna 201 2 2
Gramaticky uspořádaných klauzulí
DCG a CFG
DCG (DC gramatiky) jsou rozšířením bezkontextových gramatik (CFG) M Implementace DCG využívá rozdílových seznamů
Formální podobnosti mezi DCG a CFG: M CFG: pravidla tvaru x — y, kde 3 x e N je neterminál
M y e (N u T)* je konečná posloupnost terminálů a neterminálů
M DCG: pravidla tvaru <hlava> --> <tělo>
M <hl ava> je opět neterminál
3 <tělo> je opět konečná posloupnost terminálů a neterminálů
Pravidlo <hlava> --> <tělo> znamená, že
3 jedním z možných tvarů <hlavy> je <tělo>, neboli 3 <hl avu> je možno přepsat na <tělo>
Hana Rudová, Logické programování I, 20. dubna 201 2 3 Gramaticky uspořádaných klauzulí
Rozdíly a rozšíření DCG oproti CFG
M Neterminál může být téměř libovolný term, ovšem kromě seznamu, proměnné a čísla.
* neterminál muže být složený term, tj. neterminálům lze přidat argumenty.
M Terminál může být libovolný term, s tím, že terminály a posloupnosti terminálů uzavíráme do hranatých závorek - jako seznamy.
* hranaté závorky tedy odlišují terminály od neterminálů
Pravá strana pravidla může obsahovat dodatečné podmínky v podobě prologovských podcílů. Tyto podmínky uzavíráme do složených závorek.
M podmínky slouží jen pro testování, negenerují žádnou větnou formu
Levá strana pravidla může dokonce vypadat i tak, že neterminál je následován posloupností terminálů.
M Tělo pravidla smí obsahovat řez.
M nepodporováno všemi Prology
Hana Rudová, Logické programování I, 20. dubna 2012 4 Gramaticky uspořádaných klauzulí
Příklad: gramatika
3 sentence --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun_phrase2. noun_phrase --> noun_phrase2.
noun_phrase2 --> noun.
noun_phrase2 --> adjective, noun_phrase2.
verb_phrase --> verb.
verb_phrase --> verb, noun_phrase.
determiner --> [the].        noun --> [boy].
determiner --> [a]. noun --> [song].
verb --> [sings]. adjective --> [young].
M I ?- sentence(S, []).
S = [the,song,sings] ? ;
S = [the,song,sings,the,song] ?
I ?- sentence([the, young, boy, sings, a, song],[]). yes
Hana Rudová, Logické programování I, 20. dubna 201 2
5
Gramaticky uspořádaných klauzulí
Příklad: binární čísla
DC gramatika number rozeznávající binární čísla:
number --> [0]. number --> [1]. number --> [0], number, number --> [1], number.
I ?- number([0,l,0,l,l],  []). yes
Napište DCG number2 pro rozpoznání binárních čísel bez vedoucích nul.
Napište DCG number3 rozpoznávající binární čísla, které jsou mocninou dvojky.
Hana Rudová, Logické programování I, 20. dubna 201 2
6
Gramaticky uspořádaných klauzulí
Příklad: binární čísla
DC gramatika number rozeznávající binární čísla:
number --> [0]. number --> [1]. number --> [0], number, number --> [1], number.
I ?- number([0,l,0,l,l],  []). yes
Napište DCG number2 pro rozpoznání binárních čísel bez vedoucích nul.
Napište DCG number3 rozpoznávající binární čísla, které jsou mocninou dvojky.
number2 --> [1]. number2 --> [1], number.
Hana Rudová, Logické programování I, 20. dubna 201 2
6
Gramaticky uspořádaných klauzulí
Příklad: binární čísla
DC gramatika number rozeznávající binární čísla:
number --> [0]. number --> [1]. number --> [0], number, number --> [1], number.
I ?- number([0,l,0,l,l],  []). yes
Napište DCG number2 pro rozpoznání binárních čísel bez vedoucích nul.
Napište DCG number3 rozpoznávající binární čísla, které jsou mocninou dvojky.
number2 --> [1]. number2 --> [1], number.
number3 --> [1], zeros.
zeros --> [].
zeros --> [0], zeros.
Hana Rudová, Logické programování I, 20. dubna 2012 6 Gramaticky uspořádaných klauzulí
Příklad: neterminály s argumentem
M DC gramatika digits generuje binární čísla zapsaná jedinou číslicí:
digits --> same(O). digits --> same(l). same(N) --> [N]. same(N) --> [N], same(N).
I ?- digits([l, 1,0,1], [])■
no
I ?- digits([l,l,l], []).
yes
Upravte kód tak, aby byly akceptovány jen korektní věty:
s --> np, vp. np --> [zeny]. np --> [muzi]. vp --> [pracovali], vp --> [pracovaly].
?- s([zeny, pracovali], []). yes
Nápověda: přidejte proměnnou pro rod (pro np a vp )
Hana Rudová, Logické programování I, 20. dubna 201 2 7 Gramaticky uspořádaných klauzulí
Řešení: neterminály s argumentem
Původně:
s --> np, vp. np --> [zeny]. np --> [muzi]. vp --> [pracovali] . vp --> [pracovaly].
Řešení:
s --> np(Rod), vp(Rod). np(z) --> [zeny]. np(mz) --> [muzi]. vp(mz) --> [pracovali]. vp(z) --> [pracovaly].
Hana Rudová, Logické programování I, 20. dubna 201 2
8
Gramaticky uspořádaných klauzulí
Generativní/rozpoznávací síla DCG: větší než CFG
DCG dokáží generovat/rozpoznávat jazyky typu 0
M Cvičení: napište DCG gramatiku generující jazyk anbncn
M ?- abc(X,[]). X = [] ; X = [a, b, c] ; X = [a, a, b, b, c, c] ; X = [a, a, a, b, b, b, c, c, c] ;
Nápověda: využijte a(s(s(s(0)))), b(s(s(s(0)))), c(s(s(s(0))))
Hana Rudová, Logické programování I, 20. dubna 201 2
9
Gramaticky uspořádaných klauzulí
Generativní/rozpoznávací síla DCG: větší než CFG
DCG dokáží generovat/rozpoznávat jazyky typu 0
M Cvičení: napište DCG gramatiku generující jazyk anbncn
M ?- abc(X,[]). X = [] ; X = [a, b, c] ; X = [a, a, b, b, c, c] ; X = [a, a, a, b, b, b, c, c, c] ;
Nápověda: využijte a(s(s(s(0)))), b(s(s(s(0)))), c(s(s(s(0))))
abc --> a(N), b(N), c(N).
a(0) --> [].
a(s(N)) --> [a], a(N).
b(0) --> [].
b(s(N)) --> [b], b(N).
c(0) --> [].
c(s(N)) --> [c], c(N).
Hana Rudová, Logické programování I, 20. dubna 201 2
9
Gramaticky uspořádaných klauzulí
Pomocné podmínky v těle pravidel
J E -> T + E | T Vyhodnocování výrazů
T -> num
expr(X) --> term(A),  [+], expr(B), {X is A+B}.
expr(X) --> term(X).
term(X) --> [X], {number(X)}.
?- expr(X,  [l,+,2,+,2],  []). X = 5
Cvičení: přidejte operaci násobení
E -> N + E | N N -> T * N | T T -> num
Hana Rudová, Logické programování I, 20. dubna 201 2
10
Gramaticky uspořádaných klauzulí
Pomocné podmínky v těle pravidel
J E -> T + E | T
T -> num
expr(X) --> term(A),  [+], expr(B), {X is A+B}.
expr(X) --> term(X).
term(X) --> [X], {number(X)}.
?- expr(X,  [l,+,2,+,2],  []). X = 5
Cvičení: přidejte operaci násobení
E -> N + E | N N -> T * N | T T -> num
expr(X) --> expr2(A),  [+], expr(B), {X is A+B}. expr(X) --> expr2(X).
expr2(X) --> term(A),  [*], expr2(B), {X is A*B}. expr2(X) --> term(X). term(X) --> [X], {number(X)}.
Hana Rudová, Logické programování I, 20. dubna 201 2 1 0
Vyhodnocování výrazů
Gramaticky uspořádaných klauzulí
Komplexní vyhodnocování výrazů
E -> T + E I T - E I T T -> F * T I F / T I F F -> (E)  I f
expr(X) --> term(Y), [+], expr(Z), {X i s Y+Z}. expr(X) --> term(Y), [-], expr(Z), {X i s Y-Z}. expr(X) --> term(X).
term(X) --> factor(Y), [*], term(Z), {X i s Y*Z}. term(X) --> factor(Y), [/], term(Z), {X i s Y/Z}, term(X) --> factor(X).
factor(X) --> ['('], expr(X), [')']. factor(X) --> [X], {integer(X)}.
% vyhodnoceni výrazu 3+(4/2)-(2*6/3)
?- expr(X,[3,+,'(',4,/,2,')',-,'(',2,*,6,/,3,')'],[]). X = 1
Argument neterminálu je použit jako výstupní proměnná, která v sobě nese hodnotu příslušného aritmetického výrazu.
Hana Rudová, Logické programování I, 20. dubna 2012 11 Gramaticky uspořádaných klauzulí
Přepis do Prologu
Přepis do prologovského programu pomocí append/3:
3 Větu reprezentujeme seznamem slov [the,young,boy,sings,a,song]
3 Pravidlová část - neterminál chápeme jako unární predikát, jehož argumentem je ta větná složka, kterou daný neterminál popisuje
sentence(S) :- append(NP,VP,S),
noun_phrase(NP), verb_phrase(VP).
M Slovníková část - zapisujeme ji pomocí faktů:
determiner( [the]). noun([boy]). determi ner([a]).
Predikát append/3 zde nedeterministicky rozděluje aktuální větnou část na dva díly, což je velký zdroj neefektivnosti.
Lepší řešení poskytují rozdílové seznamy.
Hana Rudová, Logické programování I, 20. dubna 2012 12 Gramaticky uspořádaných klauzulí
Přepis do Prologu pomocí rozdílových seznamů
M Rozdílové seznamy reprezentovány dvěma argumenty, první představuje neúplný seznam a druhý jeho zbytek append(S-Sl, SI -SO, S-SO)
M Při volání predikátu S-SO je spojením: S-S3, S3-S2, S2-S1, SI -SO
sentence/2 je druhý argument prázdný; neúplný seznam tím uzavíráme tj. S0=[ ]
sentence(S,SO):- noun_phrs(S,SI), verb_phrs(Sl,SO).
noun_phrs(S,SO):- determiner(S,SI), noun_phrs2(Sl,SO). noun_phrs(S,SO):- noun_phrs2(S,SO).
noun_phrs2(S,SO):- adjective(S,SI), noun_phrs2(Sl,SO). noun_phrs2(S,SO):- noun(S,S0).
verb_phrs(S,SO):- verb(S,S0).
verb_phrs(S,SO):- verb(S,Sl), noun_phrs(Sl,SO).
determi ner([the|S],S). noun([boy|S],S).
determiner([aI S],S). noun([song|S],S).
verb([si ngs|S],S). adjective([young|S],S).
?- sentence([the,young,boy,sings,a,song],[]). yes
Hana Rudová, Logické programování I, 20. dubna 2012 13 Gramaticky uspořádaných klauzulí
Derivační strom analýzy
?- sentence(Tree,  [the,young,boy,sings,a,song],[]). Tree=s( np( det(the), np2( adj(young), np2(n(boy) ) ) ), vp( v(sings), np( det(a), np2( n(song) ) ) ) )
np
vp
det
np2
v
np
the   adj   np2 sings det np2
young n
a n
boy
song
Hana Rudová, Logické programování I, 20. dubna 201 2
14
Gramaticky uspořádaných klauzulí
Konstrukce derivačního stromu
Neterminály opatříme argumentem:
sentence(s(NP,VP)) --> noun_phrase(NP), verb_phrase(VP). noun(n(mama)) --> [mama]. noun(n(kralika)) --> [králika]. verb(v(pekla)) --> [pekla].
M Doplňte gramatiku, aby platilo:
| ?- sentence(X,  [mama,pekla,králika], []).
X = s(np(n(mama)),vp(v(pekla),np(n(kralika)))) yes
Hana Rudová, Logické programování I, 20. dubna 201 2
Gramaticky uspořádaných klauzulí
Konstrukce derivačního stromu
«á> Neterminály opatříme argumentem:
sentence(s(NP,VP)) --> noun_phrase(NP), verb_phrase(VP). noun(n(mama)) --> [mama]. noun(n(kralika)) --> [králika]. verb(v(pekla)) --> [pekla].
M Doplňte gramatiku, aby platilo:
| ?- sentence(X,  [mama,pekla,králika], []).
X = s(np(n(mama)),vp(v(pekla),np(n(kralika)))) yes
sentence(s(N,V)) --> noun_phrase(N), verb_phrase(V). noun_phrase(np(N)) --> noun(N). verb_phrase(vp(V)) --> verb(V).
verb_phrase(vp(V, N)) -->verb(V), noun_phrase(N).
noun(n(mama)) --> [mama]. noun(n(kralika)) --> [králika]. verb(v(pekla)) --> [pekla].
Hana Rudová, Logické programování I, 20. dubna 2012 15 Gramaticky uspořádaných klauzulí
Konstrukce derivačního stromu
Pokud však rozšíříme slovník:
noun(n(tata)) --> [tata]. verb(v(pekl)) --> [pekl].
Narazíme na problém se shodou podmetu a prísudku (mimo stávající problém „králíka pekla máma"):
?- sentence(_,[tata, pekla, kralika],[]). yes
?- sentence(_,[mama, pekl, kralika],[]). yes
Proto rozšiřte neterminály o další argumenty (rod, pád)
Hana Rudová, Logické programování I, 20. dubna 201 2
16
Gramaticky uspořádaných klauzulí
Konstrukce derivačního stromu (řešení)
Tento nový argument poskytuje pro odpovídající větnou složku informaci o jejím rodu a pádu - unifikací příslušných proměnných zajistíme shodu v této gramatické kategorii.
sentence(s(N,V)) --> noun_phrase(N, Rod, cl), verb_phrase(V, Rod). noun_phrase(np(N), Rod, Pad) --> noun(N, Rod, Pad). verb_phrase(vp(V), Rod) --> verb(V, Rod).
verb_phrase(vp(V, N), Rod) --> verb(V, Rod), noun_phrase(N, _Rod2, c4).
noun(n(mama), z, cl) --> [mama]. noun(n(tata), mz, cl) --> [tata]. noun(n(kralika), mn, c4) --> [králika]. verb(v(pekla), z) --> [pekla]. verb(v(pekl), mz) --> [pekl].
Hana Rudová, Logické programování I, 20. dubna 201 2
Gramaticky uspořádaných klauzulí
Vestavěné nástroje
operátor --> definován jako ?-op(1200,xfx,-->) .
predikáty ph rase/2, ph rase/3, které slouží k jednoduché tokenizaci
?- phrase(abc,[a,b,c]). % Yes
?- phrase(abc,[a,b,c,d],[d]).        % Yes
Hana Rudová, Logické programování I, 20. dubna 201 2
18
Gramaticky uspořádaných klauzulí