Syntaktická analýza zdola nahoru

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Syntaktická analýza zdola nahoru je v informatice postup syntaktické analýzy, který identifikuje nejdříve základní jednotky a z nich potom odvozuje strukturu s vyšší úrovní uspořádání. Název strategie vychází z konceptu derivačního stromu, který má nejzákladnější jednotky ve spodní části, ze kterých postupně vnikají struktury složené. Na vrcholu stromu je posléze samostatná jednotka nebo symbol zahrnující všechny informace, které jsou analyzovány. V této strategii zpracování dochází k analýze obou jazyků jak „přirozeného jazyka“, tak „počítačového jazyka“, což je v kontrastu se syntaktickou analýzou shora dolů, ve které jsou komplexní jednotky děleny do jednodušších částí až do okamžiku, kdy jsou veškeré informace zpracovány.

Lingvistika[editovat | editovat zdroj]

V lingvistice by mohla být jako příklad na syntaktickou analýzu zdola nahoru uvedena analýza věty. Nejprve identifikujeme jednotlivá slova a poté použijeme vlastnosti slov na odvození vztahů, jako jsou např. gramatiky a struktury frází, k sestavení derivačního stromu[1] z několika úplných vět.

Příklad[editovat | editovat zdroj]

Derivační strom věty „John hit the ball“.

V angličtině může být věta „John hit the ball“ analyzována od zdola nahoru. V tomto případě tvoří základ slova „John“, „hit“, „the“ a „ball“ (při ignorování konjugace a deklinace).

V gramaticky zjednodušené angličtině je pro tuto větu dostačující:

  1. věta může mít jmennou frázi následovanou frázovým slovesem (S → NP VP),
  2. jmennou frází může být samo podstatné jméno,
  3. jmenná fráze může být také determinant následovaný podstatným jménem (NP → Det N],
  4. frázové sloveso může být sloveso následované jmennou frází (VP → V NP),
  5. podstatná jména, determinanty a slovesa jsou všechna slova (N → word, Det → word, V → word).

Při zpracování těchto slov od zdola nahoru nalezneme:

Použité pravidlo Zpracované slovo Současná věta
5 V tomto případě je „John“ a „ball“ podstatné jméno, „the“ je determinátor a „hit“ je sloveso. NV Det N
3 „the ball“ je jmenná fráze. NV NP
4 „hit the ball“ je frázové sloveso. N VP
2 „John“ je jmenná fráze sama o sobě. NP VP
1 „John hit the ball“ je celá věta. S

Možné je další zpracování, např. slovo „ball“ může být zpracováno jako jmenná fráze. Nicméně žádné jiné zpracování nemůže použitím těchto zjednodušených pravidel vést k celé větě. Jak je jednou „ball“ vybráno jako jmenná fráze, tak zde není pravidlo, které by nám umožnilo zpracovat „the“. „Hrubá vyhledávací síla“ může být použita k nalezení všech možných zpracování věty. Pokud je možné více než jedno zpracování, znamená to, že má věta dvojjazyčný význam, což není běžné v přirozených jazycích.

Počítačová věda[editovat | editovat zdroj]

Kompilátory programovacích jazyků založených na syntaktické analýze zdola nahoru používají metodu, která identifikuje nejdříve terminální symboly. Poté je kombinuje postupně tak, že produkuje neterminální symboly. Produkt zpracování může být použit k vytvoření derivačního stromu z programu napsaného člověku čitelné formě zdrojového kódu tak, že může být zkompilován, aby sestavil jazyk pro pseudokód.

Odlišné počítačové jazyky vyžadují odlišné techniky zpracování. Není běžné používat techniku zpracování, která je silnější, než je potřeba.

Při syntaktické analýze zdola nahoru je běžné použít formu obecného prostředku pro zpracování, který buď zpracovává, nebo generuje analyzátor pro specifický Pravděpodobně nejznámějšími zobecněnými analyzátorovými generátory jsou Yacc a GNU bison.

Příklad[editovat | editovat zdroj]

Tato jednoduchá gramatika definuje prostý součet výrazů:

  1. kompletní výraz (suma) může být sčítanec, znaménko plus a plus jiný sčítanec (S → A “+” A),
  2. sčítanec může být písmeno, resp. proměnná (A → P),
  3. sčítanec rovněž může být číslo (A → C),
  4. sčítanec může být rovněž suma jako taková (A → S),
  5. číslo tvoří jedna číslice nebo více číslic (C → cislice+).

Znaménko plus v pravidlu č. 5 značí opakovatelnost „jedna nebo více číslic“. Pro rozlišení tohoto použití od speciálního použití je znaménko plus v pravidlu č. 1, které je umístěno uvnitř uvozovek.

