From 4973979e40dfdc26dafe1cdeddf8e0bce859ba5d Mon Sep 17 00:00:00 2001 From: Timotej Lazar Date: Wed, 18 May 2016 19:30:33 +0200 Subject: Prolog: add introduction for DCG group --- prolog/problems/dcg/intro_sl.html | 301 ++++++++++++++++++++++++++++++++++++ prolog/problems/dcg/sl.py | 7 +- prolog/problems/dcg/syntax_tree.dot | 40 +++++ prolog/problems/dcg/syntax_tree.svg | 133 ++++++++++++++++ 4 files changed, 480 insertions(+), 1 deletion(-) create mode 100644 prolog/problems/dcg/intro_sl.html create mode 100644 prolog/problems/dcg/syntax_tree.dot create mode 100644 prolog/problems/dcg/syntax_tree.svg (limited to 'prolog/problems') 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 @@ + + + + + Prolog: Gramatike (DCG) + + + + +

Prolog: Gramatike (DCG)

+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 +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
+

+ +

Dvoumnost gramatik

+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. +

+ +

Različni drevesi izpeljave za besedo `aaaa`

+ +

Dodajanje kode v gramatiko

+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. +

+ +

V kakšnem vrstnem redu prolog bere pravila?

+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. +

+ +

Dodatni argumenti in pomen

+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.
+

+ + + diff --git a/prolog/problems/dcg/sl.py b/prolog/problems/dcg/sl.py index 2e5a381..3c1deb7 100644 --- a/prolog/problems/dcg/sl.py +++ b/prolog/problems/dcg/sl.py @@ -1,2 +1,7 @@ name = 'Gramatike (DCG)' -description = 'Sestavljanje in testiranje gramatik, od preprostih do precej realističnih; podlaga za prevajalnike.' +description = '''\ +

+Gramatike +– sestavljanje in testiranje gramatik, od preprostih do precej realističnih; +podlaga za prevajalnike. +

''' diff --git a/prolog/problems/dcg/syntax_tree.dot b/prolog/problems/dcg/syntax_tree.dot new file mode 100644 index 0000000..54238d2 --- /dev/null +++ b/prolog/problems/dcg/syntax_tree.dot @@ -0,0 +1,40 @@ +digraph { + ordering=out; + pad=0; + ranksep=0.3; + + node [fontname="sans",height=0.2,penwidth=0]; + edge [fontname="sans",fontsize=8,arrowsize=0.6]; + + subgraph { + sa1 [label="s"]; + sa2 [label="s"]; + sa3 [label="s"]; + + aa1 [label="aa",fontname="mono"]; + aa2 [label="aa",fontname="mono"]; + ea [label="[]",fontname="mono"]; + + sa1 -> aa1 [label=" 2"]; + sa1 -> sa2 [label=" 2"]; + sa2 -> aa2 [label=" 2"]; + sa2 -> sa3 [label=" 2"]; + sa3 -> ea [label=" 1"]; + } + + subgraph { + sb1 [label="s"]; + sb2 [label="s"]; + sb3 [label="s"]; + + ab1 [label="aa",fontname="mono"]; + ab2 [label="aa",fontname="mono"]; + eb [label="[]",fontname="mono"]; + + sb1 -> sb2 [label=" 3"]; + sb1 -> ab1 [label=" 3"]; + sb2 -> ab2 [label=" 2"]; + sb2 -> sb3 [label=" 2"]; + sb3 -> eb [label=" 1"]; + } +} diff --git a/prolog/problems/dcg/syntax_tree.svg b/prolog/problems/dcg/syntax_tree.svg new file mode 100644 index 0000000..a1a8083 --- /dev/null +++ b/prolog/problems/dcg/syntax_tree.svg @@ -0,0 +1,133 @@ + + + + + -- cgit v1.2.1