LR(0) — Bottom-up-algoritm för att analysera kontextfria grammatiker , en av typerna av LR .
LR(0) används sällan i praktiken på grund av den smala klassen av analyserade grammatiker, men är grunden för de mer kraftfulla algoritmerna SLR(1) och LALR(1) , av vilka den senare har rika praktiska tillämpningar.
Alla tre nämnda algoritmer har samma exekveringsfas för ingångsströmmen, och skiljer sig endast i fasen för att konstruera analystabellen för grammatiken.
Denna exekveringsfas är mycket snabb (linjär tid), kan tolka alla LALR(1)-språk, dvs nästan alla programmeringsspråk som används. Dessutom är den kapabel att generera begripliga syntaxfel av formen "ett oparsat tecken sådan och sådan i sådan och sådan position" och, om det bara finns en skiftoperation i hela raden i analystabellen, av formen " sådan och sådan karaktär förväntades”.
På grund av den höga komplexiteten i att bygga en analystabell för LR(0), SLR(1) och LALR(1) algoritmerna, används vanligtvis en generator av parsers som yacc för detta , om du snabbt behöver skriva en parser manuellt, använd den rekursiva descentmetoden eller LL(1 )
Låt oss introducera begreppet "kedja". Detta är den högra sidan av en viss regel i grammatiken, och positionen i den, från 0 till N (längden på höger sida), betyder positionen N - bortom slutet av den högra sidan av regeln. Beteckna kedjan R(K, L), där K är numret på regeln och L är positionen på höger sida.
Kedjan, där L = längden på den högra sidan av regeln K, kallas komplett.
Låt oss introducera begreppet "symbol R(K, L)", det vill säga symbolen som strängen pekar på. Detta är det L:te tecknet från höger sida av regeln K. Den färdiga strängen pekar inte på något tecken.
Låt oss introducera begreppet "en uppsättning initiala kedjor för en icke-terminal". För icke-terminal A inkluderar uppsättningen av initiala kedjor:
Låt oss introducera begreppet "stat" som en uppsättning kedjor.
Låt oss introducera begreppet "initial state" som en uppsättning initiala kedjor av symbolen E, början av grammatiken.
Låt oss introducera begreppet "skifte" som en övergång från tillstånd till tillstånd under verkan av en symbol (icke-terminal eller terminal). Det nya tillståndet byggs från det gamla tillståndet när man skiftar längs symbolen A enligt följande:
Ett skifte sägs vara omöjligt om resultatet är en tom uppsättning.
För grammatiken konstrueras ett initialtillstånd.
Vidare, för alla terminaler och icke-terminaler, konstrueras alla möjliga tillstånd (uppsättningar av kedjor) erhållna genom skiftning från tidigare kända tillstånd. Detta tar bort duplicerade tillstånd.
Därefter byggs en analystabell, vertikalt - tillståndsnummer (0 - initialtillstånd), horisontellt - symboler (terminaler, icke-terminaler och symbolen för "strömslut").
Förskjutningar läggs in i tabellen enligt följande: om en förskjutning är möjlig för symbolen C och tillståndet S, skrivs värdet "skift till S-taktstillståndet" (erhållet som ett resultat av förskjutningen) in i cellen ( S, C).
Därefter ersätts början av grammatiken S → E, och för den nya början S skrivs värdet "lyckat slutförande av analys" in i cellen (S, slutet av strömmen).
Vidare skrivs reduceringsåtgärderna (reducera) in i tabellen, endast för terminaler, enligt följande: om det finns en fullbordad kedja i tillstånd S, då värdet "reduktion enligt regeln R, den högra sidan av längden på N tecken" skrivs in i alla celler (S, terminal), får vi ett icke-terminalt C från vänster sida av regeln."
Ett försök att infoga en cast i en redan upptagen tabellcell (till exempel i fallet med två kompletta kedjor i staten) kallas en shift-cast-konflikt eller en cast-cast-konflikt. I det här fallet är det inte möjligt att bygga en LR(0)-parser, men det kan vara möjligt att bygga med hjälp av den något mer komplexa SLR(1)- eller LALR(1)-algoritmen, som bara skiljer sig i hur casten läggs in i tabell.
Analysatorstacken används, där tillståndsnumren, ingångsströmmarna (terminaler och slutet av strömmen) och utgångsströmmar (regelnummer) finns.
0 skjuts först på stapeln.
Vidare, tills ett syntaxfel eller framgångsrikt slutförande av analys tas emot: