GLR parser (din engleză. Generalized Left-to-right Rightmost derivation parser - Generalized ascending store parser ) - în informatică , un algoritm de parser LR extins , conceput pentru a analiza gramatici nedeterministe și ambigue . Descris pentru prima dată de Masaru Tomiță în 1984 , este numit și „parser paralel” .
Deoarece acest algoritm este derivat din parserul LR, principiile de funcționare a acestuia au rămas aceleași: Tomița și-a propus să realizeze o recunoaștere rapidă și eficientă a textelor scrise în limbaj natural . Analizatorul LR normal nu poate rezolva nedeterminarea și ambiguitatea limbajelor naturale, în timp ce algoritmul GLR poate.
Algoritmul GLR funcționează exact ca algoritmul LR , cu excepția faptului că, pentru o gramatică dată, parserul GLR procesează toate interpretările posibile ale secvenței de intrare folosind căutarea pe lățimea întâi . Generatoarele de analiză GLR convertesc gramatica originală în tabele de analiză, la fel ca generatoarele de analiză LR. Dar, în timp ce tabelele parserului LR permit doar o tranziție de stare (definită de starea inițială a parserului și simbolul terminalului de intrare), tabelele de analiză GLR permit multe stări rezultate. Ca rezultat, algoritmul GLR permite deplasarea/reducerea și reducerea/reducerea conflictelor.
Când apare un conflict, stiva analizatorului (magazinul de colaps) se bifurcă în două sau mai multe stive paralele, ale căror stări de sus corespund fiecărei tranziții posibile. În cele ce urmează, următorul simbol de intrare este utilizat pentru a determina următoarele tranziții pe stările de sus ale fiecărei ramuri a stivei. În acest caz, poate fi din nou necesară ramificarea stivei. Dacă pentru orice stare de sus și simbol de intrare nu există nicio tranziție (în tabelul de analiză), atunci această ramură a stivei este considerată eronată și eliminată.
Baza optimizării este capacitatea de a partaja părți ale stivei cu mai multe dintre ramurile sale, ceea ce reduce cantitatea totală de memorie necesară pentru a analiza secvența de intrare. Structura complexă rezultată din această optimizare face ca stiva să arate mai mult ca un grafic aciclic direcționat decât cu un arbore.
Algoritmul GLR în cel mai rău caz are aceeași complexitate ca și algoritmul Kok-Younger-Kasami și algoritmul Earley - O ( n³ ). Cu toate acestea, algoritmul GLR are două avantaje:
În practică, majoritatea limbajelor de programare sunt deterministe sau „aproape deterministe”. Aceasta înseamnă că non-determinismul poate fi de obicei rezolvat prin citirea unui număr mic (deși nelimitat) de caractere introduse. În comparație cu alți algoritmi capabili să proceseze întreaga clasă de gramatici fără context (cum ar fi algoritmul Early sau algoritmul Kok-Younger-Kasami ), algoritmul GLR este mai performant pe astfel de gramatici „aproape deterministe”, deoarece doar o ramură a teancul.