LR(0) — Bottom-up-algoritme til at analysere kontekstfri grammatikker , en af typerne af LR .
LR(0) bruges sjældent i praksis på grund af den snævre klasse af parsede grammatikker, men er grundlaget for de mere kraftfulde algoritmer SLR(1) og LALR(1) , hvoraf sidstnævnte har rige praktiske anvendelser.
Alle tre nævnte algoritmer har den samme udførelsesfase for inputstrømmen, idet de kun adskiller sig i fasen med at konstruere parsetabellen for grammatikken.
Denne udførelsesfase er meget hurtig (lineær tid), i stand til at parse alle LALR(1) sprog, dvs. næsten alle programmeringssprog i brug. Derudover er den i stand til at generere forståelige syntaksfejl af formen "en uparset karakter sådan og sådan i sådan og sådan en position" og, hvis der kun er 1 skiftoperation i hele linjen i parsingstabellen, af formen " sådan og sådan en karakter var forventet”.
På grund af den høje kompleksitet ved at bygge en parse-tabel til LR(0), SLR(1) og LALR(1) algoritmerne, bruges en generator af parsere som yacc normalt til dette , hvis du hurtigt skal skrive en parser manuelt, brug den rekursive descent-metode eller LL(1 )
Lad os introducere begrebet "kæde". Dette er højre side af en bestemt regel i grammatikken, og positionen i den, fra 0 til N (længden af højre side), betyder positionen - ud over slutningen af højre side af reglen. Betegn kæden R(K, L), hvor K er tallet på reglen og L er positionen i højre side.
Kæden, hvor L = længden af højre side af reglen K, kaldes komplet.
Lad os introducere begrebet "symbol R(K, L)", det vil sige det symbol, som strengen peger på. Dette er det L'te tegn fra højre side af reglen K. Den færdige streng peger ikke på noget tegn.
Lad os introducere begrebet "et sæt indledende kæder for en ikke-terminal". For ikke-terminal A omfatter sættet af indledende kæder:
Lad os introducere begrebet "stat" som et sæt af kæder.
Lad os introducere begrebet "indledende tilstand" som et sæt af indledende kæder af symbolet E, begyndelsen af grammatikken.
Lad os introducere begrebet "skift" som en overgang fra tilstand til tilstand under påvirkning af et symbol (ikke-terminal eller terminal). Den nye tilstand er bygget ud fra den gamle tilstand, når der skiftes langs symbolet A som følger:
Et skift siges at være umuligt, hvis resultatet er et tomt sæt.
For grammatikken konstrueres en begyndelsestilstand.
Yderligere, for alle terminaler og ikke-terminaler, konstrueres alle mulige tilstande (sæt af kæder) opnået ved at skifte fra tidligere kendte tilstande. Dette fjerner duplikerede tilstande.
Dernæst bygges en parsing-tabel, lodret - tilstandsnumre (0 - begyndelsestilstand), horisontalt - symboler (terminaler, ikke-terminaler og "end of stream"-symbolet).
Forskydninger indtastes i tabellen som følger: Hvis en forskydning er mulig for symbolet C og tilstanden S, indtastes værdien "skift til S-slagtilstand" (opnået som et resultat af forskydningen) i cellen ( S, C).
Dernæst erstattes begyndelsen af grammatikken S → E, og for den nye begyndelse S, indtastes værdien "succesfuld afslutning af parsing" i cellen (S, slutningen af strømmen).
Yderligere er reduktionshandlingerne (reducer) indtastet i tabellen, kun for terminaler, som følger: hvis der er en fuldført kæde i tilstand S, så værdien "reduktion i henhold til reglen R, højre side af længden af N tegn" indtastes i alle celler (S, terminal), får vi et ikke-terminalt C fra venstre side af reglen."
Et forsøg på at indsætte en cast i en allerede optaget bordcelle (for eksempel i tilfælde af to komplette kæder i staten) kaldes en shift-cast-konflikt eller en cast-cast-konflikt. I dette tilfælde er det ikke muligt at bygge en LR(0)-parser, men det kan være muligt at bygge ved hjælp af den lidt mere komplekse SLR(1)- eller LALR(1)-algoritme, som kun adskiller sig i den måde, hvorpå castene indtastes i bord.
Analysatorstakken bruges, hvor tilstandsnumrene, input (terminaler og slutningen af strømmen) og output (regelnumre) streams er placeret.
0 skubbes først på stakken.
Indtil en syntaksfejl eller en vellykket afslutning af parsing modtages: