Parsiranje od vrha prema dnu

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

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:

• $A$ → $aBC$
• $B$ → $c|cd$
• $C$ → $df|eg$

bi spario $A$ → $aBC$ i pokušao spariti $B$ → $c|cd$ u sljedećem koraku. Potom bi bila pokušana produkcija $C$ → $df|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).