https://www.wikisida.no/index.php?action=history&feed=atom&title=GLR-parserGLR-parser - Sideversjonshistorikk2026-06-09T21:25:38ZVersjonshistorikk for denne siden på wikienMediaWiki 1.45.1https://www.wikisida.no/index.php?title=GLR-parser&diff=108335&oldid=prevWikisida: Én sideversjon ble importert2026-03-27T03:59:39Z<p>Én sideversjon ble importert</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="nb">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Eldre sideversjon</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Sideversjonen fra 27. mar. 2026 kl. 03:59</td>
</tr><tr><td colspan="4" class="diff-notice" lang="nb"><div class="mw-diff-empty">(Ingen forskjell)</div>
</td></tr>
<!-- diff cache key c1wiki:diff:1.41:old-108334:rev-108335 -->
</table>Wikisidahttps://www.wikisida.no/index.php?title=GLR-parser&diff=108334&oldid=prev84.208.53.16 på 21. okt. 2017 kl. 06:312017-10-21T06:31:27Z<p></p>
<p><b>Ny side</b></p><div>'''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.<br />
<br />
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.<br />
<br />
==Referanser==<br />
<references><br />
<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><br />
<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> <br />
<ref name="Tomita">Masaru Tomita. Efficient parsing for natural language. Kluwer Academic Publishers, Boston, 1986.</ref><br />
</references><br />
<br />
[[Kategori:Parsingalgoritmer]]<br />
[[Kategori:Informatikkens historie]]<br />
[[Kategori:Vitenskap i 1974]]<br />
[[Kategori:Programvare fra 1984]]</div>84.208.53.16