v



Grammatikad

Keel defineeritakse grammatikaga - see on produktsioonidest koosnev genereerimissüsteem, mis genereerib kõik keelde kuuluvad märgijadad (sõnad) ja ainult need.
Keelte defineerimisel kasutatakse kaht liiki sümboleid:
- sümboleid, mis kuuluvad defineeritavasse keelde; neid nimetatakse terminalideks;
- abimõisteid (üldmõisteid) ehk mitteterminale, mis on vajalikud defineeritava keele struktuuri kirjeldamiseks ja mis ise keelde ei kuulu.

Näiteks eesti keele lihtlause struktuuri võib kirjeldada üldmõistete "Lause", "Aluserühm", "Õeldiserühm", "Täiend" jne abil. Terminalid on lauses kasutatud sõnad: "auto", "poiss", "roheline", "kiiresti" jne. Lihtsa programmeerimiskeele süntaksi, s.t. korrektselt kirjutatud programmi süntaktilise struktuuri võib kirjeldada üldmõistete "Omistamine", "Avaldis", "Tingimus" abil; terminalid oleks keeles kasutatavad sõnad (nn võtmesõnad - keywords) if, then, else, for, ... , identifikaatorite (muutujate) tähis Ident ja arvkonstantide tähis Const.

Keele genereerimine algab algussümbolist (see on mitteterminal) ja kestab seni, kuni on saadud ainult terminale sisaldav jada s.t. kõik mitteterminalid on asendatud terminalidega.
Seega grammatika on nelik (T, V, A, P), kus

  • T on terminalide tähestik;
  • V on mitteterminalide tähestik (T ja V on erinevad, T V = );
  • A on algussümbol (A V);
  • P on produktsioonide v v' hulk; sõnad v,v' võivad sisaldavad nii terminale kui ka mitteterminale (v,v' (T V)* ) ja sõnas v on vähemalt üks mitteterminal, s.t. produktsioonid ei teisenda ainult terminalidest koosnevaid sõnu.
    Grammatika G = (T, V, A, P) genereerib keele
    LG = {w | w T*, X * w}

    Näide 1. Eespoolvaadeldud eesti keele lihtlause kirjeldamisel kasutati grammatikat G = (T, V, X, P), kus
    T = {"roheline", "värvitu", "värvitud", "suur", "ilus", "piklik", "sõidab", "jookseb", "laulab", "magavad", "loeb", "sajab", "kiiresti", "ruttu", "kaua", "rõõmsalt", "raevukalt", "ilusasti", ...}
    ( kõiki neid eesti keele sõnu vaadeldakse siin ühe sümbolina, s.t. tähena!)
    V = {Lause, Aluserühm, Õeldiserühm, Alus, Täiend, Öeldis, Määrus, Nimisõna, Omadussõna, Tegusõna, Määrsõna};
    A = Lause ;
    P = {Lause ::= Aluserühm Öeldiserühm
    Aluserühm ::= Alus | Täiend Alus
    Alus ::= Nimisõna
    Täiend ::= Omadussõna
    Öeldiserühm ::= Öeldis | Öeldis Määrus
    Öeldis ::= Tegusõna
    Määrus ::= Määrsõna
    Nimisõna ::= "auto" | "poiss" | "päike" | "elevant" | "kurk" | "idee" | "ideed" ...
    Omadussõna ::= "roheline" | "värvitu" | "värvitud" | "suur" | "ilus" | "piklik" | ...
    Tegusõna ::= "sõidab" | "jookseb" | "laulab" | "magavad" | "loeb" | "sajab" | ...
    Määrsõna ::= "kiiresti" | "ruttu" | "kaua" | "rõõmsalt" | "raevukalt" | "ilusasti" | ...}

    Näide2. 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 = {Tunniplaan, Päev, Aine, Aeg, Ruum, Klass}
    A = Tunniplaan
    V = {Tunniplaan Päev Aine Aeg Ruum Klass }
    Päev "Esmaspäev" | "Teisipäev" | ... | "Reede"
    Aine "Matemaatika" | "Ajalugu" | "Eesti keel" | ...
    Aeg 8.00 | 10.00 | 12.00 | ...
    Ruum = 101 | 102 | 201 | ...
    Klass = 9a | 9b | 10a |...

    Ülesandeid:

    1. Koosta formaalne 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 päevana ainult tööpäevi, kellaaja, õpperühma ja ruumi formaate ainult sellistena nagu näites.

    2. 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
    Eesnimi võib olla antud ka lühendina (esitäht ja punkt); aadressis on ühe- või kahesõnaline tänava-tee nimi, number, koma, numbriline postiindeks, linn; telefoninumbris võib maksimaalselt kolmest numbrist koosnev maatunnus (ei alga nulliga) ka puududa, kuid kui see on, peab see olema sulgudes , seejärel tuleb tühik, kolme või neljakohaline eesliide, tühik, kolme-või neljakohalistest numbrirühmadest (vähemalt üks) lõpp.

    3. Koosta võimalikult lihtne grammatika, mis genereeriks kõik avaldised kujul

    1n+1m=1n+m
    n,m>0
    (liitmine ühendsüsteemis), s.t. sellesse keelde kuuluks (näiteks) jadad 1+11=111, 111+1=1111 jne. Kas see keel on regulaarne? Kas see keel on kontekstivaba?

    4. Koosta võimalikult lihtne grammatika, mis genereeriks lisaks eelmises ülesandes kirjeldatud summadele ka ühendsüsteemis kirjutatud vahed, s.t. sellesse keelde kuuluks (näiteks) jadad 1+11=111, 111-1=11, 1+1=11 jne Kas see keel on regulaarne? Kas see keel on kontekstivaba?

    Küsimused, probleemid: ©2004 Jaak Henno
    Tagasi loengute sisukorra juurde