1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
|
<!DOCTYPE html>
<html lang="sl">
<head>
<meta charset="utf-8" />
<title>Prolog: Gramatike (DCG)</title>
<link rel="stylesheet" type="text/css" href="/css/codeq.css" />
<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>
|
