2. GRAMATIKE

U ovom su poglavlju opisane gramatike - veoma značajni formalizmi za specificiranje jezika. Veći dio poglavlja posvećen je beskontekstnim gramatikama i jezicima.

2.1 DEFINICIJA GRAMATIKE

Gramatike su jedna od najznačajnijih klasa generatora jezika. Ovdje će biti razmatrane klase gramatika koje se ponekad nazivaju gramatike Chomskog ili gramatike fraznih struktura.

Gramatika jezika L koristi dva disjunktna skupa znakova. To su skup neterminalnih znakova, često označen s N, i skup terminalnih znakova (alfabet), ozna#&269en s T. Skup terminalnih znakova osnova je za tvorbu rečenica jezika. Neterminalni znakovi nisu dio jezika. Koriste se u definiranju pravila za generiranje rečenica jezika.

Glavni dio gramatike jest konačan skup tvorbenih pravila ili produkcija, označenih s P, kojima je opisan način generiranja rečenica jezika. Produkcija je par nizova znakova iz skupa (Kartezijevog produkta)

(N U T)^* N(N U T)^*x (N UT)^*

Prva komponenta je bilo koji niz koji sadrži najmanje jedan neterminalni simbol. Druga komponenta može biti bilo što, pa i prazan niz. Jezik definiran gramatikom je skup nizova znakova koji se sastoje samo od terminalnih znakova i mogu biti izvedeni počevši s jednim posebnim znakom iz N, najčešće označenim sa S. Prije nego što to pokažemo, evo definicije gramatike.

Definicija 2.1

Gramatika je četvorka G= (N,T,P,S), gdje su:
N konačan skup neterminalnih znakova,
T konačan skup terminalnih znakova (alfabet) uz uvjet da je T∩N=Ø,
P konaèan skup parova nizova:
{(&alpha, &beta): &alpha=&alpha₁&gamma&alpha₂;&alpha₁,&alpha₂, &beta&epsilon (NUT) ^*, &gamma &epsilon N} (niz a je iz (NUT)⁺ i mora sadržati bar jedan znak iz skupa N),
S poseban znak iz N, S&epsilonN, nazvan početni znak (ili početni simbol).

Element (&alpha,β) iz P piše se &alpha&rarrβ i naziva produkcija. Simbol "&rarr" čita se "producira", "može biti zamijenjeno s" ili " preobličuje se u".

Primjer 2.1

Primjer gramatike je G= (N,T,P,S) , gdje su:

N = {A, S}

T = {0, 1}

P{(S, 0A1), (0A, 00A1),(A, ε)}

Početni simbol je S. Skup produkcija P mo໯emo napisati i kao

S &rarr 0A1

0A &rarr 00A1

A → &epsilon

&alpha &rarr &beta₁ ... &alpha &rarr &beta_n

&alpha &rarr &beta₁| &beta₂|... |&beta_n

&alpha &rarr &epsilon | &beta | &beta&beta | &beta&beta&beta | ...

Vitičaste zagrade omeðuju niz koji može biti izostavljen ili napisan jedanput, dvaput, triput, itd. Produkcija oblika:

&alpha &rarr &epsilon | β

U daljnjem ćemo tekstu neterminale označivati velikim slovima, engl. abecede. Terminali će biti mala slova engl. abecede i ostali znakovi: (brojke, +,-,*,/, (, ), itd.). Neterminal na početku prve produkcije bit će početni simbol.

Gramatika kao generator jezika

S &rarr &alpha₁ | &alpha₂ | ... |&alpha_n, &alpha_i &epsilon (N U T)^*, i ≥ 1

Primjer 2.2

Gramatika G= (N,T,P,S), gdje je P:

S &rarr OS | 1

