Grammatikad

Eespoolvaadeldud näidetes kasutati keelte (märgijadade hulkade) defineerimisel kaht liiki märke :

Lisaks terminalidele ja mitteterminalidele on defineerimisel tarvis veel produktsioone ja algussümbolit (mitteterminal), millest defineerimine algab. Need kõik kokku moodustavad formaalse grammatika, seega grammatika on nelik (T, V, A, P), kus

Terminalid on "lõplikud", s.t. grammatika ülesanne on kirjeldada ainult terminalidest koosnevaid jadasid. Mitteterminalid on vaid abimõisted, mis on kasulikud terminalidest moodustatud stringide struktuuri selgitamiseks, näiteks reaalarv 3.14 koosneb täisosast 3, reaalosa eraldajast . ja reaalosast 14; täis- ja reaalosa ise on (oma struktuurilt) täisarvud.

Eespoolvaadeldud näidetes oli produkstioonides v v' produktsiooni vasak pool v alati vaid üks mitteterminal, kuid alati see ei pea nii olema, üldjuhul võivad v, v' olla igasugused terminalidest ja mitteterminalidest koostatud sõnad.

Produktsioon p: v noolv' genereerib sõnast w sõna w', kui sõnu w, w' saab esitada kujul w = uvz, w' = uv'z (s.t. sõnad v, v' on vastavalt sõnade w, w' alamsõnad, u ja v on suvalised sõnad); öeldakse ka, et w' on saadud sõnast w produktsiooni p rakendamisega ja tähistatakse w p w'.
Noole asemel kasutatakse mõnikord ka muid sümboleid, näiteks programmeerimiskeele süntaksi kirjeldamisel (nn. Bacus-Nauri valemites) kasutatakse sageli sümbolit ::= .

Näide 1. Produktsioonisüsteem {a noolab, ab nool ba} genereerib sõnast ab kõikvõimalikus sõnad, kus on sama arv a-sid ja b-sid, s.t. keele (sõnade hulga) {w | |w|a = |w|b}

Näide 2. Produktsioonisüsteem {A nool B0, B nool B1, B nool B0, B nool } (viimase produktsiooni parem pool on tühi) genereerib algussümbolist A kõikvõimalikud binaarjadad, mis lõpevad 0-ga. Eespool oli sama keel kirjeldatud teistsuguste abimõiste ja teistsuguste produktsiooonidega, s.t. teistsuguse grammatikaga ja selline olukord esineb sageli: sama keelt võib kirjeldada väga erinevate grammatikatega.

Produktsioonisüsteem P genereerib (terminalidest ja mitteterminalidest koosnevast) sõnast w sõna w', kui leidub derivatsioon

w p1 w1 p2 w2 ... pn wn = w'

kus produktsioonid p1, p2,..., pn kuuluvad produkstioonisüsteemi P; lühemalt tähistatakse seda mõnikord ka nii: w *P w' .

Konkreetset produktsiooni või produktsioonisüsteemi tähistav alaindeks jäetakse sümbolites p , P sageli ära, kui kontekstist on arusaadav, millist produktsiooni või produktsioonisüsteemi mõeldakse, s.t. derivatsiooni tähistatakse lihtsalt w w1 w2 ... wn = w' ehk lühemalt w * w'.

Grammatika G = (T, V, A, P) genereerib keele
L(G) = {w | w T*, X * w}, s.t. nende ainult terminalidest koosnevate jadade hulga, mida saab algussümbolist produktsioonide abil genereerida.

Näide 1. Kui reaalarvudeks lugeda vaid numbrite jadasid, milles esineb reaalosa eraldaja '.' ja mille ees võib esineda märk + või - (märk võib ka puududa), siis genereeriks reaalarvud grammatika G = (T, V, A, P), kus

T = {0,1,2,3,4,5,6,7,8,9, '.', +,-}
V = {Number, Int, Real, Märk}

A = Real
P = {Number 0|1|2|3|4|5|6|7|8|9
Int Number | Int Number
Real Int . Int | Märk Int . Int
Märk + | - }

