Syntaktická analýza: Porovnání verzí

'''Syntaktická analýza''' (slangově podle [[Angličtina|angličtiny]] též ''parsování'' nebo ''parsing'') se v  [[Informatika|informatice]] a v  [[Lingvistika|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í gramatika|formální gramatice]].

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]], číslo, řetězec, [[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í jazyk|programovacího jazyka]] zapsaného v  [[Backus-Naurova notace|Backus-Naurově notaci]] vytvořit příslušný parser, např. [[Yacc]] (''yet another compiler compiler'').

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í gramatika|lexikálně-funkčních gramatik]], ovšem v  takovém případě je syntaktická analýza z  hlediska složitosti [[NP-úplnost|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ů]] [http://www.cis.upenn.edu/~treebank/ 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í gramatika|dependenční gramatiky]].

Moderní syntaktické analyzátory bývají alespoň částečně [[Statistika|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á gramatika|pravděpodobnostní bezkontextové gramatiky]], [[Metoda maximální entropie|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í ({{cizojazyčně|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ě [[Algoritmus CKY|algoritmu CKY]], zpravidla doplněného [[Heuristika|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ýza|LR analýzy]] pracujících v  lineárním čase. Relativně novou metodou pak je {{cizojazyčně|en|[[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ší.

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

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.

=== Overview of process ===

The first stage is the token generation, or [[lexical analysis]], by which the input character stream is split into meaningful symbols defined by a grammar of [[regular expression]]s. For example, a calculator program would look at an input such as "12„12*(3+4)^2"2“ and split it into the tokens 12, *, (, 3, +, 4, ), ^ and 2, each of which is a meaningful symbol in the context of an arithmetic expression. The parser would contain rules to tell it that the characters *, +, ^, ( and ) mark the start of a new token, so meaningless tokens like "12„12*" or "(3"3“ will not be generated.

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

* [[LL syntaktický analyzátor|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í symbol|terminálním symbolům]], které může porovnat se vstupem. Příkladem syntaktické analýzy shora dolů je [[LL analýza]].

* [http://www.cs.vu.nl/~dick/PTAPG.html Parsing Techniques - A Practical Guide] - kniha podle Dick Grune a Ceriel J.H. Jacobs, dostupná v  PDF i PostScript

Některé z  parserů se syntaktickou analýzou ''shora dolů'' zahrnují např.:

<!--

Některé z &nbsp;parserů se syntaktickou analýzou ''zdola nahoru'' zahrnují např.:

=== Parser Development Software ===

==== Commercial ====

'''Parsování''' ({{cizojazyčně|en|parsing}}) v &nbsp;[[informatika|informatice]] znamená načítání zformátovaných dat. Parsování probíhá například při [[překladač|překladu]] nebo [[interpreter|interpretaci]] zdrojových programů nebo skriptů, ale za parsování může být pokládán i proces při zobrazování zdrojového textu článků [[Česká Wikipedie|Wikipedie]] v &nbsp;[[HTML]].

== Odlišnosti od prostého načítání dat ==

*Data jsou zformátována na části, kterým se ve většině případů říká '''elementy'''. Většinou se (opět, podle daných pravidel) mohou některé elementy vyskytovat v &nbsp;jiných elementech.