Wikipedia

LALR-parser

En LALR-parser eller Look-Ahead LR-parser er innenfor informatikken benevnelsen på en forenklet versjon av en kanonisk LR parser. Parseren brukes til en syntaktisk analyse av en tekst i henhold til et sett produksjonsregler som er spesifisert av den formelle grammatikken til et programmeringsspråk. Syntaksen i teksten analyseres bunnen-opp, med detaljer på laveste nivå før man analyserer den overordnede grammatiske struktur. «LR» betyr left-to-right (venstre til høyre) eller høyre-derivering i en kontekstfri grammatikk.

En LALR-parser ble første gang beskrevet av informatikeren Franklin DeRemer, i hans Ph.D.-avhandling Practical Translators for LR(k) languages fra oktober 1969.[1] Der skrev han om de praktiske vanskeligheter som på denne tiden var forbundet med å implementere LR(1)-parsere. En LALR-parser anerkjenner flere former for grammatikk enn en LR(0)-parser, men krever på samme tid det samme antallet tilstander for et språk som kan anerkjennes av begge typen parsere. Derfor krever LALR-parsere mindre minne enn LR(1)-parsere som ikke er LR(0). Det finnes LR(1)-språk som ikke kan håndteres av LALR-parsere; LALR-parsere er likevel tilstrekkelige for de fleste utbredte programmeringsspråk,[2] deriblant Java,[3] selv om grammatikken for mange språk er tvetydig.

Den opprinnelige beskrivelsen spesifiserte ingen algoritme for en slik parser med en formell grammatikk. De første algoritmene ble beskrevet i 1973.[4] I oktober 1982 publiserte DeRemer og Thomas Pennello en algoritme som produserte minne-effektive LALR-parsere.[5] LALR-parsere kan genereres automatisk med LALR-parsergeneratorer som Yacc eller GNU Bison. Den automatisk genererte kode kan deretter forbedres manuelt av håndskrevet kode.

Historie rediger

I juli 1965 ble LR-parseren (Left to Right, Rightmost derivation) oppfunnet av den amerikanske informatikeren Donald Ervin Knuth ved Stanford University. Denne parseren godtar ethvert deterministisk kontekstfritt språk i en lineært avgrenset tid.[6] Høyre-deriveringer har svært store minnekrav, og å implementere en LR-parser var upraktisk på denne tiden grunn av den begrensede mengden med RAM i datamaskiner.

For å løse dette problemet, foreslo informatikeren Franklin DeRemer ved Massachusetts Institute of Technology (MIT) i oktober 1969 to forenklede versjoner av LR-parseren, nemlig en Look Ahead LR (LALR) parser[1] og en Simpel LR-parser (SLR). Begge hadde mye mindre krav til RAM, men håndterte færre grammatikker, og LALR-parseren var den mest effektive av de to.[1]

I mai 1975 konverterte Bell Laboratories sin C-kompilator til LALR-algoritmen; denne kompilatoren ble tatt i bruk på UNIX versjon 6 og var tidligere blitt implementert ved hjelp av en rekursiv descendant parser.

I 1977 ble minneoptimaliseringer oppfunnet for LR-parseren, men fortsatt var den mindre minne-effektiv enn de forenklede versjonene.

Den 1. august 1977 utga Alfred Aho og Jeffrey Ullman den såkalte «drageboken»;[7] denne klassiske teksten som snart ble en lærebok i kompilatorteknikk, er kjent for sitt omslagsbilde av en ridder som bekjemper en drage. På ridderens lanse stod det skrevet LALR, og denne parseralgoritmen stod sentralt i boken.[7][8] Den 1. januar 1986 kom andre utgave med Ravi Sethi som medforfatter,[9] og den 10. september 2006 tredje utgave med Sethi og Monica Sin-Ling Lam som medforfattere.[10]

I 1979 kunngjorde Franklin DeRemer og Thomas Pennello en serie optimaliseringer for LALR-parseren som ville forbedre minne-effektiviteten.[5] Deres arbeid ble publisert i oktober 1982.[5]

