LR(0) — Algoritmus zdola nahoru pro analýzu bezkontextových gramatik , jeden z typů LR .
LR(0) se v praxi používá jen zřídka kvůli úzké třídě analyzovaných gramatik, ale je základem pro výkonnější algoritmy SLR(1) a LALR(1) , z nichž druhý má bohaté praktické aplikace.
Všechny tři zmíněné algoritmy mají stejnou fázi provádění pro vstupní proud, liší se pouze ve fázi konstrukce tabulky analýzy pro gramatiku.
Tato fáze provádění je velmi rychlá (lineární čas), schopná analyzovat všechny jazyky LALR(1), tedy téměř všechny používané programovací jazyky. Kromě toho je schopen generovat srozumitelné syntaktické chyby ve tvaru „neanalyzovaný znak takový a takový na takové a takové pozici“ a pokud je pouze 1 operace posunu v celém řádku parsovací tabulky, ve tvaru „ takový a takový charakter se očekával“.
Vzhledem k vysoké složitosti vytváření tabulky analýzy pro algoritmy LR(0), SLR(1) a LALR(1) se k tomu obvykle používá generátor parserů, jako je yacc , pokud potřebujete rychle napsat parser ručně, použijte metodu rekurzivního sestupu nebo LL(1 )
Pojďme si představit pojem „řetěz“. Toto je pravá strana určitého pravidla v gramatice a pozice v ní od 0 do N (délka pravé strany), pozice N znamená - za koncem pravé strany pravidla. Označme řetězec R(K, L), kde K je číslo pravidla a L je pozice na pravé straně.
Řetězec, kde L = délka pravé strany pravidla K, se nazývá úplný.
Představme si pojem „symbol R(K, L)“, tedy symbol, na který řetězec ukazuje. Toto je L-tý znak z pravé strany pravidla K. Dokončený řetězec neukazuje na žádný znak.
Pojďme si představit koncept "množiny počátečních řetězců pro neterminál". Pro neterminál A sada počátečních řetězců zahrnuje:
Představme si pojem „stát“ jako soubor řetězců.
Představme si pojem "počáteční stav" jako množinu počátečních řetězců symbolu E, začátku gramatiky.
Představme si pojem „posun“ jako přechod ze stavu do stavu působením symbolu (nekoncového nebo koncového). Nový stav se vytvoří ze starého stavu při posunu podél symbolu A takto:
Posun je prý nemožný, pokud je výsledkem prázdná množina.
Pro gramatiku je vytvořen počáteční stav.
Dále jsou pro všechny terminály a neterminály konstruovány všechny možné stavy (množiny řetězců) získané posunutím z dříve známých stavů. Tím se odstraní duplicitní stavy.
Dále se vytvoří tabulka analýzy, vertikálně - stavová čísla (0 - počáteční stav), horizontálně - symboly (terminály, neterminály a symbol „konce proudu“).
Posuny se do tabulky zapisují následovně: pokud je posun možný pro symbol C a stav S, pak se do buňky zapíše hodnota „posun do stavu S-tah“ (získaná jako výsledek posunu) ( S, C).
Dále se nahradí začátek gramatiky S → E a pro nový začátek S se do buňky zadá hodnota „úspěšné dokončení parsování“ (S, konec streamu).
Dále se do tabulky zapisují akce zmenšení (redukce), pouze pro svorky, následovně: pokud je ve stavu S dokončený řetězec, pak hodnota „zmenšení podle pravidla R, pravá strana délky N znaků“ se zadává do všech buněk (S, terminál), dostaneme neterminální C z levé strany pravidla."
Pokus o vložení přetypování do již obsazené buňky tabulky (například v případě dvou kompletních řetězců ve stavu) se nazývá konflikt přetypování nebo konflikt přetypování. V tomto případě není sestavení LR(0) parseru možné, ale může být možné sestavit pomocí o něco složitějšího algoritmu SLR(1) nebo LALR(1), které se liší pouze ve způsobu zadávání přetypování do stůl.
Používá se zásobník analyzátoru, kde jsou umístěna čísla stavů, vstupní (svorky a konec proudu) a výstupní (čísla pravidel) proudy.
0 se vloží do zásobníku jako první.
Dále, dokud není přijata syntaktická chyba nebo úspěšné dokončení analýzy: