制度规范

百度 旅游投资仍将保持较快增长，新解决旅游就业100万人。

Tabulkovy analyzátor (anglicky chart parser) je v matematické informatice druh syntaktickych analyzátor? vhodnych pro analyzu nejednozna?nych bezkontextovych jazyk? (v?etně gramatik p?irozenych jazyk?). Pou?ívá p?ístupu dynamického programování – v?echny probírané díl?í vysledky se ukládají do tabulky, která reprezentuje orientovany multigraf, díky ?emu? mohou byt pou?ívány opakovaně. Tím se zabrání backtrackingu a kombinatorické explozi. ?esky název odrá?í skute?nost, ?e orientovany multigraf byvá implementován tabulkou (maticí).

Za autora tabulkové analyzy je pova?ován Martin Kay.

Typy tabulkovych analyzátor?

Tabulkové analyzátory obvykle pou?ívají nějakou variantu Viterbiho algoritmu. Earley?v analyzátor je tabulkovy analyzátor, ktery se pou?ívá p?edev?ím pro syntaktickou analyzu v matematické lingvistice, a ktery je pojmenovany po svém objeviteli. Dal?ím algoritmem tabulkové analyzy je algoritmus Cocke–Younger–Kasami (CYK).

Tabulkové analyzátory lze pou?ívat i pro syntaktickou analyzu po?íta?ovych jazyk?. Jmenovitě Earley?v analyzátor se pou?ívá v generátorech p?eklada??, díky své schopnosti analyzovat jazyk generovany libovolnou bezkontextovou gramatikou, co? usnadňuje úlohu vytvo?ení gramatiky pro dany jazyk. Jejich ni??í efektivita v?ak vedla k tomu, ?e se jim lidé p?i konstrukci p?eklada?? obvykle vyhybají.

P?i obousměrné tabulkové analyze jsou hrany multigrafu ozna?ovány směrem (dop?edu nebo zpět), a pravidla jsou vynucena podle směru, kterym musí vést hrany, aby je bylo mo?né zkombinovat do dal?ích hran.

P?i inkrementální tabulkové analyze se orientovany 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 jednotlivymi 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.

Analyza věty spo?ívá v p?idávání orientovanych hran mezi jednotlivé uzly grafu. Ka?dy krok analyzy p?idá novou hranu ohodnocenou nějakou polo?kou gramatiky. Pokud se v pr?běhu analyzy 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 analyze uva?ujeme pouze hrany, které jdou zleva doprava. Mezi libovolnymi dvěma uzly m??e vést vět?í po?et hran, proto se p?i analyze vytvá?í multigraf. Multigraf lze reprezentovat maticí (n+1) x (n+1) (anglicky chart), 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 byt libovolny 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 byt 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 analyze 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 jmennymi frázemi.
• Dal?í NP za?íná na pozici 5, pokud lze p?íslu?né pravidlo pro VP v?bec pou?ít

Operace p?i analyze

Tabulkovy analyzátor pou?ívá p?i analyze t?i typy operací:

1. Predikce (predikce)
2. Na?tení terminálního symbolu (p?esun)
3. 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?eny 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 = w₀w₁ ... w_n,

pak do tabulky p?idáme

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

(pokud u? v tabulce není).

Analyza 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 analyzy. 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 tyká analyzátor? zdola nahoru. Jiné metody tabulkové analyzy 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 analyzy byla nalezena úplná polo?ka pokryvají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 byt obě zkombinovány do nové hrany, která pokryvá pozice i a? k. Zna?ka (te?ka) je proto p?esunuta za symbol B.

Algoritmus analyzy

Vstup: ?etězec s = w₀w₁ ... w_n.

1. <0,0, S' → . S >, (kde S je po?áte?ní symbol gramatiky, S' je p?idany neterminální symbol.
2. Opakovat vy?e uvedené kroky predikce, p?esunu a redukce tak dlouho, dokud lze p?idávat dal?í polo?ky tabulky.

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

Poznámka: Popsany 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í analyza 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 praktickych algoritmech se pro ur?ení po?adí krok? postupně vytvá?í seznam nazyvany anglicky agenda. Zp?sob jeho budování rozhoduje, jaky postup analyzy se pou?ívá.

P?íklad

Máme bezkontextovou gramatiku popisující zjednodu?enou gramatiku něm?iny s následujícími pravidly:

1. S → NP VP
2. S → S PP
3. VP → V NP
4. NP → NP PP
5. NP → Art N
6. PP → P NP

a lexikálními pravidly:

1. NP → Donald
2. NP → Daisy
3. V → beobachtet
4. N → Fernglas
5. P → mit
6. Art → dem

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

