Nejednoznačna gramatika

S Wikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

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