GLR-parser

Fra Wikipedia, den frie encyklopedi

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[1], 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,[2] 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,[3] 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[rediger | rediger kilde]

  1. ^ Lang, Bernard (1974). Loeckx, J., red. «Deterministic techniques for efficient non-deterministic parsers». Automata, Languages and Programming, 2nd Colloquium. Lecture Notes in Computer Science. Saarbrücken: Springer. 14: 255–269. doi:10.1007/3-540-06841-4_65. 
  2. ^ Masaru Tomita. Efficient parsing for natural language. Kluwer Academic Publishers, Boston, 1986.
  3. ^ Lang, Bernard (desember 1971). «Parallel non-deterministic bottom-up parsing». ACM SIGPLAN Notices. Proceedings of the international symposium on Extensible languages. 6 (12): 56–57. doi:10.1145/942582.807982.