GLR analyzátor

Technology

12 hours ago

Author

GLR analyzátor nebo Tomitův analyzátor je metoda syntaktické analýzy pro bezkontextové gramatiky, který je zobecněním LR(k) metod. Zkratka GLR(k) znamená zobecněný LR analyzátor .

Východiskem GLR-analyzátoru je vytvoření LR(k)-tabulky. Pokud gramatika není LR(k) (např. +more protože je nejednoznačná), vede tento postup k nejednoznačnostem, tzv. konfliktům:.

* Konflikt přesun-redukce: je možné načíst další vstupní symbol na zásobník analyzátoru nebo nahradit rozpoznanou pravou stranu přepisovacího pravidla levou stranou pravidla. * Konflikt redukce-redukce: existují dvě nebo více přepisovacích pravidel, kterými může být provedena redukce.

Algoritmus GLR tyto konflikty pseudoparalelně sleduje. K tomu se používá tzv. +more grafový zásobník , což je datová struktura reprezentující orientovaný acyklický graf, která zachycuje všechny dílčí operace syntaktické analýzy.

Zásobník

Výsledkem syntaktické analýzy je - podobně jako u tabulkového analyzátoru - orientovaný acyklický graf.

Analýza německé věty Sie beobachtet den Einbrecher mit dem Fernglas.

Obr. 1 ukazuje graf po dokončení syntaktické analýzy ukázkové věty „Sie beobachtet den Einbrecher mit dem Fernglas“ (Pozoruje zloděje (s) dalekohledem).

Přitom je použita následující nejednoznačná gramatika:

# S → DP VP # VP → Vbar # VP → VP PP # Vbar → V trans DP # DP → Det NP # DP → Pron # NP → Nbar # Nbar → N # Nbar → Nbar PP # PP → P DP

Tato gramatika zachycuje nejednoznačnost dané věty („zloděj má dalekohled“ nebo „pozorovatelka používá dalekohled“), která dovoluje dvě různé analýzy. Kvůli této nejednoznačnosti gramatika není LR(k) gramatikou, protože tabulka analyzátoru obsahuje konflikty.

Každý vrchol má unikátní jméno (začínající písmenem „n“). Červené vrcholy obsahují prvky ze slovníku gramatiky, tedy pravidla s neterminálním symbolem na levé straně a slovy věty (terminálními symboly) na pravé straně. +more Modré vrcholy obsahují čísla stavů LR-tabulky analýzy. Je dobře vidět, jak jsou při začleňování předložky „mit“ v vrcholu n21 zkombinovány dvě, do té doby různé, analýzy. Díky tomu je předložková fráze „mit dem Fernglas“ analyzována pouze jednou.

Algoritmus syntaktické analýzy

Stejně jako u LR(k)-metody se proces syntaktické analýzy skládá z posloupnosti přesunů a redukcí řízených tabulkou. Při přesunu je načteno slovo ze vstupu a uloženo na zásobník. +more Při redukci je pravá strana (γ) přepisovacího pravidla A → γ, která je uložena pozpátku na zásobníku, nahrazena levou stranou pravidla (A). Zatímco u metody LR(k) se redukovaná část ze zásobníku odstraňuje, u GLR(k) analýzy se ponechává na zásobníku. To znamená, že zásobník neustále roste.

Proces je řízen GLR(k) tabulkou. V každém okamžiku se syntaktický analyzátor nachází v určitém vnitřním stavu (jako zásobníkový automat). +more Tento vnitřní stav a další symbol nebo symboly na vstupu je vyhledán v GLR(k) tabulce a výsledkem je jedna z operací shift, reduce, accept, error a nastavení nového vnitřního stavu. Případné nejednoznačnosti (konflikty) jsou trasovány kvaziparalelně. Pozdější operace přesunu však mohou různá vlákna paralelního zpracování znovu spojit; to je důležité pro časovou složitost metody.