Tabulkový analyzátor
Tabulkový analyzátor () je v matematické informatice druh syntaktických analyzátorů vhodných pro analýzu nejednoznačných bezkontextových jazyků (včetně gramatik přirozených jazyků). Používá přístupu dynamického programování – všechny probírané dílčí výsledky se ukládají do tabulky, která reprezentuje orientovaný multigraf, díky čemuž mohou být používány opakovaně. Tím se zabrání backtrackingu a kombinatorické explozi. Český název odráží skutečnost, že orientovaný multigraf bývá implementován tabulkou (maticí).

Za autora tabulkové analýzy je považován Martin Kay.

Typy tabulkových analyzátorů 
Tabulkové analyzátory obvykle používají nějakou variantu Viterbiho algoritmu. Earleyův analyzátor je tabulkový analyzátor, který se používá především pro syntaktickou analýzu v matematické lingvistice, a který je pojmenovaný po svém objeviteli. Dalším algoritmem tabulkové analýzy je algoritmus Cocke-Younger-Kasami (CYK).

Tabulkové analyzátory lze používat i pro syntaktickou analýzu počítačových jazyků. Jmenovitě Earleyův analyzátor se používá v generátorech překladačů, díky své schopnosti analyzovat jazyk generovaný libovolnou bezkontextovou gramatikou, což usnadňuje úlohu vytvoření gramatiky pro daný jazyk. Jejich nižší efektivita však vedla k tomu, že se jim lidé při konstrukci překladačů obvykle vyhýbají.

Při obousměrné tabulkové analýze jsou hrany multigrafu označovány směrem (dopředu nebo zpět), a pravidla jsou vynucena podle směru, kterým musí vést hrany, aby je bylo možné zkombinovat do dalších hran.

Při inkrementální tabulkové analýze se orientovaný multigraf konstruuje inkrementálně, jak uživatel upravuje text; při každé změně textu se provede minimální možná odpovídající změna v tabulce.

Tabulkové analyzátory lze rozdělit na analyzátory shora dolů, zdola nahoru a
analyzátory řízené hlavou pravidla,
a na aktivní a pasivní.

Tabulka 

Analyzátor zpracovává větu obsahující n slov jako graf s n+1 uzly – první uzel je před prvním slovem, dalších n-1 uzlů je mezi jednotlivými slovy a poslední uzel je za posledním slovem věty. Každé slovo je reprezentováno orientovanou hranou z uzlu před tímto slovem do následujícího uzlu. Celá vstupní věta tak tvoří nerozvětvenou cestu z pozice před prvním slovem na pozici za posledním slovem.

Analýza věty spočívá v přidávání orientovaných hran mezi jednotlivé uzly grafu. Každý krok analýzy přidá novou hranu ohodnocenou nějakou položkou gramatiky. Pokud se v průběhu analýzy přidá hrana, která jde z nultého do posledního uzlu a je ohodnocena úplnou položkou vytvořenou z pravidla, na jehož levé straně je počáteční symbol gramatiky, znamená to přijetí věty.

Při analýze uvažujeme pouze hrany, které jdou zleva doprava. Mezi libovolnými dvěma uzly může vést větší počet hran, proto se při analýze vytváří multigraf. Multigraf lze reprezentovat maticí (n+1) x (n+1) (), kde n je délka vstupní věty. Mezery mezi slovy ve vstupní větě jsou číslovány od 0 do n. V každém prvku matice může být libovolný počet položek, z nichž každá reprezentuje jednu hranu multigrafu, což jsou pravidla s tečkou na pravé straně. (Viz LR analyzátor).