UNIX versjon 7 ble lansert av Bell Laboratories den 11. januar 1979, og inkluderte den mest omfattende og lett tilgjengelige verktøykjede for kompilator-konstruksjon som noensinne er utviklet. Sentralt i denne verktøykjeden var Yacc, en LALR-parsergenerator. Operativsystemets hovedkompilator, Portable C Compiler (pcc), var også implementert ved hjelp av LALR. PCC var standard i Berkeley Software Distribution (BSD) frem til lanseringen av 4.4BSD i 1994, da den ble erstattet av GNU C Compiler (GCC). PCC ble også benyttet i FreeBSD, OpenBSD, NetBSD og av enkelte Linuxdistribusjoner.

Etter år 2000 har vi sett et paradigmeskifte bort fra LALR-parsere og tilbake til rekursive descendant parsere. Fordi LALR-parseren utfører høyrederivasjoner i stedet for den mer intuitive venstrederivasjon, er forståelsen av dens virkemåte svært vanskelig. Dette gjør det vanskelig og tidkrevende å finne den korrekte og effektive LALR-grammatikk. Av samme grunn er LALR-parseres feilmeldinger ikke alltid forståelige for sluttbrukere. Enhver LR(k > 0)-tabell gjør det likevel trivielt å oppliste de ulike gyldige token når en syntaksfeil inntreffer. Av denne grunn er en rekursiv descendant parser å foretrekke. Den krever mer håndskrevet kode fordi den skal anerkjenne språk på et lavere nivå. De har likevel ikke de spesielle vanskelighetene ved LALR-parsere, fordi de bruker venstrederivering.

Den 23. mai 1987 lanserte GNU første versjon av GNU C Compiler (GCC).[11] Kompilatoren var basert på en LALR-parser generert av Yacc. Den 6. mars 2006 lanserte GNU versjon 3.4.6 av GNU Compiler Collection (GCC).[12] Den Yacc-baserte LALR-parseren for C og C++ i tidligere versjoner, ble erstattet av en håndskrevet rekursivt descendant parser.[12] Denne parseren brukes fortsatt i versjon 13.2, som ble lansert 27. juli 2023.

Clang, som ble lansert 26. september 2007 som en konkurrent til GCC, har fra starten av benyttet en rekursiv descendant parser.[13] Versjon 18.1.4, som ble lansert 16. april 2024, bruker fortsatt denne parseren.

Den 18. desember 1987 lanserte Larry Wall den første versjonen av det funksjonelle skriptspråket Perl.[14] Dette språket har en større kompleksitet enn noen tidligere språk, og benytter seg aggressivt av en LALR-parser, produsert med Yacc.[15]

Den 19. juli 2000 startet arbeidet med Perl 6,[16] en radikal nyimplementasjon av dette språket. Rakudo Perl 6, med første lansering av både kompilatoren og dens moduler den 29. juli 2010, tar likeledes i bruk en rekursiv descendant parser som alternativ til LALR.[17]

Siste versjon er 2024.03 #170 som ble lansert 28. mars 2024. Også denne bruker en rekursiv descendant parser.

Oversikt rediger

Generelt refererer begrepet LALR-parser til en LALR(1)-parser, akkurat som begrepet LR-parser refererer til en LR(1)-parser.Tallet "(1)" er en referanse til et enkelt lookahead under parsingen. På samme måte finnes det LALR(2)-parsere med to lookahead, og LALR(k)-parsere med k antall lookahead, men de er sjeldent i bruk.

LALR(1)-parseren er basert på LR(0)-parseren, så den kan også betegnes som en LA(1)LR(0)-parser, eller mer generelt som en LA(k)LR(0)-parser. Der finnes en to-parameter-familie av LA(k)LR(j)-parsere, for alle kombinasjoner av j og k, som kan bli avledet av LALR(j +k), men disse er sjelden i praktisk bruk.

Som tilfellet er med andre LR-parsere, er LALR-parsere svært effektive i å finne den enkelte korrekte bunnen-opp parsing i et enkelt venstre-til-høyre scan av den innmatede strømmen, fordi den ikke trenger tilbakesporing. Den bruker alltid et lookahead, hvor LALR(1) er det vanligste.

Relasjonen til andre parsere rediger

LR-parsere rediger

