|
[[Soubor:Parsing-example.png|thumb|right|PříkladSyntaktická syntaktickéanalýza analýzypoužitá pro převod zápisu matematického výrazu na [[syntaktický strom]].]]
'''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]].
Program, který vykonává tuto úlohu, se nazývá '''syntaktický analyzátor''' (slangově ''parser'').
SyntaktickouPři analýzousyntaktické analýze se transformuje vstupní text dozpravidla transformuje na určité [[datová struktura|datové struktury]], většinou [[syntaktický strom| syntaktického stromu]] nebo méně abstraktníhoabstraktní [[derivační strom| derivačního stromu]], jenžkteré jezachovávají vhodnýhierarchické prouspořádání pozdějšívstupních zpracovánísymbolů a kterýjsou zachovávávhodné hierarchiipro vstupníchdalší datzpracování.
VstupnímSyntaktické krokemanalýze syntaktickézpravidla analýzy je zpravidlapředchází [[lexikální analýza]], při níž se zevstupní vstupníhotext texturozděluje vytvářína posloupnost tzv.lexikálních symbolů neboli ''[[token]]ů'', tedy– elementárních nositelů významu v rámci daného formálního jazyka. TokenemPři můžeanalýze býttextu např.v závorkapřirozeném jazyce jsou symboly obvykle slovní tvary a interpunkce, v programovacím jazyce [[identifikátor]]y, [[literál]]y (explicitně čísločísla, řetězecřetězce), [[proměnnáklíčové slovo|klíčová slova]], [[klíčové slovooperátor]]y, symbol[[oddělovač]]e a pod. Pro parser je to jižjsou dále nedělitelná základnínedělitelné stavební jednotkajednotky, které mápoužívá uloženypři 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(zapsané např. v [[Backus-Naurova notace|Backus-Naurově notaci]]) vytvořit příslušnýparser. Mezi nejznámější takovéto [[parser, např.generátor|generátory parserů]] patří program [[Yacc]] (''yet another compiler compiler'').
== Lidské jazyky ==
== Programovací jazyky ==
Syntaktická analýza je důležitou částí zpracování programů při jejich překladu (kompilaci) nebo interpretaci. Zatímco [[interpret (software)|interpret]] provádí výpočet (interpretaci) nad datovými strukturami vytvořenými analýzou programu napsaném v určitém [[programovací jazyk|programovacím jazyce]], [[Překladač|kompilátor]] z těchto datových struktur generuje program v cílovém jazyce, který lze (po dalších úpravách) interpretovat hardwarovým nebo virtuálním [[procesor]]em.
Syntaktické analýzy se obvykle užívá při kompilaci. [[Překladač|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.
Programovací jazyky bývají specifikovány deterministickými [[Bezkontextová gramatika|bezkontextovými gramatikami]], protože pro ty sekteré dálze 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átor]]em, 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ěobvykle vytvářípoužívá bezkontextový parser, který rozpoznává nadmnožinu požadovaných jazykových konstruktů (tj. přijmepřijal by i některé neplatné) s tím, žev pozdějikombinaci budous tytodalšími neplatnénástroji, obvykle [[Tabulka konstruktysymbolů|tabulkou vyřazenysymbolů]].
<!--
prosím případné spolupřekladatele, aby překládali jen to, čemu rozumějí!!! (Mmh)
=== OverviewProces of processanalýzy ===
Následující příklad demonstruje obvyklý postup analýzy programovacího jazyka se dvěma úrovněmi gramatiky: lexikální a syntaktickou.
The following example demonstrates the common case of parsing a computer language with two levels of grammar: lexical and syntactic.
První fází je [[lexikální analýza]], při níž se vstupní text, na který lze pohlížet jako na proud znaků, členěn na symboly (tokeny), zpravidla definované gramatikou [[regulární výraz|regulárních výrazů]]. Například [[kalkulátor]], který má zpracovávat vstup tvaru <code>127 * (3+45)^2</code>, jej rozloží na symboly <code>127</code>, <code>*</code>, <code>(</code>, <code>3</code>, <code>+</code>, <code>45</code>, <code>)</code>, <code>^</code> a <code>2</code>, z nichž každý je smysluplným symbolem v aritmetickém výrazu. Parser obsahuje pravidla, která určují, že znaky <code>*</code>, <code>+</code>, <code>^</code>, <code>(</code> a <code>)</code> označují začátek nového symbolu, takže nebudou uvažované nesmyslné symboly jako <code>12*</code> nebo <code>(3</code>.
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*(3+4)^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*" or "(3“ will not be generated.
Další fází je syntaktická analýza (parsing), při které se kontroluje, zda posloupnost symbolů tvoří povolený výraz. Na této úrovni je jazyk obvykle popsán [[bezkontextová gramatika|bezkontextovou gramatikou]], která rekurzivně definuje komponenty, z nichž lze složit výraz, a pořadí, ve kterém se musí objevit. Některá pravidla definující programovací jazyky nemohou být vyjádřena bezkontextovou gramatikou – problémy činí například typová kontrola a deklarace identifikátorů. Tato pravidla mohou být formálně vyjádřena pomocí [[atributová gramatika|atributové gramatiky]] a jejich dodržování se prakticky kontroluje pomocí [[tabulka symbolů|tabulky symbolů]].
The next stage is syntactic parsing or syntactic analysis, which is checking that the tokens form an allowable expression. This is usually done with reference to a [[context-free grammar]] which recursively defines components that can make up an expression and the order in which they must appear. However, not all rules defining programming languages can be expressed by context-free grammars alone, for example type validity and proper declaration of identifiers. These rules can be formally expressed with [[attribute grammar]]s.
Poslední fází je [[sémantická analýza]], která zjišťuje význam jednotlivých částí datové struktury a přiřazuje jim příslušné akce. V případě [[kalkulátor]]u mohou být těmito akcemi např. ukládání konstant na [[Zásobníkový počítač|zásobník]] nebo provedení určité aritmetické operace; v případě [[překladač]]e je akcí generování fragmentů [[Strojový kód|kódu]]. Pro definování těchto činností lze použít [[překladová gramatika|překladovou gramatiku]].
The final phase is [[Semantic analysis (computer science)|semantic parsing]] or analysis, which is working out the implications of the expression just validated and taking the appropriate action. In the case of a calculator, the action is to evaluate the expression; a compiler, on the other hand, would generate code. Attribute grammars can also be used to define these actions.
//-->
== Typy syntaktické analýzy ==
Úkolem syntaktického analyzátoru je zjistit, zda a jak je možno vstupní text vygenerovat z [[Formální_gramatika#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]].
* [[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 {{cizojazyčně|en|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]]'').
Další ještě význačnější rozlišení je mezi ''deterministickou analýzou'' a ''nedeterministickou analýzou''.
<!-- //pův. text
'''Parsování''' ({{cizojazyčně|en|parsing}}) v [[informatika|informatice]] znamená načítání zformátovaných dat. Parsování probíhá například při [[překladač|překladu]] nebo [[interpreterinterpret (software)|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 [[HTML]].
Program nebo jeho část, která parsování provádí, se nazývá '''parser'''.
| 