diff options
Diffstat (limited to 'prolog/problems/dcg/intro_sl.html')
| -rw-r--r-- | prolog/problems/dcg/intro_sl.html | 301 |
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> |