Bot1: Automatski uvoz s hrwiki (zadnjih 720 sati)

2026-10-17T23:48:29Z

Automatski uvoz s hrwiki (zadnjih 720 sati)

Nova stranica

U računalnoj znanosti, LR-parseri (engl. *LR parsers*) vrsta su sintaktičkih analizatora koji rade odozdo prema gore (*bottom-up*) i analiziraju determinističke kontekstno neovisne jezike u linearnom vremenu.<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> Postoji nekoliko inačica LR-parsera: SLR-parseri, LALR-parseri, kanonski LR(1)-parseri, minimalni LR(1)-parseri i generalizirani LR-parseri (GLR-parseri). LR-parseri mogu se generirati pomoću generatora analizatora na temelju formalne gramatike kojom je definirana sintaksa analiziranog jezika. Imaju široku primjenu u obradi računalnih jezika.

LR-parser (što znači: slijeva nadesno, izvođenje najdesnijeg slijeda produkcija u obrnutom redoslijedu) čita ulazni tekst slijeva nadesno bez vraćanja unatrag (što vrijedi za većinu analizatora) i proizvodi izvođenje najdesnijeg slijeda produkcija u obrnutom redoslijedu: provodi analizu odozdo prema gore, a ne analizu odozgo prema dolje (poput LL-analize) ili *ad-hoc* analizu. Iza naziva „LR” često slijedi brojčana oznaka, kao u „LR(1)” ili ponekad „LR(k)”. Kako bi se izbjeglo vraćanje unatrag ili nagađanje, LR-analizatoru je dopušteno unaprijed pogledati *k* ulaznih simbola prije donošenja odluke o tome kako analizirati prethodne simbole. Obično je *k* jednak 1, pa se ta vrijednost ne navodi. Ispred naziva „LR” često stoje druge oznake, kao u „SLR” i „LALR”. Oznaku „LR(k)” za gramatiku predložio je Knuth kako bi označio „prevodivost slijeva nadesno s ograničenjem *k*”.<ref name=":1" />

LR-parseri su deterministički; proizvode jednu točnu analizu bez nagađanja ili vraćanja unatrag, i to u linearnom vremenu. To je idealno za računalne jezike, no LR-parseri nisu prikladni za prirodne jezike, koji zahtijevaju fleksibilnije, ali nužno sporije metode. Neke metode koje mogu analizirati proizvoljne kontekstno neovisne jezike (npr. Cocke-Younger-Kasami, Earley, GLR) u najgorem slučaju imaju složenost O(n³). Druge metode, koje uključuju vraćanje unatrag ili daju više mogućih analiza, mogu zahtijevati čak i eksponencijalno vrijeme ako se donesu loše odluke pri nagađanju.<ref>{{Citiranje knjige|last=Aho|first=Alfred V.|title=The theory of parsing, translation, and compiling|last2=Ullman|first2=Jeffrey D.|date=1972|publisher=Prentice-Hall|isbn=978-0-13-914556-8|series=Prentice-Hall series in automatic computation|location=Englewood Cliffs, N.J}}</ref>

Navedena svojstva oznaka L, R i *k* zapravo su zajednička svim analizatorima tipa „pomakni-reduciraj” (engl. *shift-reduce parsers*), uključujući i analizatore temeljene na prioritetu operacija (*precedence parsers*). Međutim, prema konvenciji, naziv LR odnosi se na vrstu raščlambe koju je osmislio Donald Knuth i isključuje ranije, manje moćne metode temeljene na prioritetu (primjerice, raščlanjivač prioriteta operatora).[1] LR raščlanjivači mogu obraditi širi raspon jezika i gramatika nego raščlanjivači temeljeni na prioritetu ili LL raščlanjivanje odozgo prema dolje. <ref>{{Citiranje weba|title=Language theoretic comparison of LL and LR grammars|url=https://cs.stackexchange.com/questions/43/language-theoretic-comparison-of-ll-and-lr-grammars|access-date=2026-10-13|website=Computer Science Stack Exchange|language=en}}</ref>To je zato što LR raščlanjivač čeka dok ne vidi cijelu instancu određenog gramatičkog uzorka prije nego što se odluči o tome što je prepoznao. LL raščlanjivač mora odlučiti ili nagađati što vidi mnogo ranije, već nakon što vidi samo najlijevi ulazni simbol tog uzorka.

LR parser - Povijest promjena

Bot1: Automatski uvoz s hrwiki (zadnjih 720 sati)