?ís.	P?idaná polo?ka tabulky	Zdroj
1	< 0, 0, S' → . S >	Inicializace
2	< 0, 0, S → . NP VP >	P 1, 1
3	< 0, 0, S → . S PP >	P 1, 2
4	< 0, 0, NP → . NP PP >	P 2, 4
5	< 0, 0, NP → . Art N >	P 2, 5
6	< 0, 1, NP → Donald . >	S 2, L1
7	< 0, 1, S → NP . VP >	C 2, 6
8	< 0, 1, NP → NP . PP >	C 4,6
9	< 1, 1, VP → . V NP >	P 7, 3
10	< 1, 1, PP → . P NP >	P 8, 6
11	< 1, 2, V → beobachtet . >	S 9, L3
12	< 1, 2, VP → V . NP >	C, 9, 11
13	< 2, 2, NP → . NP PP >	P 12, 4
14	< 2, 2, NP → . Art N >	P 12, 5
15	< 2, 3, NP → Daisy . >	S 12, L2
16	< 1, 3, VP → V NP . >	C 12, 15
17	< 2, 3, NP → NP . PP >	C 13, 15
18	< 0, 3, S → NP VP . >	C 7, 16
19	< 3, 3, PP → . P NP >	P 17, 6
20	< 3, 4, PP → mit . NP >	S 19, L5
21	< 4, 4, NP → . NP PP >	P 20, 4
22	< 4, 4, NP → . Art N >	P 20, 5
23	< 4, 5, Art → dem . >	S 22, L6
24	< 0, 3, S → S . PP >	C 3, 18
25	< 4, 5, NP → Art . N >	C 22, 23
26	< 5, 6, N → Fernglas . >	S 25, L4
27	< 4, 6, NP → Art N . >	C, 25, 26
28	< 3, 6, PP → mit NP . >	C 20, 27
29	< 2, 6, NP → NP PP . >	C 17, 28
30	< 1, 6, VP → V NP . >	C, 12, 29
31	< 0, 6, S → NP VP . >	C 7, 30
32	< 0, 6, S → S PP . >	C 24, 28
33	< 0, 6, S' → S . >	C 1,31
34	< 0, 6, S' → S . >	C 1,32

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?znymi zp?soby (33 a 34), ukazuje, ?e větu lze analyzovat dvěma zp?soby (tj. věta je vícezna?ná). Dal?í analyza 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?ebnych polo?ek grafu lze zabránit tím, ?e se pro rozhodování kromě trojic v tabulce pou?ije také k dop?edu na?tenych a dosud neanalyzovanych symbol? ze vstupu (tzv. 'náhled – anglicky lookahead). Tato technika je dob?e známá u LR (k) analyzátor?.

Separovaná gramatika

Pro analyzu p?irozenych jazyk? se zpravidla pou?ívají tzv. separované gramatiky, v nich? je gramatika rozdělena na slovník a syntaktická pravidla. Pravá strana bezkontextovych 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. necitlivy v??i gramatickym chybám. To se tyká nap?íklad neznámych slov, kterym jsou v kroku skenování p?i?azeny v?echny pravděpodobné slovní druhy, nebo chybějících ?i nadbyte?nych slov, která jsou rozpoznávána pomocí speciálních chybovych pravidel.

Slo?itost

O(n³) pro v?echny bezkontextové gramatiky, O(n²) pro jednozna?né bezkontextové gramatiky.

Aplikace

Tabulkové analyzátory se vět?inou pou?ívají ve spojení s syntaktické analyzy 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á tabulkovy analyzátor. Syntaxe programovacích jazyk? je zpravidla navr?ena tak, aby jejich analyza byla co nejefektivněj?í, a proto je lze obvykle ú?inněji analyzovat LR(k) nebo LL(k) analyzátory.

Odkazy

Reference

V tomto ?lánku byly pou?ity p?eklady text? z ?lánk? Chart parser na anglické Wikipedii a Chart-Parser na německé Wikipedii.

Související ?lánky

• Syntaktická analyza
• P?irozeny jazyk
• ?e?ení hrubou silou
• Dynamické programování

Externí odkazy

• EARLEY, Jay. An Efficient Context-Free Parsing Algorithm. Communications of the ACM. 1970, ?ís. 13. Dostupné v archivu po?ízeném dne 2025-08-14. ISSN 0001-0782.  Archivováno 11. 8. 2017 na Wayback Machine..
• GAZDAR, Gerald; MELLISH, Chris. Natural Language Processing in Prolog. An Introduction to computational Linguistics [online]. Wokingham u. a.: 1989. ISBN 0-201-18053-7. .
• KADLEC, Vladimír; HORáK, Ale?. Algoritmy syntaktické analyzy (pomocí CFG) [online]. [cit. 2025-08-14]. Dostupné online. 
• ARNOLD, Doug. Chart Parsing [online]. [cit. 2025-08-14]. Dostupné v archivu po?ízeném dne 2025-08-14.