Nejednoznačna gramatika

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

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

• Polisemija

Reference

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