Gramatika SLR - SLR grammar

v obecná věda, Gramatiky SLR jsou třídou formální gramatiky přijato a Jednoduchý analyzátor LR. Gramatiky SLR jsou nadmnožinou všech gramatik LR (0) a podmnožinou všech gramatik LALR (1) a LR (1).

Při zpracování analyzátorem SLR se gramatika SLR převede na analyzované tabulky bez jakýchkoli kombinací stavu syntaktického analyzátoru LR (0) a očekávaného symbolu lookahead na analyzované tabulky bez konfliktů posun / zmenšení nebo zmenšení / zmenšení. Pokud gramatika není SLR, budou mít analyzované tabulky konflikty posunu / zmenšení nebo zmenšení / zmenšení konfliktů pro některé stavy a některé symboly vyhledávání a výsledný odmítnutý analyzátor již není deterministický. Analyzátor se nemůže rozhodnout, zda se má posunout nebo snížit další, nebo se nemůže rozhodnout mezi dvěma redukcemi kandidáta. Analyzátory SLR používají výpočet Follow (A) k výběru symbolů dopředného pohledu, které lze očekávat u každého dokončeného neterminálu.

Analyzátory LALR použijte jiný výpočet, který někdy dává menší a přísnější sady hledáčků pro stejné stavy analyzátoru. Tyto menší sady mohou eliminovat překrývání s akcemi posunu státu a překrývání s hledáním dalších redukcí ve stejném stavu. Konflikty překrytí hlášené analyzátory SLR jsou pak falešné, což je výsledek přibližného výpočtu pomocí funkce Follow (A).

Gramatika, která je dvojznačný bude mít nevyhnutelný posun / zmenšení konfliktů nebo zmenšení / zmenšení konfliktů pro každou metodu analýzy LR, včetně SLR. Běžným způsobem, jak mohou být gramatiky počítačových jazyků nejednoznačné, je situace, kdy je některý neterminál rekurzivní vlevo i vpravo:

Expr → Expr * Val
Expr → Val + Expr
Expr → Val

Definice

Pravidlo formy B → y • ve stavu automatu SLR (1) se říká, že je neredukovatelný nebo v a snížený stav protože byl zcela rozšířen a není schopen podstoupit jakýkoli posunový přechod. Pravidla v tomto stavu budou mít tečku (•, aktuální pozice dopředu) umístěnou na nejpravějším konci jejího RHS (pravá strana).

Pravidla

O gramatice se říká, že je SLR (1) právě tehdy, pro každý stát s v automatu SLR (1) není porušena žádná z následujících podmínek:

  1. Pro jakékoli redukovatelné pravidlo A → a • Xb ve stavu s (kde X je nějaký terminál), nesmí existovat nějaké neredukovatelné pravidlo, B → a • ve stejném stavu s takové, že následovat sada B obsahuje terminál X. Formálněji řečeno, průnik množiny obsahující terminál X a následující sada B musí být prázdné. Porušení tohoto pravidla je a Shift-snížit konflikt.
  2. U dvou kompletních položek A → a • a B → b • v s, Sledujte (A) a Sledujte (B) jsou disjunktní (jejich průsečík je prázdná množina). Porušení tohoto pravidla je a Redukce-redukce konfliktu.

Algoritmus analýzy

O gramatice se říká, že je SLR (1), pokud jde o následující jednoduchý LR parser Výsledkem algoritmu není žádná nejednoznačnost.

  1. Pokud stát s obsahuje jakoukoli položku formuláře A → a • Xb, kde X je terminál a X je další token ve vstupním řetězci, pak je akce přesunout aktuální vstupní token do zásobníku a nový stav, který má být na zásobníku posunut, je stav obsahující položku A → aX • b.
  2. Pokud stát s obsahuje kompletní položku A → y • a další token ve vstupním řetězci je v Sledujte (A), pak je akce snížit podle pravidla A → y. Snížení pravidlem S '→ S, kde S je počáteční stav, odpovídá přijetí; k tomu dojde, pouze pokud je další vstupní token $. Ve všech ostatních případech se nový stav vypočítá následujícím způsobem. Odstraňte řetězec y a všechny jeho odpovídající stavy ze syntaktického zásobníku. Odpovídajícím způsobem zálohujte v DFA do stavu, ze kterého byla stavba y začalo. Konstrukčně musí tento stav obsahovat položku formuláře B → a • Ab. Tlačit A do zásobníku a posuňte stav obsahující položku B → aA • b.
  3. Pokud je další vstupní token takový, že neplatí ani jeden z výše uvedených dvou případů, je deklarována chyba.

Viz také

Reference

  • "Konstrukce kompilátoru: Zásady a praxe" od Kennetha C. Loudena.