Arvutites esitatakse kõik suurused arvudega - ka tähed, numbrid, kõik klaviatuurilt valitavad märgid jne. Tähtede, numbrite ja teiste märkide numbritega kodeerimiseks on mitmesuguseid koodeerimissüsteeme, kuid valdavalt tuntuim on ASCII (American Standard Code for Information Interchange), milles näiteks numbrite 0, 1, ... 9 koodid on järjestikused täisarvud vahemikus 48..57, suurtähtede A,B,...,Z (inglise tähestiku 26 tähte) koodid on vahemikus 65..90 ja väiketähtede a,b,...,z koodid 97..122. Esituse kompaktsemaks muutmiseks kasutatakse ASCII-koodidel põhinevat märgistiku järjestust (arvutites töödeldavates) grammatikates sageli märkide vahemike tähistamiseks, näiteks loetelu 0|1|2|3|4|5|6|7|8|9 asemel kirjutatakse 0..9, seega eelnevas näites võiks esimese produktsiooni kirjutada ka kujul Number 0..9.

Näide 2. Enamuses programmeerimiskeeltest defineeritakse identifikaator (muutuja) kui tähtedest ja numberitest koosnev jada, mis peab algama tähega ja milles ei või esineda tühikuid ega muid märke. Tavaliselt  kasutatakse vaid inglise tähestiku tähti, seega võib identifikaatorid genereerida grammatikaga G = (T, V, A, P), kus

T = {a..z, A..Z, 0..9}
V = {Ident, Täht, Number}
A = Ident
P = {Täht a..z | A..Z
Number 0..9
Ident Täht | Ident(Täht | Number)}

Viimases produktsioonis esineb mitteterminal Ident rekursiivselt, mis võimaldabki genereerida pärast esimest tähte igasuguse tähtedest-numbritest koosneva jada ehk hulga, mida tähistab rekursiivne avaldis (Täht|Number)*, seega võiks viimase produktsiooni tähistada kompaktsemalt Ident  Täht(Täht|Number)*.

Näide 3. Ainult liitmis-lahutamisoperatsiooni (Op) kasutavad aritmeetilised avaldised (Expr) täisarvudega genereerib grammatika G = (T, V, A, P), milles:

T = {0..9, +, -}
V = {Int, Expr, Op}
A = Expr
P = {Int (0..9)+
Op + | -
Expr Int (Op Int)* }

Näide4. Kooli tunniplaan on nädala tööpäevade jaoks koostatud loetelu nelikutest Aine-Tunni_algus-Ruum-Klass. Sellise andmestruktuuri võib kirjeldada grammatikaga G = (T, V, A, P), kus ( väga väheste ainete ja klasside jaoks):

T = { Esmaspäev .. Reede, Ajalugu | Matemaatika | Eesti keel | 8.00 | 10.00 | 12.00 | 101 | 102 | 201 | 202 | 9a | 9b }
V = {Tunniplaan, Päev, Aine, Aeg, Ruum, Klass}
A = Tunniplaan
P = {Tunniplaan (Päev Aine Aeg Ruum Klass)+
Päev Esmaspäev.. Reede
Aine Matemaatika | Ajalugu | Eesti keel
Aeg 8.00 | 10.00 | 12.00
Ruum = 101 | 102 | 201 | ...
Klass = 9a | 9b }

