Otvori glavni izbornik

U računarstvu, za gramatiku kažemo da je nejednoznačna gramatika (ambiguitetna gramatika, te još i višeznačna gramatika[1]) 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).

Sadržaj

Formalna definicijaUredi

Sljedeće su dvije definicije ekvivalentne:

Ako je moguće za neki niz   izgraditi više različitih stabala parsiranja, onda je kontekstno neovisna gramatika   nejednoznačna.

Ako je moguće neki niz   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   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 jeziciUredi

Ako je moguće za niz   izgraditi više različitih stabala parsiranja, onda je niz nejednoznačan za gramatiku  .

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.

PrimjerUredi

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 jezikaUredi

Nejednoznačnost nekog jezika   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

IzvoriUredi

  1. Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 44

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