generira jezik L(G)={1, 01, 001, >0001, . . . }={0ⁿl: n≥0}. Na primjer, ako se za S izabere alternativa OS pa se S u tom nizu zamijeni s OS, dobije se niz 00S. Ako se potom za S izabere druga alternativa, konačno se dobije niz 001, jedan element jezika L(Q) .

Definicija 2.2

Rečenična forma gramatike G= (N,T,P,S) definirana je rekurzivno:
1)Početni znak je rečenična forma.
2)Ako je &alpha&delta&gamma, gdje su &alpha,&gamma &epsilon (NUT)^*, rečenična forma i &delta&rarr&beta P, tada je &alpha&delta&gamma takoðer rečenična forma.
Rečenična forma koja ne sadrži nijedan neterminal naziva se rečenica.

Definicija 2.3

Nad skupom (NUT)^* gramatike G= (N,T,P,S)definira se relacija =>, čita se "izravno izvodi", na sljedeći način: Ako je &alpha&delta&gamma niz iz (NUT)^*i &delta&rarr&beta produkcija iz P, tada

&alpha&delta&gamma ==> &alpha&beta&gamma

Ako za &alpha₀, &alpha₁, ..., &alpha_n, &alpha_i&epsilon(NUT)^*) , n≥l, vrijedi

&alpha₀ ==> &alpha₁ ==> ... ¨==> &alpha_n

tada je &alpha₀ ⁿ==> &alpha_n niz izvoðenja duljine n. Općenito se piše

&alpha_o ^* ==> &alpha_n, n≥0, &alpha_o ⁺ ==>; &alpha_n, n>0

i kaže da &alpha_o izvodi &alpha_n.

L(G) = {&omega&epsilonT^* : S^* ==>&omega}

Primjer 2.3

Gramatika s produkcijama:

E &rarr T | T+E

T &rarr F | T*F

F &rarr a | (E)

generira jednostavne aritmetičke izraze. Ako je E početni simbol, rečenične forme su:

E T F a T+E T*F+E (E) a+a a*a (a)

Primjer izvoðenja:

E ==> T+E ==> T*F+E ==> F*F+E ==> a*F+E ==> a*a+E ==> a*a+T ==> a*a+F ==> a*a+a

što se može napisati i kao

E ⁸==> a*a+a ili E ==> a*a+a

Niz a*a+a je jedna rečenica jezika koji gramatika s danim produkcijama generira.

Klasifikacija gramatika

Definicija 2.4

Za gramatiku G=(N,T,P,S) kaže se da je:
1) Linearna zdesna ili tipa 3 ako je svaka produkcija iz P oblika

A → xB ili A &rarr x A,B&epsilonN, x &epsilon T^*

Linearna slijeva ako je svaka produkcija iz P oblika

A → Bx ili A → x

Gramatika linearna zdesna naziva se regularna gramatika ako je svaka produkcija oblika

A → aB ili A → a     A,B&epsilonN, a&epsilonT

i jedino je dopuštena produkcija S →&epsilon, ali se tada S ne smije pojavljivati niti u jednoj alternativi ostalih produkcija.

2) Beskontekstna ili tipa 2 ako je svaka produkcija iz P oblika:

A → &alpha     A&epsilonN, &alpha&epsilon(NUT)^*

3)Kontekstna ili tipa 1 ako je svaka produkcija iz P oblika

    &alpha → &beta

uz uvjet da je |&alpha|≤|&beta|

4) Bez ograničenja ili tipa 0 ako produkcije ne zadovoljavaju nijedno od navedenih ograničenja.

Primjer 2.4

Na idućoj slici prikazana je silueta jednog objekta aproksimirana gramatikama tipa 3, 2 i 1, a tek u potpunosti opisana gramatikom tipa 0:

Primjer 2.5

Evo primjera regularne, beskontekstne i kontekstne gramatike, te gramatike bez ograničenja:

1) Regularna:

   S → aS | bS | &epsilon

generira jezik L={a,b}^* tj. regularni skup označen regularnim izrazom (a+b)*

