Syntaktická analýza

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Příklad syntaktické analýzy matematického výrazu.

Syntaktická analýza (slangově podle angličtiny též parsování nebo parsing) se v informatice a v lingvistice nazývá proces analýzy posloupnosti formálních prvků s cílem určit jejich gramatickou strukturu vůči předem dané (byť ne nutně explicitně vyjádřené) formální gramatice.

Program, který vykonává tuto úlohu, se nazývá syntaktický analyzátor (slangově parser).

Syntaktickou analýzou se transformuje vstupní text do datové struktury, většinou stromu, jenž je vhodný pro pozdější zpracování a který zachovává hierarchii vstupních dat.

Vstupním krokem syntaktické analýzy je zpravidla lexikální analýza, při níž se ze vstupního textu vytváří posloupnost tzv. tokenů, tedy elementárních nositelů významu v rámci daného formálního jazyka. Tokenem může být např. závorka, literál (explicitně číslo, řetězec), proměnná, klíčové slovo, symbol a pod. Pro parser je to již dále nedělitelná základní stavební jednotka, které má uloženy v listech načteného datového stromu a které použije v interpretaci vstupních dat.

Existují i programy, schopné ze specifikace programovacího jazyka zapsaného v Backus-Naurově notaci vytvořit příslušný parser, např. Yacc (yet another compiler compiler).

Lidské jazyky[editovat | editovat zdroj]

Při některých metodách počítačového zpracování lidského jazyka se používá počítačových programů, které dokáží lidský jazyk syntakticky analyzovat. Tento úkol je dosti ztížen skutečností, že stavba lidského jazyka je zpravidla velmi nejednoznačná.

Pro syntaktickou analýzu lidského jazyka musí být nejprve stanovena příslušná formální gramatika. Volba její syntaxe závisí na záměrech jednak lingvistických, jednak implementačních. Některé analytické systémy například používají lexikálně-funkčních gramatik, ovšem v takovém případě je syntaktická analýza z hlediska složitosti NP-úplným problémem. Další pro syntaktickou analýzu často užívanou lingvistickou formalizací je HPSG gramatika, avšak některé projekty využívají i mnohem jednodušších formalizací (viz např. korpus syntaktických stromů Penn Treebank). Povrchová syntaktická analýza se zaměřuje jen na rozčlenění vstupního textu na hlavní součásti jako jmenné fráze. Jinou často využívanou možností, jak se vyhnout jazykové víceznačnosti, je syntaktická analýza podle dependenční gramatiky.

Moderní syntaktické analyzátory bývají alespoň částečně statistické, tedy opírají se o korpus dat, která byla analyzována ručně. Pomocí takového korpusu může program získat informace o frekvenci výskytu různých gramatických konstrukcí ve specifických kontextech (viz též strojové učení). Používané metody zahrnují pravděpodobnostní bezkontextové gramatiky, metodu maximální entropie a neuronové sítě. Většina úspěšnějších systémů užívá metody lexikální statistiky, tj. posuzuje slova v mj. závislosti na jejich slovním druhu. Takové systémy však mohou podléhat tzv. přeučení (overfitting) a pro dosažení efektivity vyžadují pečlivé doladění.

Algoritmy pro syntaktickou analýzu přirozených jazyků musí zacházet s gramatikami mnohem složitějšími a nepřehlednějšími, než jsou „hezké“ gramatiky umělých programovacích jazyků. Jak již bylo řečeno, některé gramatické struktury jsou pro analýzu výpočetně velmi složité. Obecně se i v případě gramatických struktur, které se nedají vyjádřit bezkontextově, užívá zjednodušených bezkontextových gramatik, pomocí nichž se provádí první krok analýzy. Algoritmy, které využívají bezkontextových gramatik, často spočívají na některé variantě algoritmu CKY, zpravidla doplněného heuristikou, která umožňuje vyřadit nepravděpodobné možnosti a tak ušetřit čas (viz též tabulková analýza). Některé systémy se snaží snížit výpočtovou složitost na úkor přesnosti užitím algoritmů LR analýzy pracujících v lineárním čase. Relativně novou metodou pak je parse reranking, při kterém syntaktický analyzátor navrhne vícero možných analýz, a složitější systém pak vybere, která z nich je nejvhodnější.

Programovací jazyky[editovat | editovat zdroj]

Syntaktické analýzy se obvykle užívá při kompilaci. Kompilátor nejprve syntakticky analyzuje zdrojový kód programu, napsaný v určitém programovacím jazyku, a převede jej do interní podoby, s níž poté dále pracuje.

Programovací jazyky bývají specifikovány bezkontextovými gramatikami, protože pro ty se dá vytvořit rychlý a efektivní syntaktický analyzátor. Ten však obvykle nebývá programován ručně, nýbrž generován zvláštním programem, tzv. parser generátorem, na základě předepsané gramatiky.

Bezkontextové gramatiky zpravidla nejsou schopny vyjádřit vše, co jazyk vyžaduje. Zjednodušeně se dá říci, že bezkontextově vyjádřený jazyk má omezenou paměť. Bezkontextová gramatika nemá prostředky k zapamatování předchozího výskytu konstruktu, pokud může být oddělen libovolně dlouhým jiným textem — nedokáže tedy třeba rozpoznat, zda byl identifikátor před použitím deklarován. Mocnější gramatiky, které toto dokáží, zase nemohou být efektivně syntakticky analyzovány. Proto se běžně vytváří bezkontextový parser, který rozpoznává nadmnožinu požadovaných jazykových konstruktů (tj. přijme i některé neplatné) s tím, že později budou tyto neplatné konstrukty vyřazeny.

Typy syntaktické analýzy[editovat | editovat zdroj]

Úkolem syntaktického analyzátoru je zjistit, zda a jak je možno vstupní text vygenerovat z počátečního symbolu gramatiky. Tohoto úkolu se analyzátor může zhostit jednou ze dvou základních metod:

  • Syntaktická analýza shora dolů — Parser začíná počátečním symbolem a snaží se převést jej na vstup. Schematicky řečeno začíná největšími prvky, které postupně rozbíjí na menší části, dokud se nedostane k terminálním symbolům, které může porovnat se vstupem. Příkladem syntaktické analýzy shora dolů je LL analýza.
  • Syntaktická analýza zdola nahoru — Parser začíná vstupním textem a snaží se jej převést na počáteční symbol. Prakticky tedy hledá nejprve pravidla, která obsahují dané terminální symboly, pak pravidla, která mohou takovým pravidlům předcházet atd. Příkladem syntaktické analýzy zdola nahoru je LR analýza. Jiný termín pro tento druh syntaktické analýzy je shift-reduce parsing (doslova „posuň-zmenši“, česky označováno jako „přesun-redukce“).

Další význačné rozlišení je mezi analýzou zleva doprava a analýzou zprava doleva, tedy mezi tím, zda analyzátor — jako například při LL analýze — generuje levou derivaci vstupního textu, nebo — jako například při LR analýze — pravou derivaci (viz článek bezkontextová gramatika).

Literatura[editovat | editovat zdroj]

  • Molnár, Ľudovít – Češka, Milan – Melichar, Bořivoj: Gramatiky a jazyky. Bratislava : Alfa, 1987.

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]