aaaaKako 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 slovnici oz. gramatiki. 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).
Gramatiko jezika navadno zapišemo v obliki množice produkcij oz. preslikovalnih pravil. Naredimo to kar na primeru. Imejmo naslednjo množico (dveh) pravil:
s --> []. % pravilo #1 s --> [a,a], s. % pravilo #2
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.
Poglejmo si sestavne dele enega pravila in kako ga razumemo ter uporabljamo. Za
primer vzemimo pravilo #2 zgoraj. Puščica (-->) 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 s s seznamom [a,a] in simbolom
s“. Na enak način pravilo #1 pomeni „zamenjaj simbol
s s praznim seznamom“.
Zakaj so nekatere stvari pisane v seznamih in nekatere ne? Razlika je zelo
pomembna: tistemu, kar je pisano v seznamih (npr. [a,a]), bomo
rekli končni simboli ali terminali, simbolom izven seznamov (npr.
s) 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“.
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:
s --> [] ; [a,a], s.
Oziroma v duhu drugih jezikov za opis gramatik, kot je npr. BNF, tudi takole:
s --> [] | [a,a], s.
Skratka tudi navpičnica pomeni disjunkcijo: neterminal s se lahko
preslika ali v prazen seznam ali pa v seznam dveh terminalov a in
v neterminal s.
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 s, 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.
Primer 1: s --(2)--> aas --(1)--> aa
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 aas, nato pa na tem pravilo #1 (na
neterminalu s, seveda) in dobimo aa.
Ker po drugem koraku nimamo v rezultatu več nobenih nekončnih simbolov, smo
zaključili. Beseda oz. stavek aa je sintaktično pravilen stavek v
jeziku, ki ga definira naša zgornja gramatika.
Primer 2: s --(2)--> aas --(2)--> aaaas --(1)--> aaaa
V tem primeru smo izpeljali stavek aaaa. Če malce pomislimo,
opazimo, da naša gramatika generira prazen stavek (nič a-jev),
aa, aaaa, aaaaaa, itd. Skratka, naši
stavki so vedno sestavljeni iz sodega števila a-jev. Lahko se še
tako trudiš, a ti iz začetnega simbola s ne bo
uspelo izpeljati stavka z lihim številom a-jev. Pravzaprav lahko
ta razmislek peljemo še malce dlje. Vsak stavek lahko izpeljemo le na en sam
način! Za stavek z n a-ji moramo najprej n/2-krat uporabiti
pravilo #2 in na koncu enkrat pravilo #1.
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:
?- s(Word, []). Word = [] ; Word = [a,a] ; Word = [a,a,a,a] ; …
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).
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.
?- s([a,a], []). true ?- s([a,a,a,a,a], []). false
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:
s --> []. % pravilo #1 s --> [a,a], s. % pravilo #2 s --> s, [a,a]. % pravilo #3
Sedaj lahko stavek aaaa izpeljem na več kot en način, npr. takole:
Način 1: s --(2)--> aas --(2)--> aaaas --(1)--> aaaa Način 2: s --(3)--> saa --(2)--> aasaa --(1)--> aaaa
Kaj je v tem tako strašnega? Je morda problem v tem, da imamo več izbire? Ne,
problem je v tem, da isti stavek (aaaa) 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č.
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.
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.
aaaa
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 a v prejšnjem primeru, a želimo, da se vse črke
vedno podvajajo.
s --> []. % pravilo #1
s --> letter, s. % pravilo #2
letter --> [X,X], { member(X, [a,b,c,d, …, z]) }. % pravilo #3
Pravilo #3 je zanimivo: velike črke nam kot vedno v prologu tudi tu
predstavljajo spremenljivke. Rezultat tega pravila je seznam oblike
[X,X]. S predikatom member/2 pa generiramo vse
možnosti za X: v tem primeru vse črke abecede od a do
z. Predikat member/2 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.
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.
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.
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.
Definirajmo gramatiko, ki sprejme/generira poljubno zaporedje črk
a in b, njen pomen pa naj bo razlika v številu teh
črk. Z malo domišljije lahko rečemo, da gre za izid nogometne tekme:
a pomeni gol prve ekipe, b pa gol druge ekipe.
Neterminal game naj bo začetni simbol te gramatike.
game(0) --> [].
game(Diff) --> goal(Diff1), game(Diff2), {Diff is Diff1 + Diff2}.
goal( 1) --> [a].
goal(-1) --> [b].
Pomen lahko razumemo takole. Če je tekma brez golov (oz. ko v rekurziji pridemo
do praznega seznama golov), je razlika 0. Vsak a pomeni gol za
prvo ekipo in je vreden +1, vsak b 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 Diff1 in
Diff2.
Primer uporabe:
?- game(Diff, [a,b,a,a], []). % končni rezultat 3-1 za prvo ekipo Diff = 2.