GLR analyzátor

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 (anglicky Generalized LR(k)).

Východiskem GLR-analyzátoru je vytvoření LR(k)-tabulky. Pokud gramatika není LR(k) (např. 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. grafový zásobník (anglicky ''graph structured stack), 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:

  1. S → DP VP
  2. VP → Vbar
  3. VP → VP PP
  4. Vbar → Vtrans DP
  5. DP → Det NP
  6. DP → Pron
  7. NP → Nbar
  8. Nbar → N
  9. Nbar → Nbar PP
  10. 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ě. 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. 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). 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.

Vztah k jiným metodám syntaktické analýzy

GLR analyzátor lze považovat za předkompilovaný tabulkový analyzátor.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Tomita-Parser na německé Wikipedii.

Literatura

  • GRUNE, Dick; JACOBS; CERIEL, J.H. Parsing Techniques. [s.l.]: Springer Science+Business Media, 2008. ISBN 978-0-387-20248-8. 
  • TOMITA, Masaru. LR parsers for natural languages. In: Coling 1984: 10th International Conference on Computational Linguistics. [s.l.]: [s.n.], 1984.
  • TOMITA, Masaru. An efficient context-free parsing algorithm for natural languages. In: International Joint Conference on Artificial Intelligence. [s.l.]: [s.n.], 1985.

Média použitá na této stránce