LL parser

U računalnoj znanosti, LL-parseri (engl. *LL parsers*) vrsta su sintaktičkih analizatora koji rade odozgo prema dolje (engl. *top-down*) za ograničeni skup kontekstno neovisnih jezika. Analizirju ulaz slijeva nadesno, provodeći najlijevo izvođenje rečenice.

U slučaju da se pri analizi rečenice koristi *k* tokena unaprijednog čitanja (engl. *lookahead*), takav LL-parser se može definirati kao LL(k)-parser. Gramatika se definira kao LL(k)-gramatikom ako se na temelju nje može konstruirati LL(k)-parser. Formalni jezik je definiran kao LL(k)-jezik ako posjeduje LL(k)-gramatiku. Skup LL(k)-jezika pravi je podskup skupa LL(k+1)-jezika za svaki k ≥ 0.[1] Iz toga slijedi da se svi kontekstno neovisni jezici ne mogu prepoznati pomoću LL(k)-parsera.

LL-parser je LL-regularan (LLR) ako analizira LL-regularni jezik. Klasa LLR-gramatika obuhvaća svaku LL(k)-gramatiku za svaki k. Za svaku LLR-gramatiku postoji LLR-parser koji tu gramatiku analizira u linearnom vremenu.

Dvije vrste parsera koje odstupaju od uobičajene nomenklature su LL(*) i LL(finite). Analizator se može definirati kao LL(*)- ili LL(finite)-parser ako koristi strategiju analize LL(*) ili LL(finite). LL(*) i LL(finite) analizatori funkcionalno su bliži PEG-analizatorima. LL(finite)-analizator može optimalno analizirati proizvoljnu LL(k)-gramatiku s obzirom na broj tokena unaprijednog čitanja i broj usporedbi tih tokena. Zbog uporabe sintaktičkih i semantičkih predikata, klasa gramatika koje se mogu analizirati strategijom LL(*) također obuhvaća i neke kontekstno ovisne jezike, te nije u potpunosti definirana. Postoje mišljenja da je LL(*)-analizatore prikladnije promatrati kao TDPL-analizatore. Suprotno uvriježenom mišljenju, LL(*)-analizatori općenito nisu LLR-analizatori; konstrukcijski je zajamčeno da u prosjeku rade sporije (superlinearno naspram linearnog vremena), a u najgorem slučaju znatno sporije (eksponencijalno naspram linearnog vremena). LL gramatike, a osobito LL(1) gramatike, od velikog su praktičnog interesa, poglavito jer je analizatore za te gramatike lako konstruirati, a mnogi su računalni jezici upravo iz tog razloga dizajnirani kao LL(1) jezici. LL analizatori mogu se temeljiti na tablicama (tj. biti slični LR analizatorima), no LL gramatike mogu se analizirati i pomoću analizatora s rekurzivnim spustom.