LALR(1)-parseren er mindre kraftig enn LR(1)-parseren, og kraftigere enn SLR(1)-parseren, selv om de bruker de samme produksjonsreglene. Forenklingen som LALR(1)-parsere introduserer består i å slå sammen regler som har identiske kjerne-elementer, fordi lookahead ikke er kjent under prosessen med å konstruere LR(0). Dette reduserer parserens kraftfullhet, fordi det å ikke kjenne lookahead skaper usikkerhet om neste regel parseren skal velge og kan gi reduser/reduser-konflikter. Alle konflikter som oppstår i en LALR(1)-parser når den anvendes på en entydig LR(1)-grammatikk, er reduser/reduser-konflikter. SLR(1)-parseren foretar ytterligere sammenslåinger, noe som introduserer tilleggs-konflikter.

Standardeksempelet på en LR(1)-grammatikk som ikke kan bli parset av en LALR(1)-parser, og som gir en reduser/reduser-konflikt, er følgende:[18][19] 

  S → a E c
    → a F d
    → b F c
    → b E d
  E → e
  F → e

Under konstruksjonen av LALR-tabellen, vil to tilstander slå seg sammen til en, og etterpå vil lookahead bli tvetydig. Den ene tilstanden med lookahead er: 

  E → e. {c,d}
  F → e. {c,d}

En LR(1)-parser vil skape to forskjellige tilstander, hver med en lookahead som ikke er i konflikt, og ingen av dem er tvetydig. I en LALR-parser har denne ene tilstanden motstridende handlinger (gitt lookahead c eller d, reduser til E eller F), en reduser/reduser konflikt; den ovennevnte grammatikken vil bli erklært tvetydig av en LALR-parsergenerator og konflikter vil bli rapportert.

For å løse problemet, må tvetydigheten bli oppløst ved å velge E, fordi den intreffer før F i grammatikken. Den resulterende parser vil likevel ikke kunne gjenkjenne den gyldige innmatningsekvensen b e c, ettersom den tvetydige sekvensen e c er redusert til (E → e) c, snarere enn den korrekte (F → e) c, men b E c finnes ikke i grammatikken.

LL-parsere rediger

LALR(k)-parsere er ikke sammenlignbare med LL(k)-parsere: for enhver j og k som begge er større enn 0, finnes det en LALR(j)-grammatikk som ikke er en LL(k)-grammatikk, og omvendt. Faktisk er det ubestemmelig hvorvidt en gitt LL(1)-grammatikk er LALR(k) for enhver  .[2]

Avhengig av nærværet av tomme derivasjoner, kan en LL(1)-grammatikk være identisk med en SLR(1) eller en LALR(1)-grammatikk. Hvis LL(1)-grammatikken ikke har noen tomme derivasjoner, er den SLR(1) og hvis alle symboler med tomme derivasjoner har ikke-tomme derivasjoner, er det LALR(1). Hvis symbolene som bare har en tom derivasjon eksisterer, kan ikke kan grammatikken være LALR(1).[20]

Referanser rediger

  1. ^ a b c DeRemer 1969
  2. ^ a b Chapman 1988, s. 86-87
  3. ^ Generate the Parser". Eclipse JDT Project.
  4. ^ Anderson 1973
  5. ^ a b c DeRemer 1982
  6. ^ Knuth 1965
  7. ^ a b Aho 1977
  8. ^ Aho 1986 side 215–247
  9. ^ Aho 1986
  10. ^ Aho 2006
  11. ^ GCC Releases, Free Software Foundation, Inc., 16. juli 2015
  12. ^ a b GCC 3.4 Release Series. Changes, New Features, and Fixex, gnu.org, 6. mars 2006
  13. ^ Kevin Hu's Blog: What Parsers Are They Using?, 24. november 2014
  14. ^ Larry Wall: v13i001: Perl, a "replacement" for awk and sed, Part01/10, nyhetsgruppen comp.sources.unix, 1. februar 1988
  15. ^ casiano: Yacc is dead, perlmonks.org, 8. desember 2010
  16. ^ Kline, Joe: Report from the Perl Conference, perl.com, 21. august 2000
  17. ^ IRC log for #parrot, 2010-03-03 Arkivert 6. mars 2016 hos Wayback Machine., irclog.org, 3. mars 2010
  18. ^ "7.9 LR(1) but not LALR(1) Arkivert 4. august 2010 hos Wayback Machine.", CSE 756: Compiler Design and Implementation Arkivert 23. juli 2010 hos Wayback Machine., Eitan Gurari, Spring 2008
  19. ^ Vorčák 2011
  20. ^ Beatty 1979

Litteratur rediger

Hentet fra «https://no.wikipedia.org/w/index.php?title=LALR-parser&oldid=24407244»