Jednoduchý analyzátor LR - Simple LR parser
 | tento článek ne uvést žádný Zdroje. (Prosinec 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) |
v počítačová věda, a Jednoduché LR nebo Analyzátor SLR je typ Analyzátor LR s malými analyzovat tabulky a relativně jednoduchý algoritmus generátoru syntaktických analyzátorů. Stejně jako u jiných typů analyzátoru LR (1) je analyzátor SLR docela efektivní při hledání jediného správného analýza zdola nahoru v jediném skenování zleva doprava přes vstupní proud, bez dohadů nebo zpětného sledování. Analyzátor je mechanicky generován z formální gramatiky jazyka.
SLR a obecnější metody Analyzátor LALR a Kanonický analyzátor LR mít identické metody a podobné tabulky v době analýzy; liší se pouze v algoritmech matematické gramatické analýzy používaných nástrojem generátoru syntaktických analyzátorů. Generátory SLR a LALR vytvářejí tabulky stejné velikosti a identických stavů analyzátoru. Generátory SLR přijímají méně gramatik než generátory LALR yacc a Bison. Mnoho počítačových jazyků neodpovídá omezením SLR tak, jak jsou. Ohýbání přirozené gramatiky jazyka do Gramatika SLR forma vyžaduje více kompromisů a gramatické hackery. Generátory LALR se tedy staly mnohem více používanými než generátory SLR, přestože jsou poněkud komplikovanějšími nástroji. Metody SLR zůstávají užitečným krokem učení na univerzitních kurzech teorie překladačů.
SLR a LALR byly vyvinuty společností Frank DeRemer jako první praktické využití Donald Knuth teorie analyzátoru LR.[Citace je zapotřebí ] Tabulky vytvořené pro skutečné gramatiky pomocí plných metod LR byly neprakticky velké, větší než většina počítačových pamětí daného desetiletí, se stokrát nebo více syntaktickými stavy než metody SLR a LALR.[Citace je zapotřebí ].
Lookahead sady
Abychom pochopili rozdíly mezi SLR a LALR, je důležité porozumět jejich mnoha podobnostem a tomu, jak oba činí rozhodnutí o snížení posunu. (Viz článek Analyzátor LR nyní pro toto pozadí, v sekci o redukcích sady hledáčků.)
Jediný rozdíl mezi SLR a LALR spočívá v tom, jak jejich generátory počítají vyhledávací sady vstupních symbolů, které by se měly objevit další, kdykoli budou některé dokončeny výrobní pravidlo je nalezen a redukován.
Generátory SLR vypočítají tento pohled pomocí metody snadné aproximace založené přímo na gramatice, přičemž ignorují podrobnosti jednotlivých stavů analyzátoru a přechodů. To ignoruje konkrétní kontext aktuálního stavu analyzátoru. Pokud nějaký neterminální symbol S se používá v gramatice na několika místech, SLR s nimi zachází stejným způsobem, než aby s nimi zacházela jednotlivě. Generátor SLR funguje Sledujte (S), sada všech terminálových symbolů, které mohou okamžitě následovat nějaký výskyt S. V tabulce analýzy každá redukce na S používá následnou (S) jako svou vyhledávací sadu LR (1). Takové sady následků také používají generátory pro analyzátory LL shora dolů. Gramatice, která nemá žádné posuny / zmenšení nebo zmenšení / zmenšení konfliktů při použití následujících sad, se nazývá an Gramatika SLR.
Generátory LALR počítají množiny lookahead přesnější metodou založenou na zkoumání grafu stavů analyzátoru a jejich přechodů. Tato metoda zohledňuje konkrétní kontext aktuálního stavu analyzátoru. Přizpůsobuje zpracování každého gramatického výskytu nějakého neterminálního S. Viz článek Analyzátor LALR pro další podrobnosti tohoto výpočtu. Skupiny lookahead vypočítané generátory LALR jsou podmnožinou (a tedy lepší než) přibližných sad vypočítaných generátory SLR. Pokud má gramatika při použití sad SLR follow sets konflikty tabulek, ale při použití sad LALR follow set je bezkonfliktní, nazývá se to gramatikou LALR.
Příklad
Gramatika, kterou lze analyzovat analyzátorem SLR, ale nikoli analyzátorem LR (0), je následující:
- (0) S → E
- (1) E → 1 E
- (2) E → 1
Konstrukce tabulky akcí a goto, jak se provádí u analyzátorů LR (0), by poskytla následující sady položek a tabulky:
- Sada položek 0
- S → • E
- + E → • 1 E
- + E → • 1
- Sada položek 1
- E → 1 • E
- E → 1 •
- + E → • 1 E
- + E → • 1
- Sada položek 2
- S → E •
- Sada položek 3
- E → 1 E •
Akční a go tabulky:
| akce | jít do | ||
|---|---|---|---|
| Stát | 1 | $ | E |
| 0 | s1 | 2 | |
| 1 | s1 / r2 | r2 | 3 |
| 2 | dle | ||
| 3 | R1 | R1 | |
Jak lze pozorovat, dochází ke konfliktu snižování posunu pro stav 1 a terminál '1'. K tomu dochází, protože při vytváření tabulky akcí pro analyzátor LR (0) se redukční akce vkládají na jednotlivé řádky. Pomocí sady sledování však lze přidat akce omezování s jemnější granularitou. Následující sada pro tuto gramatiku:
| symbol | S | E | 1 |
|---|---|---|---|
| Následující | $ | $ | 1,$ |
Redukci je třeba přidat pouze do konkrétního sloupce akce, pokud je tato akce v sadě followů přidružené k této redukci. Tento algoritmus popisuje, zda musí být do sloupce akce přidána akce redukce:
funkce mustBeAdded (reduceAction, action) {ruleNumber = reduAction.value; ruleSymbol = pravidla [čísloPravidla] .leftHandSide; návrat (akce v followSet (ruleSymbol))}}například, mustBeAdded (r2, "1") je nepravdivé, protože levá strana pravidla 2 je „E“ a 1 není v sadě E pro následování. Naopak, mustBeAdded (r2, "$") je pravda, protože „$“ je v sadě E pro sledování.
Použitím mustBeAdded u každé akce redukce v tabulce akcí je výsledkem tabulka akcí bez konfliktů:
| akce | jít do | ||
|---|---|---|---|
| Stát | 1 | $ | E |
| 0 | s1 | 2 | |
| 1 | s1 | r2 | 3 |
| 2 | dle | ||
| 3 | R1 | ||