Redigerer LALR-parser

En '''LALR-parser''' eller '''Look-Ahead LR-parser''' er innenfor [[informatikk]]en benevnelsen på en forenklet versjon av en [[kanonisk LR parser]]. [[Parsing|Parseren]] brukes til en [[syntaks|syntaktisk]] analyse av en tekst i henhold til et sett [[produksjon (informatikk)|produksjonsregler]] som er spesifisert av den [[formell grammatikk|formelle grammatikken]] til et [[programmeringsspråk]]. Syntaksen i teksten analyseres [[bunnen-opp-parsing|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 [[informatiker]]en [[Franklin DeRemer]], i hans [[filosofisk doktorgrad|Ph.D.-avhandling]] ''[https://web.archive.org/web/20130819012838/http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-065.pdf Practical Translators for LR(k) languages]'' fra oktober 1969.<ref name="DeRemer1969"/> 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,<ref name="Chapman1988"/> deriblant [[Java (programmeringsspråk)|Java]],<ref>Generate the Parser". Eclipse JDT Project.</ref> selv om grammatikken for mange språk er [[tvetydighet (grammatikk)|tvetydig]].

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

==Historie==
I juli 1965 ble [[LR-parser]]en (''Left to Right, Rightmost derivation'') oppfunnet av den [[usa|amerikanske]] [[informatiker]]en [[Donald Knuth|Donald Ervin Knuth]] ved [[Stanford University]]. Denne parseren godtar ethvert [[deterministiske kontekstfrie språk|deterministisk kontekstfritt språk]] i en lineært avgrenset tid.<ref name="Knuth1965"/> 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<ref name="DeRemer1969"/> 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.<ref name="DeRemer1969"/>

I mai 1975 konverterte [[Bell Laboratories]] sin [[C (programmeringsspråk)|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 «[[Principles of Compiler Design|drageboken]]»;<ref name="Aho1977"/> 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.<ref name="Aho1977"/><ref name="Aho1986_215_247"/> Den 1. januar 1986 kom [[Compilers: Principles, Techniques, and Tools|andre utgave]] med [[Ravi Sethi]] som medforfatter,<ref name="Aho1986"/> og den 10. september 2006 tredje utgave med Sethi og [[Monica Sin-Ling Lam]] som medforfattere.<ref name="Aho2006"/>

I 1979 kunngjorde Franklin DeRemer og [[Thomas Pennello]] en serie optimaliseringer for LALR-parseren som ville forbedre minne-effektiviteten.<ref name="DeRemer1982"/> Deres arbeid ble publisert i oktober 1982.<ref name="DeRemer1982"/>

[[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]]. [[Operativsystemet]]s 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 Compiler Collection|GNU C Compiler]] (GCC). PCC ble også benyttet i [[FreeBSD]], [[OpenBSD]], [[NetBSD]] og av enkelte [[Linuxdistribusjon]]er.

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 [[leksikalsk analyse|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).<ref>[https://gcc.gnu.org/releases.html GCC Releases],  Free Software Foundation, Inc., 16. juli 2015</ref> 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).<ref name="gcc34">[https://gcc.gnu.org/gcc-3.4/changes.html GCC 3.4 Release Series. Changes, New Features, and Fixex], gnu.org, 6. mars 2006</ref>  Den Yacc-baserte LALR-parseren for C og [[C++]] i tidligere versjoner, ble erstattet av en håndskrevet rekursivt descendant parser.<ref name="gcc34"/> Denne parseren brukes fortsatt i versjon 14.2, som ble lansert 1. august 2024.

[[Clang]], som ble lansert 26. september 2007 som en konkurrent til GCC, har fra starten av benyttet en rekursiv descendant parser.<ref>Kevin Hu's Blog: [https://blog.kevinhu.me/2014/11/24/24-what-parsers-are-they-using/ What Parsers Are They Using?], 24. november 2014</ref> Versjon 18.1.8, som ble lansert 18. juni 2024, bruker fortsatt denne parseren.

Den 18. desember 1987 lanserte [[Larry Wall]] den første versjonen av det [[funksjonell programmering|funksjonelle]] [[skriptspråk]]et [[Perl]].<ref>[[Larry Wall]]: [http://groups.google.com/group/comp.sources.unix/tree/browse_frm/month/1988-02?_done=%2Fgroup%2Fcomp.sources.unix%2Fbrowse_frm%2Fmonth%2F1988-02%3F& v13i001: Perl, a "replacement" for awk and sed, Part01/10], nyhetsgruppen comp.sources.unix, 1. februar 1988</ref> Dette språket har en større kompleksitet enn noen tidligere språk, og benytter seg aggressivt av en LALR-parser, produsert med Yacc.<ref>casiano: [http://www.perlmonks.org/?node_id=876097 Yacc is dead], perlmonks.org, 8. desember 2010</ref>

Den 19. juli 2000 startet arbeidet med [[Perl 6]],<ref>Kline, Joe: [http://www.perl.com/pub/a/2000/08/tpc4.html Report from the Perl Conference], perl.com, 21. august 2000</ref> 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.<ref>[http://irclog.perlgeek.de/parrot/2010-03-03 IRC log for #parrot, 2010-03-03] {{Wayback|url=http://irclog.perlgeek.de/parrot/2010-03-03 |date=20160306180409 }}, irclog.org, 3. mars 2010</ref>

Versjon 2024.08 #175 ble lansert 29. august 2024. Også denne bruker en rekursiv descendant parser.

==Oversikt==
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 ''[[parsing|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==
===LR-parsere===
LALR(1)-parseren er mindre kraftig enn LR(1)-parseren, og kraftigere enn SLR(1)-parseren, selv om de bruker de samme [[produksjon (informatikk)|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:<ref>"[http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht 7.9 LR(1) but not LALR(1)]   {{Wayback|url=http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht |date=20100804231352 }}", ''[http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht CSE 756: Compiler Design and Implementation] {{Wayback|url=http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht |date=20100723153301 }},'' Eitan Gurari, Spring 2008</ref><ref name="Vorcak2011"/>

   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 <code>b e c</code>, ettersom den tvetydige sekvensen <code>e c</code> er redusert til <code>(E → e) c</code>, snarere enn den korrekte <code>(F → e) c</code>, men <code>b E c</code> finnes ikke i grammatikken.

===LL-parsere===
LALR(''k'')-parsere er ikke sammenlignbare med [[LL-parsere|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-grammatikk|LL(''k'')-grammatikk]], og omvendt. Faktisk er det ubestemmelig hvorvidt en gitt LL(1)-grammatikk er LALR(''k'') for enhver <math>k > 0</math>.<ref name="Chapman1988"/>

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).<ref name="Beatty1979"/>

==Referanser==
<references>
<ref name="Aho1977">[[#Aho1977|Aho 1977]]</ref>
<ref name="Aho1986">[[#Aho1986|Aho 1986]]</ref>
<ref name="Aho1986_215_247">[[#Aho1986|Aho 1986 side 215&ndash;247]]</ref>
<ref name="Aho2006">[[#Aho2006|Aho 2006]]</ref>
<ref name="Anderson1973">[[#Anderson1973|Anderson 1973]]</ref>
<ref name="Beatty1979">[[#Beatty1979|Beatty 1979]]</ref>
<ref name="Chapman1988">[[#Chapman1988|Chapman 1988, s. 86-87]]</ref>
<ref name="DeRemer1969">[[#DeRemer1969|DeRemer 1969]]</ref>
<ref name="DeRemer1982">[[#DeRemer1982|DeRemer 1982]]</ref>
<ref name="Knuth1965">[[#Knuth1965|Knuth 1965]]</ref>
<ref name="Vorcak2011">[[#Vorcak2011|Vorčák 2011]]</ref>
</references>

==Litteratur==
*{{Kilde bok
  | ref=Aho1977 
  | forfatter=[[Alfred Aho|Aho, Alfred Vaino]]; [[Jeffrey Ullman|Ullman, Jeffrey David]]
  | utgivelsesår=1977
  | artikkel=
  | redaktør=
  | tittel= [[Principles of Compiler Design]]
  | side=
  | forlag=[[Addison-Wesley]], 1. august 1977
  | isbn=0-201-00022-9
}}
*{{Kilde bok
  | ref=Aho1986
  | forfatter=Aho, Alfred Vaino; Ullman, Jeffrey David; [[Ravi Sethi|Sethi Ravi]]
  | utgivelsesår=1986
  | artikkel=
  | redaktør=
  | tittel=[[Compilers: Principles, Techniques, and Tools]]
  | side=
  | forlag=Addison-Wesley, 1. januar 1986
  | isbn=0-201-10088-6
  | id=ISBN 978-0-201-10088-4
}}
*{{Kilde bok
  | ref=Aho2006
  | forfatter=Aho, Alfred Vaino; Ullman, Jeffrey David; Sethi Ravi; [[Monica Sin-Ling Lam|Lam, Monica Sing-Ling]]
  | utgivelsesår=2006
  | artikkel=
  | redaktør=
  | tittel=[[Compilers: Principles, Techniques, and Tools]]
  | side=
  | forlag=Addison-Wesley, 2. utgave, 10. september 2006
  | isbn=0-321-48681-1
  | id=ISBN 978-0-321-48681-3
}}
*{{Kilde bok
  | ref=Anderson1973 
  | forfatter=Anderson, Thomas; Eve, James; Horning, James, Jim
  | utgivelsesår=1973
  | artikkel=
  | redaktør=
  | tittel= Efficient LR(1) parsers
  | url=http://link.springer.com/article/10.1007/BF00571461#page-1
  | side=
  | forlag=Acta Informatica (2): 2–39, Springer-Verlag 1973
}}
*{{Kilde bok
  | ref=Beatty1979 
  | forfatter=Beatty, John C.
  | utgivelsesår=1979
  | artikkel=
  | redaktør=
  | tittel= On the relationship between LL(1) and LR(1) grammars
  | url=https://cs.uwaterloo.ca/research/tr/1979/CS-79-36.pdf
  | side=
  | forlag=Journal of the ACM 29 (4 (Oct)): 1007–1022, 4. oktober 1979
}}
*{{Kilde bok
  | ref=Chapman1988
  | forfatter=Chapman, Nigel P.
  | utgivelsesår=1988
  | artikkel=
  | redaktør=
  | tittel= LR Parsing: Theory and Practice (Cambridge Studies in Cultural Systems)
  | side=
  | forlag= Cambridge University Press, 29. januar 1988
  | isbn=0-521-30413-X
  | id=ISBN 978-0-521-30413-9
}}
*{{Kilde bok
 |ref           = DeRemer1969
 |forfatter     = [[Franklin DeRemer|DeRemer, Franklin Lewis]]
 |utgivelsesår = 1969
 |artikkel      = 
 |redaktør     = 
 |tittel        = Practical Translators for LR(k) languages
 |side          = 
 |url           = http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-065.pdf
 |forlag        = (Ph.D.). [[Massachusetts Institute of Technology]], [[Massachusetts]], 24. oktober 1969
 |url-status   = død
 |arkivurl      = https://web.archive.org/web/20130819012838/http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-065.pdf
 |arkivdato     = 2013-08-19
}}
*{{Kilde bok
  | ref=DeRemer1982 
  | forfatter=DeRemer, Franklin Lewis; [[Thomas Pennello|Pennello, Thomas]] 
  | utgivelsesår=1982
  | artikkel=
  | redaktør=
  | tittel=Efficient Computation of LALR(1) Look-Ahead Sets
  | side=
  | url=http://3e8.org/pub/scheme/doc/parsing/Efficient%20Computation%20of%20LALR%281%29%20Look-Ahead%20Sets.pdf
  | forlag=(PDF). Transactions on Programming Languages and Systems (ACM) 4 (4): 615–649, oktober 1982
}}
*{{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=
  | url=http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf
  | forlag=Information and Control, volume 8, issue 6, sidene 607–639, Juli 1965
}}
*{{Kilde bok
  | ref=Vorcak2011 
  | forfatter=Vorčák, Ján 
  | utgivelsesår=2011
  | artikkel=
  | redaktør=
  | tittel=Why is this LR(1) grammar not LALR(1)?
  | side=
  | url=http://stackoverflow.com/questions/8496065/why-is-this-lr1-grammar-not-lalr1
  | forlag=stackoverflow.com, 13. desember 2011
}}

{{Autoritetsdata}}

[[Kategori:Parsingalgoritmer]]
[[Kategori:Massachusetts Institute of Technology]]
[[Kategori:Informatikkens historie]]
[[Kategori:IT-relaterte introduksjoner i 1969]]
[[Kategori:Vitenskap i 1969]]
[[Kategori:1969 i USA]]