Formaalne grammatika

Allikas: Vikipeedia

Formaalseks grammatikaks nimetatakse informaatikas ja keeleteaduses formaalse keele täpset kirjeldust, mis tähendab keele kuuluvate stringide (sõne (informaatika)) määratlemist. Formaalses grammatikas on kaks põhilist kategooriat. Esimene neist, generatiivsed grammatikad tegeleb reeglitega kuidas keelde kuuluvaid stringe genereerida. Teine, analüütilised grammatikad tegeleb reeglitega kuidas on võimalik stringe analüüsida, et aru saada, kas see kuulub keelde. Lühidalt, analüütiline grammatika kirjeldab kuidas ära tunda stringe mis kuuluvad mingisse hulka, samal ajal kui generatiivne grammatika kirjeldab kuidas kirjutada ainult neid stringe, mis kuuluvad mingisse hulka.

Generatiivsed grammatikad[muuda | redigeeri lähteteksti]

Next.svg Pikemalt artiklis Generatiivne grammatika

Generatiivne grammatika koosneb reeglitest, mille abil konstrueerida stringe. Selleks, et genereerida keelde kuuluvat stringi tuleb alustada grammatika algussümbolist ning seejärel rakendada teisi sobivaid reegleid. Reegleid võib kasutada suvalises järjekorras ja suvaline arv kordi. Reeglite rakendamise tulemusena saadakse string, mis kuulub grammatikaga määratud keelde. Osad grammatikad võimaldavad saada sama stringi mitmel eri viisil reegleid kohaldades, neid grammatikaid nimetatakse mitmeseks. Grammatikat, mille abil saab kõiki stringe ainult ühtviisi reegleid rakendades genereerida nimetatakse üheseks.

Näiteks võtame keele, milles on kaks tähte - a ja b ning 2 reeglit:

1. S \rightarrow aSb
2. S \rightarrow ba

Alustame S-st mis on algussümbol. Valides esimese reegli, asendame me S-i aSb-ga ja saame stringi aSb. Valides reegli 1 veel üks kord saame stringi aaSbb ja seejärel rakendades reeglit 2 saame stringi aababb. Lühidalt kokkuvõttes oli tuletuskäik järgmine: S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aababb. Grammatikaga määratud keeleks on kõikide nende stringide hulk mida antud reeglite abil on võimalik genereerida: \left \{ba, abab, aababb, aaababbb, ...\right \}.

Formaalne definitsioon[muuda | redigeeri lähteteksti]

Noam Chomsky pakkus 1950 aastatel välja formaalse grammatika definitsiooni. Grammatika G koosneb 4 komponendist:

  • Mitteterminalide lõplikust hulgast N
  • Terminalide lõplikust hulgast \Sigma, millel puudub ühisosa mitteterminalide hulgaga.
  • Produktsioonireeglite lõplikust hulgast P, igaüks kujul
(\Sigma \cup N)^{*} N (\Sigma \cup N)^{*} \rightarrow (\Sigma \cup N)^{*}
Lahtiseletatuna, iga produktsioonireegel seob ühe stringi teisega, vasakul pool peab olema vähemalt üks sümbol mitteterminalide hulgast. Juhul kui paremal pool on tühi string (string, milles ei ole ühtegi sümbolit), siis kasutatkse selle välja näitamiseks sümbolit epsilon (\epsilon).
  • Algussümbolist S, mis sisaldub hulgas N
S \in N

Tavaliselt viidatakse grammatikale kui nelikule: G = (N, \Sigma, P, S). Formaalse grammatika G poolt määratud keel (\boldsymbol{L}(G)) on defineeritud kui kõikide nende stringide hulk, mis koosnevad ainult sümbolitest hulgast \Sigma ja mida on võimalik genereerida alustades algussümbolist S ja seejärel rakendades produktsioone hulgast P kuni sõnad koosnevad ainult terminalidest (ei leidu sümboleid mitteterminalide hulgast N).

Näide[muuda | redigeeri lähteteksti]

Nende näidete jaoks on formaalsete keelte spetsifitseerimiseks kasutatud set-builder notationi.

Olgu meil grammatika G, kus N = \left \{S, B\right \}, \Sigma = \left \{a, b, c\right \}, S on algussümbol ja P sisaldab järgmisi produktsioonireegleid:

1. S \rightarrow aBSc
2. S \rightarrow abc
3. Ba \rightarrow aB
4. Bb \rightarrow bb

Mõned näited keelde \boldsymbol{L}(G) kuuluvate stringide tuletamisest oleks:

  • \boldsymbol{S} \Rightarrow_2 \boldsymbol{abc}
  • \boldsymbol{S} \Rightarrow_1 \boldsymbol{aBSc} \Rightarrow_2 aB\boldsymbol{abc}c \Rightarrow_3 a\boldsymbol{aB}bcc \Rightarrow_4 aa\boldsymbol{bb}cc
  • \boldsymbol{S} \Rightarrow_1 \boldsymbol{aBSc} \Rightarrow_1 aB\boldsymbol{aBSc}c \Rightarrow_2 aBaB\boldsymbol{abc}cc \Rightarrow_3 a\boldsymbol{aB}Babccc \Rightarrow_3 aaB\boldsymbol{aB}bccc  \Rightarrow_3 aa\boldsymbol{aB}Bbccc \Rightarrow_4 aaaB\boldsymbol{bb}ccc \Rightarrow_4 aaa\boldsymbol{bb}bccc
(Selgitus: loe L \Rightarrow_i R kui "L genereerib R-i kasutades selleks produktsiooni number i" ja genereeritud osa näidatakse iga kord rasvaselt)

See grammatika defineerib keele L = \left \{ a^{n}b^{n}c^{n} | n \ge 1 \right \}, kus a^{n} tähendab n arvust a sümbolitest koosnevat stringi. Seega, see keel sisaldab stringe, milles on võrdne nullist suurem arv a, b ja c stinge ning need sümbolid asuvad samas järjekorras.

Chomsky hierarhia[muuda | redigeeri lähteteksti]

Analüütilised grammatikad[muuda | redigeeri lähteteksti]

Kirjandus[muuda | redigeeri lähteteksti]

  • Jaak Henno. Formaalsed keeled, grammatikad ja translaatorid 2006. TTÜ Kirjastus. ISBN 9985-59-627-7.