Zrcadlovka(1)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 1. prosince 2014; ověření vyžaduje 1 úpravu .

SLR(1) je algoritmus analýzy zdola nahoru.

Jedná se o rozšíření algoritmu LR(0) . V některých případech to funguje, když sestavení LR(0) parse tabulky pro danou gramatiku není možné kvůli konfliktům shift-cast nebo cast-cast. Třída gramatik analyzovaných podle SLR(1) (cr. "SLR(1)-grammars") je tedy širší než třída LR(0)-gramatik.

Samotný algoritmus analýzy (provádějící analyzátor podle vstupního toku) je stejný pro SLR(1) i LR(0) — a v širším měřítku pro LALR(1) . Liší se pouze algoritmy pro konstrukci tabulky analýzy podle gramatiky v procesu generování analyzátoru.

Popis

Pro každý neterminál A v gramatice je vygenerována sada terminálů First(A), definovaná takto:

pokud má gramatika pravidlo s A na levé straně a pravou stranou začínající terminálem, pak je tento terminál v First(A)
pokud má gramatika pravidlo s A na levé straně a pravou stranou začínající neterminálem (označeno B), pak First(B) je přísně zahrnuto do First(A)
v First(A) nejsou zahrnuty žádné další terminály

Stejné sady jsou použity pro konstrukci analyzátoru LL(1).

Dále, na základě sad First(A), jsou generovány sady Follow(A), definované následovně

má-li gramatika pravidlo, kde se A nevyskytuje na poslední pozici a za ním následuje koncovka, pak je koncovka zahrnuta v Follow(A).
pokud má gramatika pravidlo, kde A není na poslední pozici, a za ním následuje neterminál (označený B), pak First(B) je přísně zahrnuto v Follow(A)
pokud má gramatika pravidlo, kde se A vyskytuje na poslední pozici, pak je Follow(C) striktně zahrnuto v Follow(A), kde C je levá strana pravidla.
v Follow(A) nejsou zahrnuty žádné další terminály

(je možné tyto podmínky zobecnit pro případ přítomnosti pravidel B -> null)

Dále se vygeneruje tabulka analýzy, jako u LR(0), s rozdílem, kdy jsou zadány akce přetypování. Přetypování pro stav S a vstupní symbol C je tabelováno pouze v případě, že v S je řetězec, který odpovídá celé pravé straně pravidla, a neterminál N z levé strany pravidla splňuje podmínku „C je v Follow( N)".

To má za následek méně pokusů pro SLR(1) vložit "přetypování" do buňky tabulky analýzy, což snižuje riziko konfliktů s přetypováním, někdy se jich úplně zbaví a vytvoří gramatiku, která není analyzována pomocí LR(0 ) parsovatelné.

Praktická aplikace

Téměř nemá (kromě vzdělávacích) kvůli úzké třídě gramatik, které se analyzují. Praktickou aplikací je LALR(1), což je zobecnění SLR(1).

Aritmetické výrazy s unárními a binárními operátory a závorkami jsou analyzovány pomocí SLR(1)

Viz také