GLR-parser

En GLR-parser (GLR står för "Generalized LR", där L står för "left-to-right" och R står för "rightmost (derivation)") är en förlängning av en LR-parseralgoritm för att hantera icke - deterministiska och tvetydiga grammatiker . Den teoretiska grunden gavs i en artikel från 1974 av Bernard Lang (tillsammans med andra generella kontextfria analyser som GLL). Den beskriver ett systematiskt sätt att producera sådana algoritmer och ger enhetliga resultat avseende korrekthetsbevis, komplexitet med avseende på grammatikklasser och optimeringstekniker. Den första faktiska implementeringen av GLR beskrevs i en tidning från 1984 av Masaru Tomita , den har också kallats en "parallell parser". Tomita presenterade fem stadier i sitt ursprungliga arbete, även om det i praktiken är det andra steget som erkänns som GLR-parser.

Även om algoritmen har utvecklats sedan dess ursprungliga former, har principerna förblivit intakta. Som framgår av en tidigare publikation var Lang främst intresserad av mer lättanvända och mer flexibla tolkar för utbyggbara programmeringsspråk . Tomitas mål var att analysera på naturligt språk grundligt och effektivt. Standard LR-parsers kan inte tillgodose den icke-deterministiska och tvetydiga naturen hos naturligt språk , och det kan GLR-algoritmen.

Algoritm

Kortfattat fungerar GLR-algoritmen på ett sätt som liknar LR-parseralgoritmen , förutom att, givet en viss grammatik, en GLR-parser kommer att bearbeta alla möjliga tolkningar av en given indata i en bredd-först-sökning . På fronten konverterar en GLR- parsergenerator en ingångsgrammatik till parsertabeller, på ett sätt som liknar en LR-generator. Däremot, där LR-parsetabeller endast tillåter en tillståndsövergång (med ett tillstånd och en inmatningstoken), tillåter GLR-parsetabeller flera övergångar. I själva verket tillåter GLR förskjutning/minska och minska/minska konflikter.

När en motstridig övergång påträffas, delas analysstacken i två eller flera parallella analysstaplar, där tillståndet som motsvarar varje möjlig övergång är överst. Sedan läses nästa inmatningstoken och används för att bestämma nästa övergång(er) för vart och ett av de "översta" tillstånden – och ytterligare forking kan inträffa. Om ett givet topptillstånd och inmatningstoken inte resulterar i minst en övergång, är den "sökvägen" genom parsetabellerna ogiltig och kan kasseras.

En avgörande optimering känd som en grafstrukturerad stack (GSS) tillåter delning av vanliga prefix och suffix för dessa stackar, vilket begränsar det totala sökutrymmet och minnesanvändningen som krävs för att analysera inmatad text. De komplexa strukturerna som uppstår från denna förbättring gör sökgrafen till en riktad acyklisk graf (med ytterligare begränsningar för "djupen" för olika noder), snarare än ett träd.

Fördelar

Igenkänning med användning av GLR-algoritmen har samma värsta tänkbara tidskomplexitet som CYK-algoritmen och Earley-algoritmen : O ( n ³ ). GLR har dock två ytterligare fördelar:

• Tiden som krävs för att köra algoritmen är proportionell mot graden av icke-determinism i grammatiken: på deterministiska grammatiker körs GLR-algoritmen i O ( n )-tid (detta är inte sant för Earley och CYK-algoritmerna, men den ursprungliga Earley-algoritmer kan modifieras för att säkerställa det)
• GLR-algoritmen är "online" – det vill säga, den förbrukar indatatoken i en specifik ordning och utför så mycket arbete som möjligt efter att ha konsumerat varje token (även sant för Earley).

I praktiken är grammatikerna för de flesta programmeringsspråk deterministiska eller "nästan deterministiska", vilket betyder att all icke-determinism vanligtvis löses inom ett litet (men möjligen obegränsat) antal tokens [ . Jämfört med andra algoritmer som kan hantera hela klassen av kontextfria grammatiker (som Earley eller CYK), ger GLR-algoritmen bättre prestanda på dessa "nästan deterministiska" grammatiker, eftersom endast en enda stack kommer att vara aktiv under majoriteten av analysprocess.

GLR kan kombineras med LALR (1)-algoritmen, i en hybridparser, vilket möjliggör ännu högre prestanda.

Se även

• Jämförelse av parsergeneratorer
• DMS Software Reengineering Toolkit
• GNU Bison , en parsergenerator som kan skapa LALR- och GLR-parsers

Vidare läsning

•   Grune, Dick; Jacobs, Ceriel JH (2008). Parsingtekniker . Springer Science+Business Media. ISBN 978-0-387-20248-8 .
• Tomita, Masaru (1984). "LR-tolkare för naturliga språk". KALLNING . 10:e internationella konferensen om beräkningslingvistik. s. 354–357.
• Tomita, Masaru (1985). "En effektiv kontextfri analysalgoritm för naturliga språk". IJCAI . Internationell gemensam konferens om artificiell intelligens. s. 756–764.