LALR-parser

En LALR parser er et datalogisk begreb for en parser. 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 
LALR står for Look Ahead, Left to right, Rightmost derivation.

Look Ahead – eller se 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.

Beskrivelse af syntaks 

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 som N

De tre grundtokens, N, ± og ×, kan kombineres til de afledte tokens P (produkt), S (sum) og Z (hele koden). Regel r5 siger f.eks., at P kan være N (et heltal), og regel r4 siger, at P også kan være produktet af P og N.

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

Kolonnen Terminatorer 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 efter P (regel r4 og r5) kan komme et × ses af regel r4; at der også kan komme et ± ses af regel r3, som siger at P kan være et S og regel r1. Der kan ikke komme et × efter S, og der kan ikke komme nogen tegn efter Z.

Tilstande 
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.

Tilstand t0 
Den første tilstand findes ved at gå ud fra, at hele kildekoden, Z, skal læses. Det skrives:
 • Z
Da Z kan være S i følge regel r0, er det muligvis samtidig S, der læses. Det kan skrives:
 Z → • S
På denne måde ekspanderes listen vha. alle relevante regler. Det bliver til:

Når Z er læst, er hele kildekoden accepteret; det angives med ordet accept. 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 kolonnen Handling.

Tilstand t1 
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 kolonnen Handling.

Tilstand t2

Tilstand t3

Tilstand t4

Tilstand t5

Tilstand t6

Tilstand t7

Tilstand t8

Aktionstabeller 
Informationerne om næste tilstand og regel fra tilstandene samles i en aktionstabel, som styrer parseren:

Ofte har man to tabeller: en shift/reduce tabel svarende til de fire første kolonner (◊, ±, × og N) og en go to tabel, svarende til de tre sidste kolonner (S, P og Z).

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.

Eksempel 

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

 – 3 + 4 * 21

Kildekoden skal først læses af en leksikalsk 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

Referencer 
 Compilers: Principles, Techniques, and Tools, Aho, Sethi, Ullman, Addison-Wesley, 1986. . 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, 
 The theory of parsing, translation, and compiling, Alfred V. Aho and Jeffrey D. Ullman, available from ACM.org

Implementation af programmeringssprog