Parsiranje od vrha prema dnu

Izvor: Wikipedija
Skoči na: orijentacija, traži

Parsiranje od vrha prema dnu je strategija analiziranja odnosa nepoznatih podataka postavljanjem hipoteze struktura stabla parsiranja i potom razmatrajući jesu li poznate fundamentalne strukture podudarne sa hipotezom. Koristi se u analizi i prirodnih jezika i računalnih jezika.

Primjena u programskim jezicima[uredi VE | uredi]

Jezični procesor parsira ulaz iz programskog jezika u asembler ili neku internu reprezentaciju sparivanjem ulaznih znakova (simbola) u Backus-Naurov oblik pravila produkcija. LL parser, poznat i kao parser od vrha prema dnu, primjenjuje pojedine produkcije na temelju pročitanog znaka ulaznog niza i na temelju krajnje lijevog nezavršnog znaka u nizu. Na ovaj način parsiranje započinje od krajnje lijevog znaka desne strane produkcije i evaluira nezavršne znakove sa lijeve strane, te nastavlja duž stabla parsiranja za svaki novi nezavršni znak prije nego nego nastavi na sljedeći znak produkcije.

Na primjer:

  • AaBC
  • Bc|cd
  • Cdf|eg

bi spario AaBC i pokušao spariti Bc|cd u sljedećem koraku. Potom bi bila pokušana produkcija Cdf|eg. Neki jezici su nejednoznačniji od drugih. Za jednoznačni jezik u kojem sve produkcije za nezavršni znak daju različite nizove znakova, niz znakova kojeg daje jedna produkcija neće započeti sa istim znakom kao niz znakova kojeg daje druga produkcija. Jednoznačni jezik može biti parsiran LL(1) gramatikom pri čemu (1) označava da parser čita jedan po jedan ulazni znak. LL parser za nejednoznačne jezike mora unaprijed čitati više od jednog znaka, npr. LL(3).

Uobičajeno rješenje jest korištenje LR parsera (poznatog i kao parser od dna prema vrhu ili pomak-reduciraj parser).