Redigerer LR-parser

En '''LR-parser''' er innenfor [[informatikk]]en betegnelsen på en type [[parsing|parser]] (syntaktisk analysator). Det er en [[bunnen-opp parsing|bunnen-opp parser]] som effektivt håndterer [[deterministiske kontekstfrie språk]] i en lineært avgrenset tid.<ref name="Knuth1965"/> Vanlige varianter av LR-parsere er [[LALR-parser]]e og [[Simpel LR-parser|simple LR-parsere]]. LR-parsere er blitt benyttet i prosesseringen av en rekke [[programmeringsspråk]]. De blir ofte generert automatisk av [[parsergeneratorer]], som leser en [[formell grammatikk]] for det aktuelle programmeringsspråk. Eksempler på slike parsergeneratorer er [[Yacc]] og [[GNU Bison]].

Navnet '''LR''' er en [[initialisme]], der '''L''' ('''''L'''eft to right'') betyr at [[parsing|parser]]en leser teksten fra venstre til høyre uten en sikkerhetskopi, og produserer en [[Kontekstfri grammatikk|høyrederivering]] (''reversed '''R'''ightmost derivation'') eller et parsertre gjennom [[bunnen-opp-parsing]]. De mest detaljerte delene av [[Tre (datastruktur)|treet]] (løvnodene) er i bunnen, de større strukturene som er bygd opp av den befinner seg i lenger opp, og roten er øverst.

Navnet LR blir ofte etterfulgt av en numerisk kvalifikator som eksempelvis '''LR(1)''' eller '''LR(''k'')'''. LR(1)-parsere blir også kalt [[kanonisk LR-parser|kanoniske LR-parsere]]. For å unngå [[tilbakesporing]] eller gjetting, har LR-parseren lov til å se fremover i innmatingsstrømmen ''k'' symboler før den bestemmer seg for hvordan den vil parse tidligere symboler. Vanligvis er ''k'' lik 1 og er ikke nevnt.

LR-parsere er deterministiske. De produserer en enkel, korrekt parsing, uten gjetting eller tilbakesporing, i en lineært avgrenset tid. Dette er ideelt for programmeringsspråk, men uegnet for [[Naturlig språk|menneskelige språk]] som behøver mer fleksible (og tregere) metoder. For naturlige språk brukes [[GLR-parser]]e, [[CYK-algoritmen]] eller [[Earley-parser]]e.

De ovenfor nevnte egenskaper til '''L''', '''R''' og '''k''' deles i realiteten av alle [[skift-reduser]]-parsere, inkludert [[presedens-parser]]e. LR-navnet brukes likevel vanligvis om den form for parsing som ble oppfunnet av [[Donald Knuth]],<ref name="Knuth1965"/> uten å innbefatte tidligere presendens-metoder, som for eksempel [[operatorpresendens-parser]]e. LR-parsere kan håndtere flere språk og grammatikker enn presedens-parsere eller [[LL-parsere]]; sistnevnte foretar venstrederiveringer av parsertreet gjennom [[ovenfra-ned parsing]], og brukes eksempelvis i [[rekursiv descendant parser|rekursiv descendant parsere]].


==Referanser==
<references>
<ref name="Knuth1965">[[#Knuth1965|Knuth 1965]]</ref>
</references>

==Litteratur==
*{{Kilde bok
  | ref=Knuth1965 
  | forfatter=[[Donald Knuth|Donald Ervin Knuth]]
  | utgivelsesår=1965
  | artikkel=
  | redaktør=
  | tittel=On the translation of languages from left to right
  | side=607–639
  | forlag=Information and Control, volume 8, issue 6, juli 1965
  | url=http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf
}}

{{stubb}}
{{Autoritetsdata}}

[[Kategori:Parsingalgoritmer]]
[[Kategori:Informatikkens historie]]
[[Kategori:Stanford University]]
[[Kategori:IT-relaterte introduksjoner i 1965]]
[[Kategori:Vitenskap i 1965]]
[[Kategori:1965 i USA]]