LR syntaktický analyzátor () je v matematické informatice typ syntaktického analyzátoru zdola nahoru, který efektivně zpracovává deterministické bezkontextové jazyky v zaručeném lineárním čase. Jeho často používanými variantami jsou LALR analyzátor a SLR analyzátor. Pro vytváření LR syntaktických analyzátorů se často používají generátory syntaktických analyzátorů, které generují analyzátor mechanicky z formální gramatiky jazyka. Častěji než jiné druhy generovaných syntaktických analyzátorů se používají pro zpracování programovacích jazyků.
Zkratku LR, případně LR(k) lze rozložit na jednotlivé složky: L znamená, že syntaktický analyzátor čte vstupní text v jednom směru bez návratu (tak funguje většina syntaktických analyzátorů) typicky zleva doprava. R znamená, že syntaktický analyzátor provádí syntaktickou analýzu zdola nahoru a produkuje obrácený pravý rozbor, čímž se liší od velké skupiny analyzátorů provádějících syntaktickou analýzu shora dolů nebo ad-hoc. Zkratka LR je často následována číselným kvalifikátorem, např. LR(1) nebo LR(k). Aby se zamezilo backtrackingu nebo hádání, analyzátor se rozhoduje, jak analyzovat předchozí symboly, na základě náhledu na k dosud nezpracovaných vstupních symbolů. Nejčastěji bývá k rovno 1, a pak se neuvádí. Zkratku LR často předchází jiné kvalifikátory, jako SLR a LALR.
LR syntaktické analyzátory jsou deterministické; produkují jedinou správnou syntaktickou analýzu bez hádání nebo návratu () a pracují v lineárním čase. Díky tomu jsou ideální pro programovací jazyky. Lidské jazyky jsou naproti tomu nejednoznačné a vyžadují flexibilnější metody, které však jsou pomalejší. Příkladem je CYK algoritmus, Earleyův analyzátor a GLR syntaktický analyzátor), které provádějí návraty nebo dávají více analýz, a mohou mít časovou složitost O(n2), O(n3) nebo dokonce exponenciální, pokud provádějí špatné odhady.
Výše uvedené vlastnosti L, R a k ve skutečnosti mají všechny syntaktické analyzátory založené na přístupu přesun-redukce, včetně jednoduchého precedenčního syntaktického analyzátoru. Označení LR se však používá pouze pro třídu analyzátorů, které poprvé popsal Donald Knuth, nikoli na dřívější, méně výkonné precedenční metody (například operátorový precedenční syntaktický analyzátor). LR syntaktický analyzátor může zpracovávat větší obor jazyků a gramatik než precedenční syntaktický analyzátor nebo analyzátor shora dolůJazykově teoretické porovnání LL a LR gramatik. Je to způsobeno tím, že syntaktický analyzátor LR má pro rozhodování, jaké pravidlo použít, k dispozici celou instanci nějakého vzorku gramatiky. LL syntaktický analyzátor se naproti tomu musí rozhodnout a odhadnout, jaké pravidlo použít, mnohem dříve, v okamžiku, kdy viděl pouze první symbol zleva v tomto vzorku. LR je také lepší v oznamování chyb. Syntaktické chyby ve vstupním proudu detekuje hned, jak je to možné.
Úvod LR analyzátor načítá a analyzuje vstupní text v jednom průchodu textem zleva doprava. Derivační strom analyzátor vytváří inkrementálně, zdola nahoru a zleva doprava, bez hádání nebo backtrackingu. V každém bodě tohoto průchodu analyzátor vytváří seznam podstromů nebo frází vstupního textu, které již byly analyzovány. Tyto podstromy zatím nejsou spojeny, protože analyzátor ještě nedosáhl pravého konce syntaktického vzoru, který použije pro jejich složení.
Gramatika pro A*2 + 1 LR analyzátory se konstruují z gramatik, které formálně definují syntaxi vstupního jazyka jako množinu vzorků. Gramatika v praxi nepokrývá všechna pravidla jazyka, nezabývá se například formátováním textu programu pomocí mezer a konců řádků, velikostí čísel nebo konzistencí používání jmen a jejich definic v kontextu celého programu. LR analyzátory používají bezkontextové gramatiky, které pracují pouze s lokálními vzorky symbolů.
Použijeme malý výsek gramatiky popisující aritmetický výraz v programovacím jazyce Java nebo C:
r0: Goal → Sums eof r1: Sums → Sums + Products r2: Sums → Products r3: Products → Products * Value r4: Products → Value r5: Value → int r6: Value → id
Terminální symboly gramatiky jsou víceznakové symboly neboli 'tokens', které ze vstupního proudu načetl lexikální analyzátor. V našem případě se jedná o symboly + * a int pro libovolnou celočíselnou konstantu, id pro libovolné jméno identifikátoru a eof pro konec vstupního souboru. Gramatika se nestará o to, jakou konkrétní hodnotu mají symboly int nebo id, ani o mezery a znaky konce řádku. Gramatika tyto terminální symboly používá, ale nedefinuje je. Jedná se vždy o koncové uzly (ve spodní části) derivačního stromu.
Slova začínající velkým písmenem jako Sums jsou neterminální symboly. Jsou to jména pro koncepty, syntaktické kategorie nebo vzorky v jazyce, které se samy ve vstupním proudu nikdy neobjeví. Jsou pouze použity v gramatice pro popis struktury jazyka. V derivačním stromě jsou to vždy interní uzly (nad spodní částí). Při analýze se objeví jako výsledek použití některého z pravidel gramatiky. Některé terminály jsou na levé straně dvou nebo více pravidel; pak se jedná o alternativní pravidla. Pravidla, ve kterých se vyskytuje stejný neterminál na levé i pravé straně, se nazývají rekurzivní. V této gramatice se rekurzivní pravidla používají pro definici opakovaných matematických operátorů. Gramatiky pro úplné jazyky používají rekurzivní pravidla pro zpracovávání seznamů, uzávorkovaných výrazů a vnořených příkazů.
Derivační strom analýzy zdola nahoru řetězce A*2 + 1 V kroku 6 v příkladu analýzy, bylo analyzováno pouze „A*2“, neúplně. Z derivačního stromu máme pouze tmavěji podbarvený spodní levý roh. Uzly od čísla 7 zatím neexistují. Uzly 3, 4 a 6 jsou kořeny izolovaných podstromů, po řadě pro proměnnou, operátor * a číslo 2. Tyto tři výchozí uzly jsou dočasně uchovávány na zásobníku analyzátoru. Zbývající nenačtená část vstupního proudu je „+ 1“.
Akce přesun a redukce LR analyzátor se řadí k analyzátorům typu přesun-redukce, které provádějí dva druhy akcí: Přesun () je načtení symbolu ze vstupního proudu. Načtený symbol se stane novým derivačním stromem s jedním uzlem. Redukce () aplikuje pravidlo gramatiky na několik posledních derivačních stromů, které spojí do jednoho stromu s nový počátečním symbolem. Pokud vstup neobsahuje syntaktické chyby, analyzátor opakuje tyto kroky, dokud nenačte celý vstup a dokud všechny dílčí derivační stromy nejsou zkombinovány do jediného stromu, který reprezentuje analýzu celého vstupního řetězce.
LR analyzátory se liší od jiných analyzátorů pracujících metodou přesun-redukce tím, jak se rozhodují, kdy provést redukci a jak vybírat z pravidel s podobnými konci. Ale výsledné rozhodnutí a posloupnost přesunů a redukcí je stejná.
Efektivita LR analyzátorů pramení především z jejich determinismu. Aby LR analyzátor nemusel hádat, co dělat s dříve načtenými symboly, obvykle načítá další nezpracované symboly (výhled, ). Lexikální analyzátor funguje s výhledem na jeden nebo více symbolů analyzátoru. Symboly ve výhledu jsou 'pravým kontextem' pro rozhodování o dalším postupu analýzy.Keith Cooper a Linda Torczon: Engineering Compiler (2. vydání), Morgan Kaufman 2011.
Zásobník analyzátoru zdola nahoru Stejně jako jiné analyzátory pracující metodou přesun-redukce LR analyzátory před rozhodnutím, o jakou konstrukci se jedná, čekají, dokud nejsou načteny a analyzovány všechny složky této konstrukce. Analyzátor pak hned zpracovává výslednou kombinaci. V derivačním stromu v ukázce, se v krocích 1-3 fráze A zredukuje na Value a pak na Products, jakmile se ve výhledu objeví *, a již se nečeká na pozdější kombinování těchto složek do derivačního stromu. Rozhodnutí, jak zpracovávat A závisí pouze na tom, co bylo dosud nečteno na vstupu analyzátoru, bez uvažováním symbolů, které se vyskytují dále vpravo.
Redukce reorganizuje jeden nebo více naposledy analyzovaných objektů, které jsou bezprostředně před symbolem ve výhledu. Seznam již analyzovaných objektů tedy funguje jako zásobník. Pokud obsah zásobníku analyzátoru () zapíšeme jako řetězec, roste doprava. Dno zásobníku je tedy úplně vlevo a obsahuje nejlevější, tj. nejstarší fragment analýzy. Každá redukce pracuje pouze se symboly na pravém konci, kde jsou nejnovější fragmenty analýzy. (Tím se akumulativní zásobník LR analyzátoru výrazně liší od prediktivního, doleva rostoucího zásobníku analyzátorů provádějících analýzu shora dolů.)
Analýza zdola nahoru řetězce A*2 + 1 Krok Zásobník analyzátoru Nenačteno Akce 0 prázdný A*2 + 1 přesun 1 id *2 + 1 Value → id 2 Value *2 + 1 Products → Value 3 Products *2 + 1 přesun 4 Products * 2 + 1 přesun 5 Products * int + 1 Value → int 6 Products * Value + 1 Products → Products * Value 7 Products + 1 Sums → Products 8 Sums + 1 přesun 9 Sums + 1 přesun 10 Sums + int eof Value → int 11 Sums + Value eof Products → Value 12 Sums + Products eof Sums → Sums + Products 13 Sums eof přijato
V kroku 6 se provádí redukce podle pravidla s více symboly na pravé straně: Products → Products * Value které porovná vrchol zásobníku obsahující analyzovanou frázi „... Products * Value“. Redukce nahradí tuto instanci pravé strany pravidla, „Products * Value“ levou stranou, v tomto případě symbolem Products. Pokud by analyzátor vytvářel úplné derivační stromy, tři stromy pro vnitřní Products, * a Value by byly zkombinovány do nového stromu s kořenem Products. Sémantické detaily z vnitřních uzlů Products a Value jsou výstupem pro pozdější průchody překladače nebo jsou zkombinovány a uloženy do nového symbolu Products.Crafting a Compiler, by Charles Fischer, Ron Cytron a Richard LeBlanc, Addison Wesley 2009.
LR kroky analýzy řetězce A*2 + 1 U slabých LR analyzátorů jsou rozhodnutí o přesunu nebo redukci založena na obsahu celého zásobníku, nejen na symbolu na vrcholu zásobníku. Nevhodná implementace by mohla vést k velmi pomalým analyzátorům, jejichž rychlost by dále klesala pro delší vstupy. Aby mohly LR analyzátory provádět rozhodnutí s konstantní rychlostí, musí sumarizovat všechny relevantní informace z levého kontextu do jediné hodnoty nazývané LR(0) stav analyzátoru (). Pro každou gramatiku a metodu LR analýzy existuje pevný (konečný) počet takových stavů. Zásobník analyzátoru uchovává kromě již analyzovaných symbolů také čísla doposud dosažených stavů.
Vstupní text je v každém okamžiku analýzy rozdělen na již analyzované fráze na zásobníku, aktuální symbol ve výhledu a zbývající, dosud nenačtený, text. Další akce analyzátoru je určena aktuálním LR(0) (na zásobníku úplně vpravo) a symbolem ve výhledu. V následujícím textu jsou všechny informace psané černě stejné jako u jiných analyzátorů nepracujících metodou LR přesun-redukce. LR analyzátor ukládá na zásobník stavové informace zapsané fialově, přičemž sumarizuje černé fráze vlevo na zásobníku, a jaké syntaktické možnosti mají být očekávány dále. Uživatelé LR analyzátoru stavové informace obvykle ignorují. Tyto stavy jsou vysvětleny v další části.
Krok Zásobník analyzátoru [Symbol]* Výhled Nenačtenývstup Akceanalyzátoru Pravidlo gramatiky Aktuálnístav 0 id A*2 + 1 přesun 1
id * 2 + 1 redukce Value → id 2
Value * 2 + 1 redukce Products → Value 3
Products * 2 + 1 přesun 4
Products * int + 1 přesun 5
Products * int + 1 redukce Value → int 6
Products * Value + 1 redukce Products → Products * Value 7
Products + 1 redukce Sums → Products 8
Sums + 1 přesun 9 Sums + int eof přesun 10 Sums + int eof redukce Value → int 11
Sums + Value eof redukce Products → Value 12
Sums + Products eof redukce Sums → Sums + Products 13
Sums eof přijetí
V počátečním kroku 0 je vstupní řetězec „A*2 + 1“ rozdělen na prázdnou část na zásobníku analyzátoru, text výhledu „A“ načtený (lexikálním analyzátorem) jako symbol id a zbývající dosud nenačtený text „*2 + 1“. Na začátku analýzy obsahuje zásobník analyzátoru pouze počáteční stav 0. Pokud analyzátor ve stavu 0 vidí výhled id, musí provést přesun, který uloží symbol id na zásobník, načte další vstupní symbol * a přejde do stavu 9.