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:
- Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} → Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle aBC}
- Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} → Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c|cd}
- Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} → Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle df|eg}
bi spario Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} → Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle aBC} i pokušao spariti Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} → Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c|cd} u sljedećem koraku. Potom bi bila pokušana produkcija Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} → Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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).