Nejednoznačna gramatika

U računarstvu, za gramatiku kažemo da je nejednoznačna gramatika (ambiguitetna gramatika, te još i višeznačna gramatika) ako postoji neki niz znakova (simbola) koji se može generirati na više različitih načina (tj. niz znakova ima više različitih stabala parsiranja).

Formalna definicija

Sljedeće su dvije definicije ekvivalentne:

Ako je moguće za neki niz $w\in L(G)$ izgraditi više različitih stabala parsiranja, onda je kontekstno neovisna gramatika $G$ nejednoznačna.

Ako je moguće neki niz $w\in L(G)$ generirati primjenom više različitih postupaka generiranja niza zamjenom krajnje lijevog nezavršnog znaka ili primjenom više različitih postupaka generiranja niza zamjenom krajnje desnog nezavršnog znaka, onda je gramatika $G$ nejednoznačna.

Posljednja definicija slijedi iz prve jednostavnom implikacijom iz činjenice da je bilo koje stablo parsiranja moguće izgraditi primjenom jednog i samo jednog postupka generiranja niza zamjenom krajnje lijevog, odnosno desnog, nezavršnog znaka.

Nejednoznačni nizovi i jezici

Ako je moguće za niz $w\in L(G)$ izgraditi više različitih stabala parsiranja, onda je niz nejednoznačan za gramatiku $G$.

Jezik je inherentno nejednoznačan ako ga može generirati samo nejednoznačna gramatika.

U programskim jezicima, nejednoznačne gramatike mogu dovesti do poteškoća prilikom implementacije jezičnih procesora, posebice zbog činjenice što nijedna nejednoznačna gramatika nikad ne može biti LR gramatika.

Primjer

Kontekstno neovisna gramatika

A → A + A | A − A | a

je nejednoznačna jer postoje dva postupka generiranja 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 generira nije inherentno nejednoznačan, jer postoji nejednoznačna gramatika koja generira isti jezik:

A → A + a | A − a | a

Razriješavanje nejednoznačnosti jezika

Nejednoznačnost nekog jezika $L$ se općenito može razriješiti na dva načina: promjenom gramatike koja ga generira i promjenom samog jezika.

Prilikom promjene gramatike, izbor jednoznačne gramatike određuje način gradnje stabla parsiranja. Može postojati više različitih jednoznačnih gramatika koji generiraju jezik.

Razriješavanje nejednoznačnosti promjenom jezika se obavlja iz tri osnovna razloga:

• jezik je inherentno nejednoznačan
• jednoznačna gramatika je previše složena
• žele se sačuvati sve moguće interpretacije pojedinih nizova

Izvori

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