Ülesandeid:
1. Raamat koosneb esi- ja tagakaanest, mille vahel on tiitelleht, sisukord ja peatükid; iga peatükk algab pealkirjaga, seejärel on lühikokkuvõte mõned paragrahvid. Koosta grammatika raamatu struktuuri kirjeldamiseks, kasutades mõisteid (terminale) {esikaas, tagakaas, tiitelleht, sisukord, kokkuvõte, leht}.
2. Koosta grammatika kooli (ülikooli) tunniplaani struktuuri kirjeldamiseks; tunniplaan lihtsa programmeerimiskeele süntaksi (s.t. selles keeles kirjutatud süntaktiliselt korrektse programmi) kirjeldamiseks. Tunniplaani näide:
Esmaspäev 8.00-9.30 LA-41 Loogiline Programmeerimine Jaak Henno AK-140 Loeng
Esmaspäev 10.00-11.30 LA-41 Loogiline Programmeerimine Jaak Henno AK-111 Harjutus
Kolmapäev 8.00-9.30   Translaatorite koostamine Jaak Henno AK-140 Loeng
Grammatika peab lubama tööpäeva, kellaaja, õpperühma ja ruumi formaate ainult sellistena nagu näites.
3. Auditoorium koosneb ridadest; reas on lauad ja nende järel toolid (toolide-laudade arv reas pole vastavuses). Koosta grammatika auditooriumi struktuuri kirjeldamiseks mõistete (terminalide) laud, tool abil.
4. Koosta grammatika telefoniraamatu kirjeldamiseks, kui telefoniraamatu sissekanded peavad olema kujul:
Jakobson, Aino Paldiski mnt 20,13518 Tallinn (372) 621 0323
Kala, K. Sõpruse pst 36,13814 Tallinn 631 4183
Toober, Toomas Tuuliku tee 4c, 10621 Tallinn (372) 5152 3058
Svensson, I. Karlskronavägen 4c, 37192 Stockholm (46) 866 328 2822
5. Linnuvaatleja päevaprotokoll algab kuupäevaga; selle järel on iga linnu jaoks rida, kus algul on linnu nimi (kuldnokk, vares, lõoke, jaanalind) ja seejärel komadega eraldatud loetelu, kus iga element on kas täisarv (korraga lendasid üle 3 varest) või mingi arv püstkriipse | (kuldnokad lendasid üle ühekaupa, iga linnu ajal tõmbas vaatleja püstkriipsu); täisarvude ja täisarvu ja püstkriipsu vahel peab kõikjal olema koma (muidu võiks püstkriipsu tõlgendada täiearvu järele või ette kirjutatud number 1-na; püstkriipsude vahel võib koma olla, kuid võib ka puududa.. Koosta grammatika linnuvaatleja päevaprotokolli kirjeldamiseks.
6. Koosta võimalikult lihtne grammatika, mis genereeriks kõik avaldised kujul

|n+ |m = |n+m
n,m>0

(kahe ühendsüsteemis kirjutatud arvu liitmine), s.t. sellesse keelde kuuluks (näiteks) jadad |+|| = |||, |||+| = ||||
7. Koosta võimalikult lihtne grammatika, mis genereeriks kõik avaldised kujul

|n1+ |n2+ |n3+... = |n1+n2+n3+...
n,m>0

(ükskõik mitme ühendsüsteemis kirjutatud arvu liitmine), s.t. sellesse keelde kuuluks (näiteks) jadad |+|| = |||, |+||+||+||| = |||||||| jne. Kas see keel on regulaarne? Kas see keel on kontekstivaba?
8. Antud on aritmeetilisi avaldisi genereeriv grammatika:

id (A..Z | a..z)+
arv (0..9)+
mult *
div /
plus +
minus -
pleft (
pright )
exp exp plus exp
| exp minus exp | exp mult exp | exp div exp | pleft exp pright | id | arv

Algussümbol on exp. Kirjuta mõned selle grammatika abil genereeritavad avaldised, kus oleks (vähemalt kord) kasutatud kõiki produktsioone.
10. Koostada (minimaalne) grammatika ja lõplik (deterministlik) automaat muutujate ja tüübideklaratsioonide kirjeldamiseks C-keeles, mis lubaks järgmisi näiteid (kuid grammatika peab lubama ka teisi analoogilisi deklaratsioone!)

int x;
int blue = 5;
double x = 0.0 , y = 3.14;
float y, number = 3.14;
char *txt;
int a[10][10];

11. Koosta kontekstivaba grammatika C-keele sisend-väljundlausete scanf, printf süntaksi kirjeldamiseks; grammatika peab suutma kirjeldada (näiteks) selliseid lauseid:

printf("Kokku = %-10.4d\nKasum = %d\n", total, profit);
scanf("%d %s", &mitu, nimed);

12. Järgnevas on kolm näidet VoiceXML-keelest: 1.

<form id="shopping">
< if cond="total > 1000">
<prompt> This is too much to spend.</prompt>
</if>
</form>

2.

<form id="debit">
<if cond="amount < 29.95">
<goto next="#debit"/>
<else />
<prompt>You are out of cash. </prompt>
</if>
</form>

3.

<form id="icecream">
<if cond="flavor == 'vanilla'">
<prompt> You ordered vanilla. </prompt>
<elseif cond="flavor == 'chocolate'" />
<prompt> You ordered chocolate. </prompt>
<else />
<prompt> You didn't order vanilla or chocolate. </prompt>
</if>
</form>

Koosta kontekstivaba või regulaarne grammatika, mis kirjeldaks ülalesitatud näidete süntaksit ja võimaldaks genereerida ka teisi analoogilisi VoiceXML-tekste.

12. Installatsiooniprogrammi "Inno Setup" installatsiooniskript koosneb järgmistest osadest:

Sektsioonid - algavad alati sektsiooninimega, mis on [,] vahel, näit [Setup], [Files], [Icons] jne

Edasi tulevad sektsiooni direktiivid. Sektsioonide ja sektsioonides dirktiivide järjekord pole oluline; ka kommentaare (reakommentaarid, algavad semikooloniga ; ) võib paigutada ükskõik kuhu.

Sektsioonis [Setup] järgnevad direktiivid (käsud), mille esimene sõna on muutuja (AppName, AppVerName, AppCopyright, DefaultDirNAme, DefaultGroupName, UninstallDisplayIcon; neist AppName, AppVerName, DefaultDirName on kohustuslikud, ülejäänud võivad ka puududa), seejärel "=" ja siis vastav info (string).

Teistes sektsioonides on dirktiivid mitmeosalised; osa struktuur on selline:

Muutuja : Väärtus

näiteks Source: "MyProg.exe"; DestDir: "{app}".

Väärtused on kõikjal stringid; nende esimene element võib olla ka figuursulgude {...} vahele võetud konstant: {pf}, {app}, {group}, {commonprograms},{userdesktop}.

Koosta (võimalikult minimaalne) grammatika, mis kirjeldaks järgnevaid kahte skripti näidet.

Näide 1.

; -- Sample1.iss --
; Demonstrates copying 3 files and creating an icon.
; SEE THE DOCUMENTATION FOR DETAILS ON CREATING .ISS SCRIPT FILES!

[Setup]
AppName=My Program
AppVerName=My Program version 1.5
AppCopyright=Copyright (C) 1997-2000 My Company, Inc.
DefaultDirName={pf}\My Program
DefaultGroupName=My Program
UninstallDisplayIcon={app}\MyProg.exe
; uncomment the following line if you want your installation to run on NT 3.51 too.
; MinVersion=4,3.51

[Files]
Source: "MyProg.exe"; DestDir: "{app}"
Source: "MyProg.hlp"; DestDir: "{app}"
Source: "Readme.txt"; DestDir: "{app}"; Flags: isreadme

[Icons]
Name: "{group}\My Program"; Filename: "{app}\MyProg.exe"

Näide 2

; Same as Sample1.iss, but creates its icon in the Programs folder of the
; Start Menu instead of in a subfolder, and also creates a desktop icon.
; SEE THE DOCUMENTATION FOR DETAILS ON CREATING .ISS SCRIPT FILES!

[Setup]
AppName=My Program
AppVerName=My Program version 1.5
AppCopyright=Copyright (C) 1997-2000 My Company, Inc.
DefaultDirName={pf}\My Program
DisableProgramGroupPage=yes
; ^ since no icons will be created in "{group}", we don't need the wizard
; to ask for a group name.
UninstallDisplayIcon={app}\MyProg.exe

[Files]
Source: "MyProg.exe"; DestDir: "{app}"
Source: "MyProg.hlp"; DestDir: "{app}"
Source: "Readme.txt"; DestDir: "{app}"; Flags: isreadme

[Icons]
Name: "{commonprograms}\My Program"; Filename: "{app}\MyProg.exe"
Name: "{userdesktop}\My Program"; Filename: "{app}\MyProg.exe"

13. Autokuulutused
Küsimused, probleemid: ©2004-2013 Jaak Henno