Wikipedia

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 redigér

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

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 redigér

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

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

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 redigér

t2 Regel Handling
r2 S → ε • r2

Tilstand t3 redigér

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

Tilstand t4 redigér

t4 Regel Handling
r5 P → N • r5

Tilstand t5 redigér

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

Tilstand t6 redigér

t6 Regel Handling r4 P → P × • N t8

Tilstand t7 redigér

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

Tilstand t8 redigér

t8 Regel Handling
r4 P → P × N • r4

Aktionstabeller redigér

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

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 redigér

Hentet fra "https://da.wikipedia.org/w/index.php?title=LALR-parser&oldid=11319684"