LR-parser
En LR-parser er innenfor informatikken betegnelsen på en type parser (syntaktisk analysator). Det er en bunnen-opp parser som effektivt håndterer deterministiske kontekstfrie språk i en lineært avgrenset tid.[1] Vanlige varianter av LR-parsere er LALR-parsere og 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 (Left to right) betyr at parseren leser teksten fra venstre til høyre uten en sikkerhetskopi, og produserer en høyrederivering (reversed Rightmost derivation) eller et parsertre gjennom bunnen-opp-parsing. De mest detaljerte delene av 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 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 menneskelige språk som behøver mer fleksible (og tregere) metoder. For naturlige språk brukes GLR-parsere, CYK-algoritmen eller Earley-parsere.
De ovenfor nevnte egenskaper til L, R og k deles i realiteten av alle skift-reduser-parsere, inkludert presedens-parsere. LR-navnet brukes likevel vanligvis om den form for parsing som ble oppfunnet av Donald Knuth,[1] uten å innbefatte tidligere presendens-metoder, som for eksempel operatorpresendens-parsere. 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 parsere.
Referanser[rediger | rediger kilde]
- ^ a b Knuth 1965
Litteratur[rediger | rediger kilde]
- Donald Ervin Knuth (1965). On the translation of languages from left to right (PDF). Information and Control, volume 8, issue 6, juli 1965. s. 607–639.