Nejednoznačna gramatika

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

U računarstvu, za gramatiku kažemo da je nejednoznačna gramatika (još i ambiguitetna gramatika) ako postoji neki niz znakova (simbola) koji se može generisati na više načina (tj. niz znakova ima više od jednog stabla parsiranja ili može biti generisan više nego jednim postpukom generisanja niza zamjenom krajnje lijevog nezavršnog znaka). Jezik je inherentno nejednoznačan ako ga može generisati samo nejednoznačna gramatika.

U programskim jezicima, nejednoznačne gramatike mogu dovesti do poteškoća prilikom implementacije jezičnih procesora.

Primjer[uredi | uredi izvor]

Kontekstno nezavisna gramatika

A → A + A | A − A | a

je nejednoznačna jer postoje dva postupka generisanja niza zamjenom krajnje lijevog nezavršnog znaka za niz a + a − a:

     A → A + A      A → A − A
     → a + A      → A + A − A
     → a + A − A      → a + A − A
     → a + a − A      → a + a − A
     → a + a − a      → a + a − a

Ekvivalentno, nejednoznačna je jer postoje dva stabla parsiranja za niz a + a − a

S druge strane, jezik koji generiše nije inherentno nejednoznačan, jer postoji nejednoznačna gramatika koja generiše isti jezik:

A → A + a | A − a | a

Također pogledajte[uredi | uredi izvor]

Reference[uredi | uredi izvor]

Programming Languages: Design and Implementation, T. Pratt, M. Zelkowitz. Prentice Hall, 2001