LR-parser
LR - parsere , også kjent som LR-parsere , er en klasse enheter for å manipulere noen kontekstfrie grammatikker . De tilhører familien av bottom-up parsere, siden de utgjør syntakstreet fra bladene til roten. De bruker reduksjonsforskyvningsanalyseteknikken. Det er tre typer LR-parsere: SLR(K), LALR(K) og kanoniske LR(K).
En LR-parser består av:
- et driverprogram
- En oppføring
- En utgang
- En analysetabell som består av to deler (ACTION og GOTO).
Det skal bemerkes at driverprogrammet alltid er det samme, og varierer bare parsetabellen for hvert språk.
Algoritmen for å gjenkjenne strenger er som følger: gitt det første tegnet i strengen og den opprinnelige tilstanden til tabellen, slå opp hvilken handling som tilsvarer den i handlingstabellen.
Hvis tilstanden er shiif n ( n ∈ N), skyves tegnet og tilstandsnummeret n inn på stabelen, neste tegn leses og prosedyren gjentas, men denne gangen søkes den tilsvarende tilstanden.
Hvis HANDLING = REDUSERE n ( n ∈ N), blir like mange tupler (tilstand, symbol) som lengden på køen til den n.-plasserte produksjonen hoppet av stabelen og erstattet av hodet til denne produksjonen. Den nye tilstanden oppnås ved å slå opp GOTO-tabellen ved å bruke tilstandsnummeret som er igjen på toppen av stabelen, og ikke-terminalen øverst. I ACTION-tabellen finner du også ACCEPT (som tar strengen som gyldig) og analysen avsluttes eller ERROR (som avviser strengen).
Algoritme for å generere en LR(0)-automat
For å generere en LR(0) -automat basert på en G-grammatikk, må du først definere:
- Utvidet grammatikk : Gitt en grammatikk G, er den utvidede grammatikken G'a definert:
1. Legg til en produksjon S'->S#, der S er startsymbolet (# representerer slutten av strengen).
2. Alle produksjoner sendes til konfigurasjonselementer med prikk i begynnelsen av køen.
3. Definer S' som det første symbolet for grammatikken.
- Konfigurasjonselement - Et konfigurasjonselement er en produksjon som har et spesialtegn (vanligvis et punktum) et sted i køen. For eksempel: produksjonen S->ABC genererer følgende elementer: { S->.ABC, S->A.BC, S->AB.C S->ABC.}. Som vi vil se om et øyeblikk, og når vi snakker uformelt, representerer punktet det nåværende stedet der det kan finnes på et øyeblikk i analysen i en produksjon.
- Lukking av en vare : lukking av en vare er definert (og uformelt) a: gitt en vare S->A.cB (A, B e V*, ce Vt union VN) til settet dannet av
1. S->A.cB
2. Hvis c er en ikke-terminal, legges alle elementer med c i toppen av produksjonen og punktet i begynnelsen av halen til.
3. Hvis p er en vare som tilhører nedleggelsen, hører nedleggelsen av p til nedleggelsen så lenge den ikke lenger er lagt til.
Med andre ord, og for å forstå konseptet, representerer lukkingen av en vare alle produksjonene som kan brukes på en gyldig kjede fra varens punkt. Til slutt er konstruksjonen av automaten som følger:
- Grammatikken utvides.
- Gitt det innledende symbolet for den utvidede grammatikken, beregnes dens lukking og defineres som en starttilstand.
- For hver stat er produksjonene gruppert etter karakteren etter punktet; hvis tilstanden ennå ikke er definert, flyttes punktet ett tegn til høyre, den nye tilstanden opprettes med disse produksjonene og lukkingen av hver av dem, karakteren som var etter punktet i den opprinnelige tilstanden, er definert som karakteren av overgangen.
- Hvis staten har prikken på slutten i en eller annen produksjon, markeres denne tilstanden som en endelig tilstand for automaten.
- Det fortsetter til det ikke er flere mulige nye stater.
Strengt tatt er LR-automaten en deterministisk automat, selv om dens nytte generelt ligger i å være grunnlaget for konstruksjonen av LR(0)-tabellen.
Se også