GLR analyzátor (z angl. Generalized Left-to-right Rightmost derivation parser - Generalized ascending store parser ) - v informatice rozšířený algoritmus LR analyzátoru určený k analýze nedeterministických a nejednoznačných gramatik . Poprvé popsaný Masaru Tomitou v roce 1984 , je také nazýván "paralelním analyzátorem" .
Protože je tento algoritmus odvozen od LR parseru, principy jeho fungování zůstaly stejné: Tomita si dal za cíl dosáhnout rychlého a efektivního rozpoznávání textů psaných v přirozeném jazyce . Normální LR analyzátor není schopen vyřešit neurčitost a nejednoznačnost přirozených jazyků, zatímco algoritmus GLR ano.
Algoritmus GLR funguje přesně jako algoritmus LR , kromě toho, že pro danou gramatiku zpracovává analyzátor GLR všechny možné interpretace vstupní sekvence pomocí vyhledávání do šířky . Generátory analyzátoru GLR převádějí původní gramatiku do tabulek analyzátoru, stejně jako generátory analyzátorů LR. Ale zatímco tabulky analyzátoru LR umožňují pouze jeden přechod stavu (definovaný počátečním stavem analyzátoru a symbolem vstupního terminálu), tabulky analyzátoru GLR umožňují mnoho výsledných stavů. Výsledkem je, že algoritmus GLR umožňuje posun/snížení a snížení/snížení konfliktů.
Když dojde ke konfliktu, zásobník analyzátoru (sbalení úložiště) se rozdělí na dva nebo více paralelních zásobníků, jejichž nejvyšší stavy odpovídají každému možnému přechodu. V následujícím je následující vstupní symbol použit k určení dalších přechodů na nejvyšších stavech každé větve zásobníku. V tomto případě může být opět nutné větvit stoh. Pokud pro jakýkoli nejvyšší stav a vstupní symbol neexistuje žádný přechod (v tabulce analyzátoru), pak je tato větev zásobníku považována za chybnou a zahozena.
Základem optimalizace je možnost sdílet části zásobníku s několika jeho větvemi, což snižuje celkové množství paměti potřebné k analýze vstupní sekvence. Složitá struktura vyplývající z této optimalizace způsobuje, že zásobník vypadá spíše jako orientovaný acyklický graf než jako strom.
Algoritmus GLR má v nejhorším případě stejnou složitost jako Kok-Younger-Kasami algoritmus a Earleyho algoritmus - O ( n³ ). Algoritmus GLR má však dvě výhody:
V praxi je většina programovacích jazyků deterministická nebo „téměř deterministická“. To znamená, že nedeterminismus lze obvykle vyřešit čtením malého (i když neomezeného) počtu vstupních znaků. Ve srovnání s jinými algoritmy schopnými zpracovat celou třídu bezkontextových gramatik (jako je Early algoritmus nebo Kok-Younger-Kasami algoritmus) je algoritmus GLR výkonnější na takových „téměř deterministických“ gramatikách, protože pouze jedna větev zásobník.