Detail výsledku
Syntaktická analýza založená na gramatikách s rozptýleným kontextem
Úkolem práce bylo navrhnout vhodný algoritmus pro syntaktickou analýzu, neboli parsing, nad gramatikami s rozptýleným kontextem (SCG). Množina jazyků, kterou lze získat pomocí tohoto typu gramatik, pokrývá kontextové jazyky. Syntaktická analýza je proces určování, zda řetězec vstupních symbolů je větou daného jazyka. Je-li, určí se syntaktická struktura řetězce. Syntaktickou analýzu provádí syntaktický analyzátor. Vstupem analyzátoru je řetězec lexikálních jednotek a výstupem je syntaktický strom nebo odvozená posloupnost. Jsou zde uvedeny dvě varianty algoritmů. Algoritmus I využívá kombinaci metody zdola nahoru a shora dolů. Součástí popisu algoritmu jsou i příklady a závěrečné zhodnocení. Uvádím i verzi upravenou pro paralelní prostredí. Algoritmus II je založen pouze na postupu zdola nahoru. Vzhledem k jeho složitosti je uveden i podrobný popis doplněný jednoduchými příklady. Závěrecné zhodnocení srovnává oba algoritmy.
The family of languages generated by scattered context grammar is contained in thefamily of context sensitive languages and contains all languages accepted by linear timenondeterministic Turing machines.
gramatiky s rozptýleným kontextem, syntaktická analýza, SCG
SCG, Scattered Context Grammar, Parsing
@inproceedings{BUT192573,
author="Petr {Blatný}",
title="Syntaktická analýza založená na gramatikách s rozptýleným kontextem",
booktitle="SVOČ 2004 - Soutěž vysokoškoláků ve vědecké odborné činnosti v matematice",
year="2004",
pages="32--32",
publisher="Fakulta strojního inženýrství VUT",
address="Brno",
isbn="0",
url="http://www.mat.fme.vutbr.cz/svoc/sekce_s4.html#blatny"
}