Definite clause grammars (DCG): alternativni zapis predikatov. Primeren za zapis formalnih jezikov (množic besed). Pri tem imamo:

• terminalne simbole
• neterminalne simbole (med njimi en posebni začetni simbol)

Primer: jezik besed s sodim številom a-jev (a^(2n), n ≥ 0).

s --> [].		% s --> [] | [a,a], s.
s --> [a,a], s.

Na levi strani puščice je (en) neterminal, na desni zaporedje terminalov (v oglatih oklepajih) in neterminalov, v katero se prepiše.

Primeri poizvedb (generiranje oz. prepoznavanje besed):

?- s(Word, []).
  [a,a] ;
  [a,a,a,a] ;
  …
?- s([a,a,a], []).
  false.

Narišemo in razložimo drevo izpeljave za [a,a,a,a].

Gramatiki iz uvoda dodamo še pravilo

s --> s, [a,a].

in narišemo še drugo drevo izpeljave za [a,a,a,a]. Poveš, zakaj je dvoumnost slaba (recimo primer iz C-ja

if (…) if (…) A else B,

kjer ne vemo, kateremu if pripada else B).

Razložiš tudi, da gre spet za DFS in da prolog poskuša pravila po vrsti. Prav tako dodaja oz. expanda terminale / neterminale na desni strani puščice.

Jezik, ki opisuje zaporedja golov na nogometni tekmi.

s --> goal.
s --> goal, s.

goal --> [a].
goal --> [b].

% Še dve možnosti za zapis pravil za goal:
%  goal --> [a] | [b].
%  goal --> [X], { memb(X, [a,b]) }.

Dodamo pomen:

goal(1) --> [a].
goal(-1) --> [b].

s(Diff) --> goal(Diff).
s(Diff) --> goal(Diff1), s(Diff2), { Diff is Diff1 + Diff2 }.

Primer poizvedbe:

?- conc(Goals, _, _), s(Result, Goals, []).

Napiši gramatike v prologu za naslednje jezike:

1. jezik a^m b^n, kjer je m,n >= 0
   • primeri besed: [], a, aab, abbb, bbb
2. rožice +++–+++
   • besede, ki pripadajo jeziku, imajo najprej N plusov, potem M minusov in na koncu spet N plusov, N >= 0 in M > 0
3. jezik enomestnih števil (števk/cifer)
   • jezik opisuje množico {0,1,2,3,4,5,6,7,8,9}
4. jezik nenegativnih desetiških števil (lahko z vodilnimi ničlami)
   • primeri besed: 123, 54, 0122, 0001221, 0
5. isto kot prej, vendar brez števil z vodilnimi ničlami (razen števila 0)
   • primeri besed: 123, 54, 122, 1221, 0
6. isto kot prej, z definiranim pomenom: število, ki ga beseda predstavlja
   • primer klica: ?- number(N, [1,2,3,4], [])
7. jezik pravilno gnezdenih oklepajev
8. isto kot prej, z definiranim pomenom: največja globina gnezdenih oklepajev
   • primer klica: ?- paren(D, ['(','(',')',')','(',')'], []).
9. jezik aritmetičnih izrazov, ki vsebujejo števila brez vodilnih ničel
   • dovoljeni operaciji sta + in *; podizraze lahko združujemo z oklepaji
   • primeri besed: (1 + 2) * 3, 42 * 8 * 3, (2 + 1) * (3 + 4)
10. isto kot prej, z definiranim pomenom: vrednost izraza
    • primer klica expr(N, ['(',2,'+',1,')','*','(',3,'+',4,')'], []).