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. +more 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. +more 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. +more 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. +more 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. +more 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 , 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. +more α 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:

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. +more * 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 a B → γ je pravidlo gramatiky,

pak do tabulky přidáme

(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). +more 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 (kde w je terminální symbol příp. preterminální symbol) a pokud w je j-té slovo analyzované věty s = w0w1 . +more wn,.

pak do tabulky přidáme

(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ř. +more 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 (B je neterminální symbol) a položku

potom do tabulky přidáme

(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. +more Značka (tečka) je proto přesunuta za symbol B.

Algoritmus analýzy

Vstup: řetězec s = w0w1 ... wn.

# , (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 , 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. +more 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í). +more 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á). +more 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 - ). +more 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. +more 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. +more 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. +more 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

. * . * *

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