2) Beskontekstna:

S → aSb | ab

generira jezik L= {aⁿbⁿ: n≥ 1}.

3) Kontekstna:

S → aSBC | abc   CB → BC

bB → bb          bC → bC

cC → cc

generira jezik L= {aⁿbⁿcⁿ:     n≥ 1}.

4) I, na kraju, primjer gramatike bez ograničenja:

S → CD

C → aCa | bCb | &epsilon

AD → aD

BD → bD

Aa → aA

Ab → bA

Ba → aB

Bb → bB

D → &epsilon

generira jezik L={ωω:   ωε{a,b}^*}

Beskontekstni jezici

Definicija 2.5

Za beskontekstnu gramatiku G= (N,T,P,S) kaže se da je:

1)Rekurzivna slijeva ako P sadrži produkciju oblika

A → A &alpha           &alpha&epsilon (NUT)⁺

2)Rekurzivna zdesna ako P sadrži produkciju oblika

A → &alpha A           &alpha&epsilon (NUT)⁺

3)Rekurzivna ako P sadrži produkciju oblika

A → &alpha A &beta           &alpha, &beta &epsilon (NUT)⁺

ili ako je istodobno rekurzivna slijeva i zdesna, ili ako nije rekurzivna, ali postoji implicitna rekurzija:

A ⁺==> &alpha A &beta           &alpha, &beta &epsilon (NUT)⁺

Gramatika rekurzivna slijeva, zdesna, odnosno, općenito rekurzivna, generira beskonačan jezik.

Primjer 2.6

Regularna gramatika iz prethodnog primjera:

S → aS | bS | &epsilon

rekurzivna je zdesna, a beskontekstna gramatika iz istog primjera:

S → aSb | ab

jest rekurzivna. Gramatika s produkcijama:

E → E+E | E*E | (E) | a

rekurzivna je "sa svih strana", tj. samo se kaže daje rekurzivna.

Stabla izvoðenja

Definicija 2.6

Označeno ureðeno stablo D je stablo izvoðenja (ili stablo sintaksne analize) beskontekstne gramatike G(S)= (N,T,S,P) ako vrijedi:

  1) Korijen od D označen je sa A.

  2) Ako su D₁, ..., D_k podstabla direktnih slijednika korijena i korijen od D_i je označen sa X_i, tada je

S → X₁...X_k

produkcija u P. D_i mora biti stablo izvoðenja za

G(X_i) = (N,T,P,X_i)

ako je X_i neterminal, odnosno D_ii je čvor (list) označen sa X_i ako je X_i terminal.

3) Inače, ako je D_i jedino podstablo korijena Di korijen od D_i označen je sa &epsilon, tada je S→&epsilon produkcija u P.

Primjer 2.7

Primjeri stabala izvoðenja gramatike G, definirane sa

S → aSbS | bSaS | &epsilon

dani su na sljedećoj slici:

a)

S

b)

S

|

&epsilon

d)

Definicija 2.7

Granica stabla izvoðenja jest niz koji se dobije nastavljanjem oznaka listova (u ureðenju slijeva nadesno).

Primjer 2.8

Granice stabala izvoðenja iz prethodnog primjera jesu:

a) S      b) &epsilon      c)abab       d) abab

Definicija 2.8

Neka je =(N,T,P,S) beskontekstna gramatika. Pisat ćemo

&alpha =^1m=> ß

ako je &alpha= &omega A &gamma, ß= &omega&delta&gamma, &omega&epsilonT^*, &delta&epsilon(NUT)^* i A →&delta je produkcija u P. Odnosno, rečenična forma P dobivena je zamjenom prvog neterminalnog znaka slijeva u rečeničnoj formi &alpha . Izvoðenje

&alpha_o ^*=_1m=> &alpha₁ ^*=_1m=>... ^*=_1m=> &alpha_n

