LALR-parser

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

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

Nr	Regel	Terminatorer
r0	Z → S	◊
r1	S → S ± P	◊ ±
r2	S → ε	◊ ±
r3	S → P	◊ ±
r4	P → P × N	◊ ± ×
r5	P → 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:

t0	Regel	Handling
	• Z	accept
r0	Z → • S	t1
r1	S → • S ± P	t1
r2	S → • ε	t2
r3	S → • P	t3
r4	P → • P × N	t3
r5	P → • N	t4

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:

t1	Regel	Handling
r0	Z → S •	r0
r1	S → S • ± P	t5

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

t2	Regel	Handling
r2	S → ε •	r2

Tilstand t3

t3	Regel	Handling
r3	S → P •	r3
r4	P → P • × N	t6

Tilstand t4

t4	Regel	Handling
r5	P → N •	r5

Tilstand t5

t5	Regel	Handling
r1	S → S ± • P	t7
r4	P → • P × N	t7
r5	P → • N	t4

Tilstand t6

t6	Regel	Handling	r4	P → P × • N	t8

Tilstand t7

t7	Regel	Handling
r1	S → S ± P •	r1
r4	P → P • × N	t6

Tilstand t8

t8	Regel	Handling
r4	P → P × N •	r4

Aktionstabeller

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

tilstand	◊	±	×	N	S	P	Z
t0	t2	t2		t4	t1	t3	accept
t1	r0	t5
t2	r3	r3
t3	r2	r2	t6
t4	r5	r5	r5
t5				t4		t7
t6				t8
t7	r1	r1	t6
t8	r4	r4	r4

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

nr	Stak	Kildekø	Handling	Operation	Reduktion	Beregning
0		± N ± N × N		←t0
1	t0	± N ± N × N	[t0,±] : reducér		r2 : S → ε	S = 0
2	t0	± N ± N × N	[t0,S]	←t1 = [S,0]
3	t0 t1	± N ± N × N	[t1,±] : læs	←t5 = [±,-]
4	t0 t1 t5	N ± N × N	[t5,N] : læs	←t4 = [N,3]
5	t0 t1 t5 t4	± N × N	[t4,±] : reducér	t4→	r5 : P → N	P = 3
6	t0 t1 t5	± N × N	[t5,P]	←t7 = [P,3]
7	t0 t1 t5 t7	± N × N	[t7,±] : reducér	t7→ t5→ t1→	r1 : S → S ± P	S = 0 - 3 = -3
8	t0	± N × N	[t0,S]	←t1 = [S,-3]
9	t0 t1	± N × N	[t1,±] : læs	←t5 = [±,+]
10	t0 t1 t5	N × N	[t5,N] : læs	←t4 = [N,4]
11	t0 t1 t5 t4	× N	[t4,×] : reducér	t4→	r5 : P → N	P = 4
12	t0 t1 t5	× N	[t5,P]	←t7 = [P,4]
13	t0 t1 t5 t7	× N	[t7,×] : læs	←t6 = [×,*]
14	t0 t1 t5 t7 t6	N	[t6,N] : læs	←t8 = [N,21]
15	t0 t1 t5 t4 t6 t8		[t8,◊] : reducér	t8→ t6→ t4→	r4 : P → P × N	P = 4 • 21 = 84
16	t0 t1 t5		[t5,P]	←t7 = [P,84]
17	t0 t1 t5 t7		[t7,◊] : reducér	t7→ t5→ t1→	r1 : S ± P	S = -3 + 84 = 81
18	t0		[t0,S]	←t1 = [S,81]
19	t0 t1		[t1,◊] : reducér	t1→	r0 : Z → S	Z = 81
20	t0		[t0,Z] : accept	output 81

Referencer

• 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 from ACM.org