Redigerer 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 [[Tvetydighet (grammatikk)|tvetydig]] grammatikk. Det teoretiske grunnlaget for den ble gitt i 1974 i en avhandling av Bernard Lang<ref name="Lang74" />, 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]],<ref name="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,<ref name="Lang71"/> var Lang primært interessert i en enklere og mer fleksibel parser for utvidbare [[programmeringsspråk]]. Tomita's målsetning var å parse [[Naturlig språk|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==
<references>
<ref name="Lang71">{{cite journal|last=Lang|first=Bernard|title=Parallel non-deterministic bottom-up parsing|journal=ACM SIGPLAN Notices|date=desember 1971|volume=6|series=Proceedings of the international symposium on Extensible languages|issue=12|pages=56–57|doi=10.1145/942582.807982|url=https://www.researchgate.net/publication/255677839_Parallel_non-deterministic_bottom-up_parsing}}</ref>
<ref name="Lang74">{{cite journal|last=Lang|first=Bernard|title=Deterministic techniques for efficient non-deterministic parsers|journal=Automata, Languages and Programming, 2nd Colloquium|year=1974|volume=14|series=Lecture Notes in Computer Science|pages=255–269|doi=10.1007/3-540-06841-4_65|editor1-first=J.|editor1-last=Loeckx|publisher=Springer|location=Saarbrücken|issn=0302-9743|url=https://www.researchgate.net/publication/220898271_Deterministic_Techniques_for_Efficient_Non-Deterministic_Parser}}</ref> 
<ref name="Tomita">Masaru Tomita. Efficient parsing for natural language. Kluwer Academic Publishers, Boston, 1986.</ref>
</references>

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