LR(0) – Alulról felfelé haladó algoritmus környezetfüggetlen nyelvtanok elemzéséhez, az LR egyik típusa .
Az LR(0) ritkán használatos a gyakorlatban az elemzett nyelvtanok szűk osztálya miatt, de ez az alapja az erősebb SLR(1) és LALR(1) algoritmusoknak , amelyek közül az utóbbi gazdag gyakorlati alkalmazásokkal rendelkezik.
Mindhárom említett algoritmusnak ugyanaz a végrehajtási fázisa a bemeneti adatfolyamhoz, csak a nyelvtani elemző tábla elkészítésének fázisában térnek el egymástól.
Ez a végrehajtási fázis nagyon gyors (lineáris idő), képes elemezni az összes LALR(1) nyelvet, azaz szinte az összes használt programozási nyelvet. Ezen kívül képes „egy elemzetlen karakter ilyen és ilyen pozícióban” formájú érthető szintaktikai hibákat generálni, és ha az elemző tábla teljes sorában csak 1 eltolási művelet van, akkor a „ ilyen-olyan karaktert vártak”.
Az LR(0), SLR(1) és LALR(1) algoritmusokhoz való értelmező tábla felépítésének nagy bonyolultsága miatt általában egy értelmező generátort használnak, mint például a yacc , ha gyorsan kell manuálisan írni egy értelmezőt, használja a rekurzív süllyedés módszerét vagy az LL(1 )
Vezessük be a „lánc” fogalmát. Ez egy bizonyos szabály jobb oldala a nyelvtanban, és a benne lévő pozíció 0-tól N-ig (a jobb oldal hossza), az N pozíció azt jelenti - a szabály jobb oldalának végén túl. Jelölje az R(K, L) láncot, ahol K a szabály száma, L pedig a jobb oldali pozíció.
A láncot, ahol L = a K szabály jobb oldalának hossza, teljesnek nevezzük.
Vezessük be az "R(K, L) szimbólum" fogalmát, vagyis azt a szimbólumot, amelyre a karakterlánc mutat. Ez az L-edik karakter a K szabály jobb oldalán, a befejezett karakterlánc nem mutat semmilyen karakterre.
Vezessük be a "kezdeti láncok halmaza egy nemterminálishoz" fogalmát. A nem terminális A esetében a kezdeti láncok halmaza a következőket tartalmazza:
Vezessük be az „állam” fogalmát, mint láncok halmazát.
Vezessük be a "kezdeti állapot" fogalmát, mint az E szimbólum kezdeti láncainak halmazát, a nyelvtan kezdetét.
Vezessük be az „eltolódás” fogalmát, mint állapotból állapotba való átmenetet egy szimbólum (nem terminális vagy terminális) hatására. Az új állapot a régi állapotból épül fel, amikor az A szimbólum mentén a következőképpen váltunk:
Az eltolást lehetetlennek mondjuk, ha az eredmény üres halmaz.
A nyelvtan számára létrejön egy kezdeti állapot.
Továbbá minden terminálra és nem terminálra az összes lehetséges állapotot (lánchalmazt), amelyet a korábban ismert állapotokból való eltolással kapunk, megszerkesztjük. Ez eltávolítja az ismétlődő állapotokat.
Ezután egy elemző tábla épül fel, függőlegesen - állapotszámok (0 - kezdeti állapot), vízszintesen - szimbólumok (terminálok, nem terminálok és a „folyam vége” szimbólum).
Az eltolásokat a következőképpen írjuk be a táblázatba: ha a C szimbólum és az S állapot esetén lehetséges eltolás, akkor a cellába (az eltolás eredményeként kapott) „S-löket állapotba váltás” érték kerül beírásra ( S, C).
Ezt követően az S → E nyelvtan eleje lecserélésre kerül, és az új kezdetű S-hez a cellába (S, folyam vége) a „sucessful completion of parsing” (az elemzés sikeres befejezése) értéke kerül beírásra.
Továbbá a csökkentési műveletek (redukció) bekerülnek a táblázatba, csak a termináloknál, a következőképpen: ha van egy befejezett lánc S állapotban, akkor az „R szabály szerinti redukció, N hosszának jobb oldala” érték. karakterek” minden cellába beírva (S, terminál), a szabály bal oldaláról kapunk egy nem terminális C-t."
Egy cast beszúrására tett kísérletet egy már foglalt táblázatcellába (például abban az esetben, ha két teljes lánc van az állapotban) shift-cast konfliktusnak vagy cast-cast konfliktusnak nevezzük. Ebben az esetben egy LR(0) elemző építése nem lehetséges, de lehetséges a valamivel bonyolultabb SLR(1) vagy LALR(1) algoritmus használatával, amelyek csak abban különböznek egymástól, ahogy a castok bekerülnek a asztal.
Az analizátor verem használatos, ahol az állapotszámok, a bemeneti (terminálok és a folyam vége) és a kimeneti (szabályszámok) folyamok találhatók.
0 kerül először a verembe.
Továbbá, amíg nem érkezik szintaktikai hiba vagy az elemzés sikeres befejezése: