LR parser

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. 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*”.

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.

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. 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.