====== DCG ======

===== Uvod =====

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]''.

===== Dvoumnost =====

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.

===== Pomen =====

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, []).

===== Naloge =====

Napiši gramatike v prologu za naslednje jezike:

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