Prolog: add introduction for DCG group

author: Timotej Lazar <timotej.lazar@fri.uni-lj.si> 2016-05-18 19:30:33 +0200
committer: Timotej Lazar <timotej.lazar@fri.uni-lj.si> 2016-05-18 19:33:14 +0200
commit: 4973979e40dfdc26dafe1cdeddf8e0bce859ba5d (patch)
tree: 58fd0d205f6ac20f3bf5a52cf6247b5fa577589f /prolog/problems/dcg/intro_sl.html
parent: 025254ce93f7ce8b4d175dcb85d228506202583c (diff)
1 files changed, 301 insertions, 0 deletions
diff --git a/prolog/problems/dcg/intro_sl.html b/prolog/problems/dcg/intro_sl.html
new file mode 100644
index 0000000..ae94e73
--- /dev/null
+++ b/prolog/problems/dcg/intro_sl.html
@@ -0,0 +1,301 @@
+<!DOCTYPE html>
+<html lang="sl">
+<head>
+    <meta charset="utf-8" />
+    <title>Prolog: Gramatike (DCG)</title>
+    <link rel="stylesheet" type="text/css" href="../style.css" />
+</head>
+<body>
+
+<h1>Prolog: Gramatike (DCG)</h1>
+<p>
+Kako se ljudje sporazumevamo med seboj? Z jeziki, seveda. No, saj obstajajo
+tudi drugi načini komunikacije, a je vendarle jezik tisti osrednji,
+najpogostejši, način. In kako se sporazumevamo z računalnikom, kako mu
+razložimo, kaj naj naredi? Prav tako z jeziki, pa čeprav programskimi. Saj tako
+velike razlike med naravnimi in programskimi jeziki niti ni, le da so slednji
+bolj formalizirani, bolj natančni, bi lahko rekli. In prav vsi jeziki temeljijo na
+<em>slovnici</em> oz. <em>gramatiki</em>. Ta natančno opredeli, katere besede
+(včasih jim pravimo tudi stavki) so slovnično pravilne (so elementi jezika) in
+katere niso (niso elementi danega jezika).
+</p>
+
+<p>
+Gramatiko jezika navadno zapišemo v obliki množice produkcij oz. preslikovalnih
+pravil. Naredimo to kar na primeru. Imejmo naslednjo množico (dveh) pravil:
+</p>
+<pre>
+s --> [].           % pravilo #1
+s --> [a,a], s.     % pravilo #2
+</pre>
+<p>
+Medklic: Pravila načeloma niso videti kot prologov program, a v resnici jih
+prolog razume in interno pretvori v kodo, kot si je vajen. A danes se v to ne
+bomo spuščali, ker niti ni pomembno.
+</p>
+
+<p>
+Poglejmo si sestavne dele enega pravila in kako ga razumemo ter uporabljamo. Za
+primer vzemimo pravilo #2 zgoraj. Puščica (<code>--></code>) nam pravilo
+razdeli na levi in desni del. Pomeni pa naslednje: simbol na levi strani
+preslika v to, kar je na desni. Torej naše konkretno pravilo pomeni „zamenjaj
+simbol <code>s</code> s seznamom <code>[a,a]</code> in simbolom
+<code>s</code>“. Na enak način pravilo #1 pomeni „zamenjaj simbol
+<code>s</code> s praznim seznamom“.
+</p>
+
+<p>
+Zakaj so nekatere stvari pisane v seznamih in nekatere ne? Razlika je zelo
+pomembna: tistemu, kar je pisano v seznamih (npr. <code>[a,a]</code>), bomo
+rekli končni simboli ali terminali, simbolom izven seznamov (npr.
+<code>s</code>) pa nekončni simboli oz. neterminali. Nekončne simbole gramatike
+moramo vedno preslikati še naprej, medtem ko končnih simbolov ne moremo več
+preslikati naprej – od tu tudi njihovo poimenovanje. Ko si nekoč v šoli delal
+stavčno analizo pri pouku slovenščine, si stavek verjetno razdelil na
+samostalnik, glagol in podobne sintaktične elemente – to so nekončni simboli.
+Končni simboli pa so konkretni primeri teh elementov: npr. glagol
+„programirati“.
+</p>
+
+<p>
+DCG je le en izmed možnih zapisov gramatike. Na levi strani pravil v DCG se
+vedno pojavlja en in samo en nekončni simbol. Na desni strani je lahko poljubno
+zaporedje končnih in nekončnih simbolov, ločenih z vejicami. Slednje pomenijo
+konjunkcijo, kot smo že vajeni. Pravil je lahko poljubno mnogo – katero bomo
+uporabili v nekem konkretnem primeru, je stvar izbire. Ko smo že pri
+konjunkciji: podpičje tudi tu pomeni disjunkcijo. Zgornji dve pravili bi lahko
+zapisali tudi takole:
+</p>
+<pre>
+s --> [] ; [a,a], s.
+</pre>
+<p>
+Oziroma v duhu drugih jezikov za opis gramatik, kot je npr. BNF, tudi takole:
+</p>
+<pre>
+s --> [] | [a,a], s.
+</pre>
+
+<p>
+Skratka tudi navpičnica pomeni disjunkcijo: neterminal <code>s</code> se lahko
+preslika ali v prazen seznam ali pa v seznam dveh terminalov <code>a</code> in
+v neterminal <code>s</code>.
+</p>
+
+<p>
+Prav, sedaj poznamo obliko zapisa. Kaj pa lahko s tem počnemo oz. kakšno
+povezavo ima to z jeziki? Pri vsaki gramatiki imamo tipično določen tudi nek
+začetni nekončni simbol, pri našem primeru bo to kar simbol <code>s</code>, ki
+je tudi edini nekončni simbol. Izpeljavo poljubne besede oz. stavka v jeziku
+začnemo s tem simbolom in na njem v poljubnem redu uporabljamo preslikovalna
+pravilo dokler ne dobimo rezultata sestavljenega samo iz končnih simbolov.
+Poglejmo nekaj primerov.
+</p>
+
+<pre>
+Primer 1: <strong>s</strong> --(2)--> aa<strong>s</strong> --(1)--> aa
+</pre>
+
+<p>
+Za lažji prikaz so odebeljeno prikazani nekončni simboli, z normalno pisavo pa
+končni simboli. V prvem primeru na začetnem simbolu najprej uporabimo pravilo
+#2 in dobimo <code>aa<strong>s</strong></code>, nato pa na tem pravilo #1 (na
+neterminalu <code><strong>s</strong></code>, seveda) in dobimo <code>aa</code>.
+Ker po drugem koraku nimamo v rezultatu več nobenih nekončnih simbolov, smo
+zaključili. Beseda oz. stavek <code>aa</code> je sintaktično pravilen stavek v
+jeziku, ki ga definira naša zgornja gramatika.
+</p>
+
+<pre>
+Primer 2: <strong>s</strong> --(2)--> aa<strong>s</strong> --(2)--> aaaa<strong>s</strong> --(1)--> aaaa
+</pre>
+
+<p>
+V tem primeru smo izpeljali stavek <code>aaaa</code>. Če malce pomislimo,
+opazimo, da naša gramatika generira prazen stavek (nič <code>a</code>-jev),
+<code>aa</code>, <code>aaaa</code>, <code>aaaaaa</code>, itd. Skratka, naši
+stavki so vedno sestavljeni iz sodega števila <code>a</code>-jev. Lahko se še
+tako trudiš, a ti iz začetnega simbola <code><strong>s</strong></code> ne bo
+uspelo izpeljati stavka z lihim številom <code>a</code>-jev. Pravzaprav lahko
+ta razmislek peljemo še malce dlje. Vsak stavek lahko izpeljemo le na en sam
+način! Za stavek z n <code>a</code>-ji moramo najprej n/2-krat uporabiti
+pravilo #2 in na koncu enkrat pravilo #1.
+</p>
+
+<p>
+Preden to misel razvijemo naprej, naj odgovorim še na vprašanje, kako lahko
+zgornje stvari poskusiš v prologu. Preposto, zgornjo gramatiko prepišeš kot
+program (kar v resnici je!) in poganjaš poizvedbe v konzoli takole:
+</p>
+<pre>
+?- s(Word, []).
+Word = [] ;
+Word = [a,a] ;
+Word = [a,a,a,a] ;
+…
+</pre>
+
+<p>
+Poizvedbo torej pokličeš z začetnim simbolom (ki ga prolog v resnici interno
+prevede v predikat, kot si jih vajen), ki mu podaš dva argumenta. V bistvu je
+ta par argumentov en sam argument, ki tvori besedo (oz. stavek), ki jo bo
+gramatika generirala. Zakaj tak zapis z dvema seznamoma? Gre za razliko
+seznamov – če drugega pustiš praznega, bo prvi ostal tak, kot je; tako bomo
+večinoma pustili. Tak zapis je posledica učinkovite implementacije. Ko prolog
+generira besede nekega jezika, to počne s konkatenacijo seznamov. Za slednjo si
+videl, da je časovne zahtevnosti O(n), a se jo da s trikom razlike seznamov
+narediti v času O(1).
+</p>
+
+<p>
+Kot si že vajen, stvari delujejo v več smeri. Zgoraj smo gramatiko uporabili za
+generiranje besed jezika. Bolj običajna uporaba pa je v drugi smeri:
+računalniški prevajalniki tipično preverjajo, ali je podana beseda sintaktično
+pravilna. To pomeni, ali jo lahko izpeljemo z uporabo pravil dane gramatike.
+Spodnji poizvedbi sta tak primer uporabe.
+</p>
+
+<pre>
+?- s([a,a], []).
+true
+?- s([a,a,a,a,a], []).
+false
+</pre>
+
+<h2>Dvoumnost gramatik</h2>
+<p>
+Zakaj smo posebej izpostavili, da lahko nek stavek izpeljemo le na en način?
+Ker je to verjetno ena najpomembnejših lastnosti gramatik! Predpostavimo, da
+imamo poleg zgornjih dveh pravil še tretje:
+</p>
+<pre>
+s --> [].          % pravilo #1
+s --> [a,a], s.    % pravilo #2
+s --> s, [a,a].    % pravilo #3
+</pre>
+
+<p>
+Sedaj lahko stavek <code>aaaa</code> izpeljem na več kot en način, npr. takole:
+</p>
+<pre>
+Način 1: <strong>s</strong> --(2)--> aa<strong>s</strong> --(2)--> aaaa<strong>s</strong> --(1)--> aaaa
+Način 2: <strong>s</strong> --(3)--> <strong>s</strong>aa --(2)--> aa<strong>s</strong>aa --(1)--> aaaa
+</pre>
+
+<p>
+Kaj je v tem tako strašnega? Je morda problem v tem, da imamo več izbire? Ne,
+problem je v tem, da isti stavek (<code>aaaa</code>) lahko pomeni več stvari.
+Če računalniku rečeš „Prištej ena.“, ne želiš, da to pomeni več različnih
+stvari, kajne? Predstavljaj si, da bi te računalnik razumel malce po svoje: saj
+bi bilo zabavno, ampak jaz si tako sprogramiranega avtopilota na primer ne
+želim kaj preveč.
+</p>
+
+<p>
+Omenili smo pomen in da je pomen tesno povezan z izpeljavo (zaporedjem uporabe
+konkretnih preslikovalnih pravil gramatike). Tako je, kasneje bomo videli, da
+tipično vsaki preslikavi pripišemo pomen.
+</p>
+
+<p>
+Izpeljavo besed v jeziku tipično predstavimo z drevesi izpeljave. Tako bolj
+pregledno pokažemo tisto kar smo zgoraj naredili s puščicami v eni vrstici. Pri
+več neterminalih tako točno vemo kateri neterminal smo preslikali v kaj.
+Primera zgornjih izpeljav sta podana spodaj. Končni rezultat preberemo z levim
+obhodom drevesa, posamezne sezname pa konkateniramo med seboj.
+</p>
+
+<figure>
+    <img src="syntax_tree.svg" />
+    <figcaption>Različni drevesi izpeljave za besedo <code>aaaa</code></figcaption>
+</figure>
+
+<h2>Dodajanje kode v gramatiko</h2>
+<p>
+Ker v našem primeru gramatiko uporabljamo znotraj programskega jezika
+(prologa), nam seveda pride na misel, da bi lahko znotraj gramatike uporabili
+tudi običajne prologove predikate. To je dejansko mogoče in nam v nekaterih
+primerih pride precej prav. Poglejmo, kako to naredimo na naslednjem primeru.
+Recimo, da želimo definirati gramatiko za jezik, kjer imamo večjo izhodno
+abecedo kot samo <code>a</code> v prejšnjem primeru, a želimo, da se vse črke
+vedno podvajajo.
+</p>
+
+<pre>
+s --> [].                                               % pravilo #1
+s --> letter, s.                                        % pravilo #2
+letter --> [X,X], { member(X, [a,b,c,d, …, z]) }.       % pravilo #3
+</pre>
+
+<p>
+Pravilo #3 je zanimivo: velike črke nam kot vedno v prologu tudi tu
+predstavljajo spremenljivke. Rezultat tega pravila je seznam oblike
+<code>[X,X]</code>. S predikatom <code>member/2</code> pa generiramo vse
+možnosti za <code>X</code>: v tem primeru vse črke abecede od <code>a</code> do
+<code>z</code>. Predikat <code>member/2</code> smo zapisali znotraj zavitih
+oklepajev. V tem primeru ne gre za omejitve kot pri CLP(R), ampak prologu na ta
+način povemo, da gre za običajno prologovsko kodo. Tako lahko uporabljamo
+poljubne predikate znotraj pravil DCG. Celo CLP(R) lahko uporabimo, tako da
+znotraj zavitih oklepajev zapišemo še ene zavite oklepaje.
+</p>
+
+<h2>V kakšnem vrstnem redu prolog bere pravila?</h2>
+<p>
+Vrstni red uporabe pravil je tak, kot smo ga že vajeni pri prologu. Ta poskuša
+pravila za posamezni neterminal od zgoraj navzdol. In poskuša vse, torej zopet
+generira vse možne izpeljave eno za drugo z mehanizmom vračanja, če seveda tako
+zahtevamo.
+</p>
+
+<p>
+Vrstni red preslikave znotraj posameznega pravila je od leve proti desni.
+Vrstni red je pomemben. Kodo (z zavitimi oklepaji) lahko vključimo na poljubno
+mesto in jo ločimo z vejicami. Izvedla se bo takrat, ko bo prolog nanjo
+naletel, torej zopet od leve proti desni.
+</p>
+
+<h2>Dodatni argumenti in pomen</h2>
+<p>
+Nekončnim simbolom gramatike lahko dodajamo dodatne argumente. Ti nam lahko
+služijo za različne stvari, a največkrat z njimi definiramo pomen besed, ki jih
+generira oz. razpozna dana gramatika.
+</p>
+
+<p>
+Definirajmo gramatiko, ki sprejme/generira poljubno zaporedje črk
+<code>a</code> in <code>b</code>, njen pomen pa naj bo razlika v številu teh
+črk. Z malo domišljije lahko rečemo, da gre za izid nogometne tekme:
+<code>a</code> pomeni gol prve ekipe, <code>b</code> pa gol druge ekipe.
+Neterminal <code>game</code> naj bo začetni simbol te gramatike.
+</p>
+
+<pre>
+game(0) --> [].
+game(Diff) --> goal(Diff1), game(Diff2), {Diff is Diff1 + Diff2}.
+goal( 1) --> [a].
+goal(-1) --> [b].
+</pre>
+
+<p>
+Pomen lahko razumemo takole. Če je tekma brez golov (oz. ko v rekurziji pridemo
+do praznega seznama golov), je razlika 0. Vsak <code>a</code> pomeni gol za
+prvo ekipo in je vreden +1, vsak <code>b</code> pa gol za drugo ekipo in je
+vreden -1. Pravilo, da je tekma sestavljena iz gola in potem še poljubno golov
+v nadaljevanju, pa pove, da je razlika taka kot je v nadaljevanju, ki ji
+prištejemo še vrednost gola: plus ali minus 1. Kot vidiš, je precej podobno,
+kot če bi to sprogramili v prologu z rekurzijo. Pravzaprav se prevede v točno
+to! Pomembno je, da smo dali kodo znotraj zavitih oklepajev na konec pravila
+#2. Do takrat namreč že izvemo vrednosti za <code>Diff1</code> in
+<code>Diff2</code>.
+</p>
+
+<p>
+Primer uporabe:
+</p>
+<pre>
+?- game(Diff, [a,b,a,a], []).       % končni rezultat 3-1 za prvo ekipo
+Diff = 2.
+</pre>
+
+</body>
+</html>
author	Timotej Lazar <timotej.lazar@fri.uni-lj.si>	2016-05-18 19:30:33 +0200
committer	Timotej Lazar <timotej.lazar@fri.uni-lj.si>	2016-05-18 19:33:14 +0200
commit	4973979e40dfdc26dafe1cdeddf8e0bce859ba5d (patch)
tree	58fd0d205f6ac20f3bf5a52cf6247b5fa577589f /prolog/problems/dcg/intro_sl.html
parent	025254ce93f7ce8b4d175dcb85d228506202583c (diff)