LALR-parser

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg
Broom icon.svg Der mangler kildehenvisninger i denne artikel.
Du kan hjælpe ved at angive kilder til de påstande som fremføres i artiklen.
Question book-4.svg
Scientist.svg Svært stof
Denne artikel omhandler svært stof. Der er endnu ikke taget hensyn til ikke-eksperter. Du kan hjælpe ved at skrive en letforståelig indledning.

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[redigér | redigér wikikode]

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[redigér | redigér wikikode]

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 ZS
r1 SS ± P ◊ ±
r2 S → ε ◊ ±
r3 SP ◊ ±
r4 PP × N ◊ ± ×
r5 PN ◊ ± ×

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[redigér | redigér wikikode]

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[redigér | redigér wikikode]

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[redigér | redigér wikikode]

De øvrige tilstande dannes efter de samme principper:

t1 Regel Handling
r0 ZS r0
r1 SS • ± 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[redigér | redigér wikikode]

t2 Regel Handling
r2 S → ε • r2

Tilstand t3[redigér | redigér wikikode]

t3 Regel Handling
r3 SP r3
r4 PP • × N t6

Tilstand t4[redigér | redigér wikikode]

t4 Regel Handling
r5 PN r5

Tilstand t5[redigér | redigér wikikode]

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

Tilstand t6[redigér | redigér wikikode]

t6 Regel Handling r4 PP × • N t8

Tilstand t7[redigér | redigér wikikode]

t7 Regel Handling
r1 SS ± P r1
r4 PP • × N t6

Tilstand t8[redigér | redigér wikikode]

t8 Regel Handling
r4 PP × N r4

Aktionstabeller[redigér | redigér wikikode]

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[redigér | redigér wikikode]

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 : PN 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 : SS ± 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 : PN 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 : PP × 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 : ZS Z = 81
20 t0 [t0,Z] : accept output 81

Referencer[redigér | redigér wikikode]