Der er for få eller ingenkildehenvisninger i denne artikel,hvilket er et problem. Du kan hjælpe ved at angivetroværdige kilder til de påstande, som fremføres i artiklen.

Denne artikel omhandlersvært stof. Der er endnu ikke taget hensyn til ikke-eksperter. Begrundelsen kan findes pådiskussionssiden eller i artikelhistorikken. Du kan hjælpe ved at skrive en letforståelig indledning. (Lær hvordan og hvornår man kan fjerne denne skabelonbesked)

EnLALR parser er etdatalogisk begreb for enparser. En parser er et program, som genkender kode skrevet i et programmeringssprog og derved gør det muligt at producere oversat kode – f.eks.C – eller en fortolker – f.eks.JavaScript.

LALR står forLook Ahead, Left to right, Rightmost derivation.

Look Ahead – ellerse fremad – betyder, at parseren ser på nogle af de efterfølgende symboler i koden, før den beslutter sig for, hvordan en konkret del af koden skal fortolkes.

Det forstås bedst ved et eksempel: I et program skal to tal lægges sammen; parseren har fået præsenteret kodestrengen:

17 + 25

Umiddelbart ser det ud som om, at det giver 42, men hvis det næste tegn er et gangetegn, så bliver resultatet et andet:

17 + 25*3

Fordi der kommer et gangetegn efter 25 må parseren vente med at udføre additionen til multiplikationen er udført. Hvis det næste tegn havde været et minus, som i:

17 + 25 – 4

ville det have været korrekt at udføre additionen først, og derefter udføre subtraktionen.

En LALR(1)-parser, som er i stand til at se 1 symbol frem, er i stand til at genkende situationer som disse.

Det er muligt at bygge parsere, som kan se flere tegn frem. En parser, der ser 2 tegn frem, ville hedde LALR(2). I moderne programmeringssprog foretrækker man dog at indrette syntaksen, så de kan parses med LALR(1)-parsere. Da de fleste LALR-parsere derfor er LALR(1) vil LALR ofte være synonymt med LALR(1).

En LALR parser kan produceres automatisk ud fra beskrivelsen af en syntaks;Yacc er et eksempel på et program, der gør det. Det er muligt, men ikke særligt nemt, at lave en LALR-parser uden at have et værktøj til det.

For at vise princippet vises her hvordan man kan lave en LALR-parser ud fra beskrivelsen af syntaksen for et yderst simpelt sprog. Det består af heltal og tegnene + (plus), – (minus), * (gange) og / (division). Inden LALR parseren får koden, er den blevet analyseret af en leksikalsk analysator; den fortolker teksten som tokens:

• + og – genkendes som ±
• * og / genkendes som ×
• heltal sammensat af 0, 1, 2, 3, 4, 5, 6, 7, 8 og 9 genkendes somN

De tre grundtokens,N, ± og ×, kan kombineres til de afledte tokensP (produkt),S (sum) ogZ (hele koden). Regel r5 siger f.eks., atP kan væreN (et heltal), og regel r4 siger, atP også kan være produktet afP ogN.

Der er desuden et pseudotoken, ε, som betyder, at et token kan være en tom plads. Det benyttes i regel r2, som siger, atS kan være en tom plads.

KolonnenTerminatorer viser hvilke tokens, der kan komme umiddelbart efter det token, der står på venstre side i reglen. Tegnet ◊ betyder, at der måske ikke kommer flere tegn. At der efterP (regel r4 og r5) kan komme et × ses af regel r4; at der også kan komme et ± ses af regel r3, som siger atP kan være etS og regel r1. Der kan ikke komme et × efterS, og der kan ikke komme nogen tegn efterZ.

Parseren fungerer som en endelig automat. Den skifter mellem et antal tilstande efterhånden som kildekodens tokens læses. Disse tilstande kan findes ud fra beskrivelsen af syntaksen.

Den første tilstand findes ved at gå ud fra, at hele kildekoden,Z, skal læses. Det skrives:

•Z

DaZ kan væreS i følge regel r0, er det muligvis samtidigS, der læses. Det kan skrives:

Z → •S

På denne måde ekspanderes listen vha. alle relevante regler. Det bliver til:

NårZ er læst, er hele kildekoden accepteret; det angives med ordetaccept. For hvert af de øvrige mulige tokens, som kan læses som det næste, skal der være en ny tilstand. Der henvises til dem i kolonnenHandling.

De øvrige tilstande dannes efter de samme principper:

Når en regel, som i denne tilstand regel r0, er læst færdig, så indsættes reglen som reduktion i kolonnenHandling.

Informationerne omnæste tilstand ogregel fra tilstandene samles i en aktionstabel, som styrer parseren:

Ofte har man to tabeller: enshift/reduce tabel svarende til de fire første kolonner (◊, ±, × ogN) og engo to tabel, svarende til de tre sidste kolonner (S,P ogZ).

I de tomme felter, som svarer til tokens som ikke forventes på det pågældende sted, kan man indsætte fejlmeddelelser. De er udeladt her for overskuelighedens skyld.

For at illustrere hvordan aktionstabellen bruges vises hvordan denne kildekode parses:

– 3 + 4 * 21

Kildekoden skal først læses af enleksikalsk analysator. Her genkendes de enkelte tekstelementer som tokens. Det genkendte token gemmes sammen med den tilsvarende tekst. Det kan vises som en kø af objekter:

[±,-] [N,3] [±,+] [N,4] [×,*] [N,21]

Af hensyn til overskueligheden vises denne kø i denne forkortede udgave i den følgende oversigt:

±N ±N ×N

• Compilers: Principles, Techniques, and Tools,Aho,Sethi,Ullman,Addison-Wesley, 1986.ISBN 0-201-10088-6. An extensive discussion of LR parsing and the principal source for some sections in this article.
• CS.VU.nl, Parsing Techniques – A Practical Guide web page of book includes downloadable pdf.
• The Functional Treatment of Parsing (Boston: Kluwer Academic, 1993), R. Leermakers,ISBN 0-7923-9376-7
• The theory of parsing, translation, and compiling, Alfred V. Aho and Jeffrey D. Ullman, available fromACM.org

• Implementation af programmeringssprog

• Kilder mangler (samlet liste)
• Kilder mangler siden Uge 43, 2010
• Artikler med avanceret sprog