Základní jednotky gramatiky jsou jednotlivá písmena, znaménko plus a skupiny s jednou nebo více číslicemi. Proto jsou na vstupu „a + x + 12“ základní jednotky „a“, „+“, „x“, „+“ a „12“. Zpracování může vypadat například takto:

Použité pravidlo Zpracovaný symbol Současný výraz
5 „12“ je číslo a + x + C
2, 2, 3 „a“, „x“ a „12“ jsou sčítance A + A + A
1 „a + x“ je celá suma S + A
4 suma „a + x“ je také sčítanec A + A
1 „a + x + 12“ je celá suma S

Na rozdíl od přirozeného jazyka nemůže být počítačový jazyk nejednoznačný. Proto zpracování zdola nahoru musí mít pro počítačový jazyk dodatečná pravidla jako „nejvíce vlevo možné nahrazení je vybráno“. Počítačové zpracování zřídkakdy prozkoumává celý vstup najednou (vstup může být velmi rozsáhlý počítačový program). Většina analyzátorů čte vstup od začátku do konce (tj. „zleva doprava“). Nicméně možnost ověřit více následujících symbolů („lookahead“) před aplikováním pravidel zvyšuje vyjadřovací sílu gramatiky.

Posuvně-redukční zpracování[editovat | editovat zdroj]

Nejběžnější zpracování ze zdola nahoru představuje posuvně-redukční zpracování. Tyto analyzátory prozkoumávají vstupní tokeny a buď je posunují (push) do zásobníku, nebo redukují elementy na vrcholu zásobníku nahrazováním pravou stranu za levou.

Tabulka činností (analýza činností)[editovat | editovat zdroj]

Často je konstruována tabulka činností, která pomáhá analyzátoru určit co zpracovat příště. Následuje popis toho, co může být uvedeno tabulce činností.

Činnost[editovat | editovat zdroj]

  • Posun – posun tokenu na zásobník
  • Redukce – odebrání handlu ze zásobníku a vložení odpovídajícího neterminálu
  • Příjem – rozpoznání věty, kdy zásobník obsahuje pouze odlišné symboly a zásobník je prázdný
  • Chyba – pokud není ani jedno z výše uvedeného možné, což znamená, že původní vstup nebyla věta

Posun a redukce[editovat | editovat zdroj]

Analyzátor posunu a redukce používá zásobník pro udržení symbolů gramatiky, zatímco očekává redukci. Během operace analýzy jsou symboly ze vstupu posunuty na zásobník. Pokud prefix symbolů na vrcholu zásobníku souhlasí s RHS (right-hand side) pravidlem gramatiky, které je korektní pravidlo pro použití v tomto kontextu. Následně analyzátor redukuje RHS pravidlo k LHS (left-hand side) nahrazením symbolu RHS na vrcholu zásobníku neterminálem vyskytujícím se na LHS pravidlem. Tento proces posun-redukce pokračuje dokud analyzátor neskončí úspěchem nebo selháním. Pokud skončí úspěchem, potom je vstup v pořádku a je přijat analyzátorem. Pokud skončí selháním, byla detekována chyba na vstupu.

Analyzátor je zásobníkový automat, který se nachází v jednom z několika diskrétních stavů. Ve skutečnosti v případě analyzátoru LR obsahuje zásobník analyzátoru spíše stavy než symboly gramatiky. Nicméně pokud každý stav odpovídá unikátnímu symbolu gramatiky, stav zásobníku může být namapován na gramatické symboly dříve zmíněného zásobníku.

Algoritmus posuvně-redukčního analyzátoru:

  1. začneme s analyzovanou větou jako výchozí větnou formou,
  2. dokud je větná forma startovací symbol:
    1. prozkoumávání vstupu dokud nerozpozná něco, co odpovídá RHS jednomu produkčnímu pravidlu, toto se nazývá handle,
    2. opačnou aplikace produkčního pravidla nahradíme RHS pravidlem, které se objeví ve větné formě pravidlem LHS (akce známá jako redukce).

V kroku 2.1 je posunut vstupní symbol ke straně tak, jak je přesouván přes sebe. Proto analyzátory, které operují opakovaně aplikováním předešlých kroků 2.1, 2.2 jsou známé jako posuvně redukční analyzátory.

Posuvně-redukční analyzátory se převážně implementují za pomoci zásobníku, kde postupujeme takto:

  • Začneme s prázdným zásobníkem.
  • Akce „posun“ odpovídá posunu současného vstupního symbolu na zásobník.
  • Akce „redukce“ nastává, když se pracuje na vrcholu zásobníku. K provedení redukce vyjmeme handle ze zásobníku a nahradíme jej neterminálem přes LHS odpovídajícím pravidlem.

Reference[editovat | editovat zdroj]

  1. http://www.cs.vsb.cz/kot/anim/a-deriv_strom.pdf – derivační strom

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

Externí odkazy[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Bottom-up parsing na anglické Wikipedii.