Formálně lze hranu multigrafu popsat jako množinu trojic <i, j, A → α . β>, kde:

 A → α . β je položka gramatiky (pravidlo, v jehož pravé straně je vyznačena aktuální pozice tečkou); zatímco symboly, které odpovídají řetězci α, již byly načteny, symboly odpovídající β dosud ne. α a β je libovolná posloupnost terminálních a neterminálních symboly dané gramatiky. Řetězce α i β mohou být i prázdné.
 i (0 ≤ i ≤ n) je pozice ve vstupním řetězci, na které začíná pokrytí vstupního řetězce uvedenou položkou.
 j (j ≥ i) je pozice, po kterou byly načteny vstupní terminální symboly, které odpovídají řetězci α.

Příklad 
Hrana multigrafu použitého při analýze může vypadat například takto:

< 2, 5, VP → V NP . NP >

Což znamená:
 Od vstupní pozice 2 může začínat slovesná fráze (VP).
 Dosud byl vstup načten až po pozici 5, což na pravé straně pravidla VP → V NP NP odpovídá pozici mezi oběma jmennými frázemi.
 Další NP začíná na pozici 5, pokud lze příslušné pravidlo pro VP vůbec použít

Operace při analýze 
Tabulkový analyzátor používá při analýze tři typy operací:

 Predikce (predikce)
 Načtení terminálního symbolu (přesun)
 Kombinace dvou dílčích konstituentů (redukce)

Predikce 
Pokud tabulka obsahuje < i, j, A → α . B β > a B → γ je pravidlo gramatiky,

pak do tabulky přidáme

< j, j, B → . γ >

(pokud už v tabulce není).

Od počáteční pozice j se očekává složka kategorie B (tj. řetězec terminálů vytvořený z neterminálního symbolu B). Pro expanzi symbolu B existuje pravidlo s pravou stranou γ. Přidáme tedy novou predikci γ začínající od pozice j.

Načtení terminálního symbolu 
Pokud tabulka obsahuje < i, j, A → α . w β > (kde w je terminální symbol příp. preterminální symbol) a pokud w je j-té slovo analyzované věty s = w0w1 ... wn,

pak do tabulky přidáme

< i, j+1, A → α w . β >

(pokud už v tabulce není).

Analýza je tedy v situaci, kdy se na pozici j očekává terminální symbol (příp. preterminální symbol vyjadřující slovní druh nebo jinou mluvnickou kategorii např. finitní sloveso). Je-li j-té slovo skutečně rovné w (nebo je jeho mluvnická kategorie w), pak jej lze začlenit do analýzy. To se znázorní posunutím tečky za načtené slovo.

Kombinace dvou dílčích konstituentů 
Poznámka: zde popsaná operace kombinace se týká analyzátorů zdola nahoru. Jiné metody tabulkové analýzy mohou pracovat poněkud odlišně.

Pokud tabulka obsahuje položku < i, j, A → α . B β > (B je neterminální symbol) a položku < j, k, B → γ . >

potom do tabulky přidáme

< i, k, A → α B . β >

(pokud v ní už není).

Během analýzy byla nalezena úplná položka pokrývající pozice j a k odpovídající neterminálnímu symbolu B. Pokud v multigrafu existuje hrana, která odráží očekávání, že hrana B může začínat na pozici j, mohou být obě zkombinovány do nové hrany, která pokrývá pozice i až k. Značka (tečka) je proto přesunuta za symbol B.

Algoritmus analýzy 
Vstup: řetězec s = w0w1 ... wn.

 <0,0, S' → . S >, (kde S je počáteční symbol gramatiky, S' je přidaný neterminální symbol.
 Opakovat výše uvedené kroky predikce, přesunu a redukce tak dlouho, dokud lze přidávat další položky tabulky.

Výstup: ano, pokud tabulka obsahuje <0, n, S' → S . >, jinak ne.

Poznámka: Popsaný algoritmus pouze zjišťuje, zda lze danou větu odvodit v dané gramatice. Pro získání rozboru věty (jednoho nebo více derivačních stromů tzv. sbaleného lesa derivačních stromů) je třeba využít další informace z grafu.

