GLR-parser (från engelskan. Generaliserad från vänster till höger höger-avledningsparser - Generalized ascending store parser ) - inom datavetenskap , en utökad LR-parseralgoritm , designad för att analysera icke-deterministiska och tvetydiga grammatiker . Först beskrevs av Masaru Tomita 1984 , den kallas också en "parallell parser" .
Eftersom denna algoritm härrör från LR-parsern, förblev principerna för dess funktion desamma: Tomita satte sig som mål att uppnå snabb och effektiv igenkänning av texter skrivna på naturligt språk . Den normala LR-parsern kan inte lösa obestämdheten och tvetydigheten hos naturliga språk, medan GLR-algoritmen kan.
GLR-algoritmen fungerar precis som LR-algoritmen , förutom att för en given grammatik bearbetar GLR-parsern alla möjliga tolkningar av inmatningssekvensen med hjälp av bredd-först-sökning . GLR-parsergeneratorer omvandlar den ursprungliga grammatiken till parsertabeller, precis som LR-parsergeneratorer. Men medan LR-parsertabeller endast tillåter en tillståndsövergång (definierad av parserns initiala tillstånd och ingångsterminalsymbolen), tillåter GLR-parsertabeller många resulterande tillstånd. Som ett resultat tillåter GLR-algoritmen skift/minska och reducera/minska konflikter.
När en konflikt uppstår, delas parserns stack (kollapslagring) i två eller flera parallella stackar, vars topptillstånd motsvarar varje möjlig övergång. I det följande används nästa inmatningssymbol för att bestämma nästa övergångar i topptillstånden för varje gren av stacken. I det här fallet kan det återigen bli nödvändigt att förgrena stapeln. Om det för något topptillstånd och ingångssymbol inte finns någon övergång (i parsertabellen), så anses denna gren av stacken vara felaktig och kasseras.
Grunden för optimering är möjligheten att dela delar av stacken med flera av dess grenar, vilket minskar den totala mängden minne som krävs för att analysera inmatningssekvensen. Den komplexa strukturen som blir resultatet av denna optimering gör att stacken ser mer ut som en riktad acyklisk graf än ett träd.
GLR-algoritmen har i värsta fall samma komplexitet som Kok-Younger-Kasami- algoritmen och Earley-algoritmen - O ( n³ ). GLR-algoritmen har dock två fördelar:
I praktiken är de flesta programmeringsspråk deterministiska eller "nästan deterministiska". Detta innebär att icke-determinism vanligtvis kan lösas genom att läsa ett litet (om än obegränsat) antal inmatade tecken. Jämfört med andra algoritmer som kan bearbeta hela klassen av kontextfria grammatiker (som den tidiga algoritmen eller Kok-Younger-Kasami- algoritmen), är GLR-algoritmen mer presterande på sådana "nästan deterministiska" grammatiker, eftersom endast en gren av stapeln.