GLR-parser

GLR-parser er en forkortelse for Generalized LR, hvor L står for left-to-right (venstre-til-høyre og r står for rightmost. Det er en utvidelse av en LR-parser for å håndtere en ikke-deterministisk og tvetydig grammatikk. Det teoretiske grunnlaget for den ble gitt i 1974 i en avhandling av Bernard Lang, sammen med andre generelle kontekstfrie parsere slik som GLL. Avhandlingen beskriver en systematisk måte å lage slike algoritmer på, og uniforme resultater angående korrekthetsbevis, kompleksiteten med hensyn til grammatikkens klasser og optimaliseringsteknikker. Den første implementasjon av GLR ble beskrevet i 1984 av Masaru Tomita, og ble også kalt en parallell parser. Tomita presenterte fem stadier, selv om det andre stadium i praksis er anerkjent som GLR-parseren.

Algoritmen har utviklet seg fra sin originale form, men prinsippene har forblitt uendret. Som vist i en publikasjon fra 1971, var Lang primært interessert i en enklere og mer fleksibel parser for utvidbare programmeringsspråk. Tomita's målsetning var å parse naturlige språk gjennomgående og effektivt. Alminnelige LR-parsere kan ikke håndtere den ikke-deterministiske og tvetydige natur hos naturlige språk, noe som GLR-parseren kan.

Referanser

Masaru Tomita. Efficient parsing for natural language. Kluwer Academic Publishers, Boston, 1986.

Kategori:Parsingalgoritmer
Kategori:Informatikkens historie
Kategori:Vitenskap i 1974
Kategori:Programvare fra 1984