je krajnje izvoðenje slijeva za &alpha_n iz &alpha_o, u gramatici G.Ako je

S ^*=_1m=> &alpha

&alpha se naziva lijeva rečenična forma. Definira se izvoðenje zdesna i krajnje izvoðenje zdesna, analogno izvoðenju slijeva. Na svim mjestima umjesto ""lijevo"" treba stajati "desno", a oznaka "lm" prelazi u "rm".

Primjer 2.9

Neka je G gramatika s produkcijama

E → E+T|T      T → T*F | F      F → (E) | a

gdje je E početni simbol. Stablo izvoðenja prikazano na sljedećoj slici predstavlja deset ekvivalentnih izvoðenja rečenice a+a.

E

|

E     +      T

|             |

T            F

|             |

F            a

|             

a           

Krajnje izvoðenje slijeva je:

E => E+T => T+T => F+T => a+T => a+F => a+a

a krajnje izvoðenje zdesna:

E => E+T => E+F => E+a => T+a => F+a => a+a

Definicija 2.9

Kaže se da je beskontekstna gramatika G dvoznačna ako postoji najmanje jedna rečenica &omega u L(G)za koju postoji više od jednog različitog stabla izvoðenja s granicom ω. To je ekvivalentno tvrdnji da je G dvoznačna gramatika ako postoji rečenica &omega u L(G) s dva ili više različitih krajnjih izvoðenja slijeva (ili zdesna).

Primjer 2.10

Neka je G gramatika s produkcijama

E => E+E | E*E | (E) | a

G je dvoznačna. Na primjer, rečenica a*a+a može se dobiti s dva različita niza izvoðenja slijeva:

1) E => E*E => a*E   => a*E+E   => a*a+E   => a*a+a

2) E => E*E => E*E+E => a*E+E   => a*a+E   => a*a+a

2.2 PRIKAZ GRAMATIKA

Backus- Naurova forma (BNF)

1) Neterminalni simboli pišu se izmeðu znakova "<" i ">".
     2) Umjesto "&rarr" koristi se simbol "::=" i čita "definirano je kao". Pišući neterminale izmeðu znakova "<" i ">" moguće je izborom njihovih imena uvesti "značenje" u produkcije, jer će nas imena podsjećati na vrstu rečenica koja će se generirati u nekom podjeziku.

Primjer 2.11

Sljedeća gramatika generira "jezik kaubojskih vlakova":

<kaubojski vlak> ::= <lokomotiva><požtanska kola><dodatak>

<dodatak>   ::= {<putnička kola>}<kola za konje>|&epsilon

Sintaksni dijagrami

1) Terminalni simbol x prikazan je kao

→x→

2) Neterminalni simbol A prikazan je kao

→A→

3) Produkcija oblika

A → A₁A₂ . . . A_n               A_i&epsilon (NUT)

predstavlja se dijagramom

→ A₁ → A₂ →     → A_n

4) Produkcija oblika

A → A₁|A₂|. . . |A_n     A_i&epsilon (N UT)

prikazuje se dijagramom

gdje je svaki A_i prikazan prema pravilima od (1) do (4). Ako je A_i= &epsilon, ta se alternativa prikazuje punom crtom.

5) Produkcije oblika

A → {B} i C → [D]     B,D&epsilon (N UT)

prikazuju se dijagramima:

gdje su B i D prikazani dijagramima prema pravilima (1) do (4).

Primjer 2.12

Gramatika G s produkcijama P

A → x | (B)     B → AC    C → {+A}

generira jezik L(G) ={x,(x),((x)),...,(x+x),...}. Primjenjujući pravila (1) do (5), dobili bismo dijagrame

Primjer 2.13

Formalizam pisanja produkcija u BNF-u takoðer je jezik! Evo beskontekstne gramatike jezika BNF prikazane u pojednostavljenom zapisu sintaksnih dijagrama:

<BNF>

→ produkcija →

<produkcija>