V bodě 2 není uvedeno, v jakém pořadí se mají provádět jednotlivé kroky. Vlastní analýza může používat různé metody vyhledávání (prohledávání do hloubky, prohledávání do šířky, uspořádané prohledávání). V praktických algoritmech se pro určení pořadí kroků postupně vytváří seznam nazývaný . Způsob jeho budování rozhoduje, jaký postup analýzy se používá.

Příklad 
Máme bezkontextovou gramatiku popisující zjednodušenou gramatiku němčiny s následujícími pravidly:

 S → NP VP
 S → S PP
 VP → V NP
 NP → NP PP
 NP → Art N
 PP → P NP

a lexikálními pravidly:
 NP → Donald
 NP → Daisy
 V → beobachtet
 N → Fernglas
 P → mit
 Art → dem

Má být analyzována německá věta "Donald beobachtet Daisy mit dem Fernglas" (Donald pozoroval Daisy dalekohledem).

Vysvětlivky:

 Pn,m=Predikce (predict) vstupu n přepisovacím pravidlem m,
 Sn,Lm=Přesun (načtení) predikce vstupu n lexikálním pravidlem m,
 Cn,m=Redukce (kombinace) položek n a m

Skutečnost, že koncovou položku lze vytvořit různými způsoby (33 a 34), ukazuje, že větu lze analyzovat dvěma způsoby (tj. věta je víceznačná). Další analýza odpovídá českému překladu „Donald pozoroval Daisy s dalekohledem“ (tj. dalekohled měla v tomto případě Daisy).

Rozšíření

Vypouštějící pravidla 
Vypouštějící pravidla jsou pravidla tvaru A → ε. Tato pravidla jsou obvykle integrována zvláštní strategií zpracování do grafu analyzátoru.

Náhled 
Generování nepotřebných položek grafu lze zabránit tím, že se pro rozhodování kromě trojic v tabulce použije také k dopředu načtených a dosud neanalyzovaných symbolů ze vstupu (tzv. 'náhled – ). Tato technika je dobře známá u LR (k) analyzátorů.

Separovaná gramatika 
Pro analýzu přirozených jazyků se zpravidla používají tzv. separované gramatiky, v nichž je gramatika rozdělena na slovník a syntaktická pravidla. Pravá strana bezkontextových pravidel gramatiky tedy obsahuje buď pouze terminální symboly (slova analyzovaného jazyka) nebo neterminální symboly. To umožňuje zefektivnit proces predikce a načítání, protože postupují pouze na úroveň preterminálních symbolů (slovních druhů nebo jemnějších kategorií).

Robustnost 
Protože ne vždy je vstupem analyzátoru věta vytvořená podle pravidel gramatiky, je užitečné, aby analyzátor byl robustní, tj. necitlivý vůči gramatickým chybám. To se týká například neznámých slov, kterým jsou v kroku skenování přiřazeny všechny pravděpodobné slovní druhy, nebo chybějících či nadbytečných slov, která jsou rozpoznávána pomocí speciálních chybových pravidel.

Složitost 
O(n3) pro všechny bezkontextové gramatiky, O(n2) pro jednoznačné bezkontextové gramatiky.

Aplikace 
Tabulkové analyzátory se většinou používají ve spojení s syntaktické analýzy přirozeného jazyka, protože až na Tomitův analyzátor mají nejlepší časovou složitost pro jakékoli (tedy i víceznačné) bezkontextové gramatiky. Například kontrola gramatiky v aplikaci Microsoft Word používá tabulkový analyzátor. Syntaxe programovacích jazyků je zpravidla navržena tak, aby jejich analýza byla co nejefektivnější, a proto je lze obvykle účinněji analyzovat LR(k) nebo LL(k) analyzátory.

Odkazy

Reference

Související články 
 Syntaktická analýza
 Přirozený jazyk
 Řešení hrubou silou
 Dynamické programování

Externí odkazy 
  .
 .
 
 

Syntaktická analýza přirozeného jazyka
Algoritmy syntaktické analýzy