Bot1: Automatski uvoz s hrwiki (zadnjih 720 sati)

2026-10-17T23:50:15Z

Automatski uvoz s hrwiki (zadnjih 720 sati)

Nova stranica

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.<ref name=":1">{{Citiranje časopisa|last=Knuth|first=Donald E.|date=1965-12|title=On the translation of languages from left to right|url=https://linkinghub.elsevier.com/retrieve/pii/S0019995865904262|journal=Information and Control|language=en|volume=8|issue=6|pages=607–639|doi=10.1016/S0019-9958(65)90426-2}}</ref>

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.<ref name=":1" />

LL-parser je LL-regularan (LLR) ako analizira LL-regularni jezik.<ref>{{Citiranje časopisa|last=Jarzabek|first=Stanislaw|last2=Krawczyk|first2=Tomasz|date=1975-11|title=LL-regular grammars|url=https://linkinghub.elsevier.com/retrieve/pii/0020019075900095|journal=Information Processing Letters|language=en|volume=4|issue=2|pages=31–37|doi=10.1016/0020-0190(75)90009-5}}</ref> 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.<ref name=":1" />

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).<ref>{{Citiranje weba|last=Belcak|first=Peter|title=The LL(finite) strategy for optimal LL(k) parsing|url=https://arxiv.org/abs/2010.07874|url-status=live|access-date=}}</ref> 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.<ref>{{Citiranje časopisa|last=Ford|first=Bryan|date=2004-01|title=Parsing expression grammars: a recognition-based syntactic foundation|url=https://dl.acm.org/doi/10.1145/982962.964011|journal=ACM SIGPLAN Notices|language=en|volume=39|issue=1|pages=111–122|doi=10.1145/982962.964011|issn=0362-1340}}</ref> 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.<ref>{{Citiranje knjige|last=Terry|first=Patrick D.|title=Compiling with C# and Java|last2=Terry|first2=Patrick|date=2005|publisher=Pearson, Addison-Wesley|isbn=978-0-321-26360-5|series=Pearson education|location=Harlow Boston, Mass}}</ref> 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. <ref>{{Citiranje weba|date=2019-02-27|title=Construction of LL(1) Parsing Table|url=https://www.geeksforgeeks.org/compiler-design/construction-of-ll1-parsing-table/|access-date=2026-10-13|website=GeeksforGeeks|language=en}}</ref>

LL parser - Povijest promjena

Bot1: Automatski uvoz s hrwiki (zadnjih 720 sati)