GLR-parser (fra engelsk. Generaliseret venstre-til-højre-afledningsparser - Generalized ascending store parser ) - i datalogi , en udvidet LR-parser-algoritme , designet til at parse ikke-deterministiske og tvetydige grammatikker . Først beskrevet af Masaru Tomita i 1984 , kaldes det også en "parallel parser" .
Da denne algoritme er afledt af LR-parseren, forblev principperne for dens drift de samme: Tomita satte sig som mål at opnå hurtig og effektiv genkendelse af tekster skrevet i naturligt sprog . Den normale LR-parser er ikke i stand til at løse ubestemmeligheden og tvetydigheden af naturlige sprog, mens GLR-algoritmen kan.
GLR-algoritmen fungerer nøjagtigt som LR-algoritmen , bortset fra at for en given grammatik behandler GLR-parseren alle mulige fortolkninger af inputsekvensen ved brug af bredde-først-søgning . GLR-parsergeneratorer konverterer den originale grammatik til parsertabeller, ligesom LR-parsergeneratorer. Men mens LR-parsertabeller kun tillader én tilstandsovergang (defineret af parserens starttilstand og inputterminalsymbolet), tillader GLR-parsertabeller mange resulterende tilstande. Som et resultat tillader GLR-algoritmen forskydning/reducer og reducer/reducer konflikter.
Når der opstår en konflikt, gafler parserens stak (kollapslager) sig i to eller flere parallelle stakke, hvis toptilstande svarer til hver mulig overgang. I det følgende bliver det næste inputsymbol brugt til at bestemme de næste overgange på de øverste tilstande af hver gren af stakken. I dette tilfælde kan det igen være nødvendigt at forgrene stakken. Hvis der for en hvilken som helst toptilstand og inputsymbol ikke er nogen overgang (i parsertabellen), så anses denne gren af stakken for at være fejlagtig og kasseret.
Grundlaget for optimering er muligheden for at dele dele af stakken med flere af dens grene, hvilket reducerer den samlede mængde hukommelse, der kræves for at parse inputsekvensen. Den komplekse struktur som følge af denne optimering får stakken til at ligne mere en rettet acyklisk graf end et træ.
GLR-algoritmen har i værste fald samme kompleksitet som Kok-Younger-Kasami- algoritmen og Earley-algoritmen - O ( n³ ). GLR-algoritmen har dog to fordele:
I praksis er de fleste programmeringssprog deterministiske eller "næsten deterministiske". Det betyder, at ikke-determinisme normalt kan løses ved at læse et lille (omend ubegrænset) antal inputtegn. Sammenlignet med andre algoritmer, der er i stand til at behandle hele klassen af kontekstfri grammatikker (såsom den tidlige algoritme eller Kok-Younger-Kasami- algoritmen), er GLR-algoritmen mere effektiv på sådanne "næsten deterministiske" grammatikker, da kun én gren af stakken.