→ neterminal → ::= &rarr alternativa &rarr

<neterminal>

→ < → niz znakova → > →

<alternativa>

→ &epsilon ------------------------------------------------------>

→ niz ----------------------------------------------------↑

→ { → alternativa &rarr }-----------------------------------↑

→ [ → alternativa → ]-----------------------------------↑

<niz>

→ znak →

↓→ neterminal →↑

gdje je <znak> znak alfabeta, a <niz znakova> izabrani skup znakova (slova, brojke).

Pitanja i zadaci

1) Dane su dvije gramatike, G₁= (N₁,T₁,S₁,P₁)i G₂= (N₂,T₂,S₂,P₂), N₁∩N₂= Ø.

Definirajte gramatiku G koja generira jezik

L(G)= {&omega₁&omega₂:   &omega₁&epsilonL(G₁), &omega₂&epsilonL(G₂)}

2) Definirajte regularne gramatike koje generiraju jezik označen sljedećim regularnim izrazima:

a)(0)⁺(l)⁺

b)(00+ll+(01+10)(00+11)*(01+10))*

c) 01 ( ( (ab) *+ccc) *+x) *z

3) Definirajte gramatike jezika:

a) L₁ = {1,2,3,4,5,6, ...}

b) L₂ = {2,4,6,8,10,12,...}

c) L₃ = {1,3,5,7,9,11, ...}

d) L₄ = {4,8,12,16,20, ...}

e) L₅ = {3,6,9,12,15,18,...}

f) L₆ = {9,18,27,36,45,... }

4)Definirajte gramatiku jezika palindroma (nizova x koji imaju svojstvo da je x=x^R) nad alfabetom A={a,b, c}.

5)Definirajte gramatiku jezika rimskih brojeva i, ii, iii, iv, v, ..., mmmcmxcviii, mmmcmxcix.

6)Definirajte gramatiku jezika:

a) L₁= {xx^R:x&epsilon{0,1,a,b}⁺}, gdje je x^R reverzni niz niza x. Na primjer, u jeziku su: 00,11, aa, bb, ..., OalbblaO, itd.

b) L₂= {aⁿb²ⁿ: n≥l}

c) L₃= {aⁿb^mc^mdⁿ: m≥l, ≥l}

7) Definirajte gramatiku jezika prijestupnih godina, od 2000. do 9996. godine. (Pazite, godine koje su djeljive sa 100 moraju biti djeljive i s 400 da bi bile prijestupne! Godina 2000.je bila         prijestupna, ali godine 2100., 2200. i 2300. nisu itd.)

8)Definirajte gramatiku jezika datuma napisanih u obliku DD.MM.GGGG, gdje su:

DD     - dan (01, 02, ..., 31)

MM     - mjesec (01, 02, ..., 12)

GGGG   - godina (2000 do 9999)

Na primjer, u jeziku su 01.01.2000 i 29.02.9996, a nisu 29.02.2100., 01.13.2000, itd.

9) Dana je gramatika:

S → aB | bA

A → a | aS | bAA

B → b | bS | aBB

Za niz aaabbabbba treba naći:

    a) krajnje izvoðenje slijeva

    b) krajnje izvoðenje zdesna

    c) stablo izvoðenja

10) Je li gramatika iz primjera 2.9 dvoznačna?

11) Definirajte gramatiku logičkih izraza u kojima će "varijable" biti f, t, x i y, "logičke operacije" # (negacija), $ (disjunkcija) i & (konjunkcija). Izraz može sadržavati i zagrade.

12) Analizirajte popis literature u nekoj knjizi ili stručnom časopisu i pokušajte definirati gramatiku pravila njihova pisanja (ako postoje!). Produkcije gramatike prikazite sintaksnim dijagramima u     kojima će neterminali biti riječi hrvatskoga jezika (na primjer, <ime>, <izdavač> itd.).

Sadržaj