Original title:
Návrh systému pro aplikaci deformačních gramatik
Authors:
Junek, Lukáš Document type: Bachelor's theses
Year:
2014
Language:
cze Abstract:
[cze][eng] V bakalářské práci se zabývám návrhem a implementací syntaktického analyzátoru řetězových kódů popisujících určitý objekt. Během návrhu jsem musel vyřešit řadu obtíží. Vypořádat se s natočením objektů, možnou různou velikostí, ale hlavně s deformacemi ve vstupním kódu. Nakonec jsem implementoval rozšířenou verzi Tomita parsru, který se dokáže dobře vyrovnat s nejednoznačností akcí v LR tabulce a konflikty na vstupu. Funkčnost implementovaného programu jsem následně ověřil sérií testů, kde jsem posuzoval správnost detekce objektu a celkový čas potřebný k syntaktické analýze.In my Bachelor thesis I am dealing with designing and implementation of my syntactic analyser. My parser processes chain codes describing a particular object. During the draft, I had to solve some problems. Deal with the object rotation, possibility of object different sizes, but especially with deformations in the input code. Finally, I implemented an extend version of Tomita parser that is able to cope well with ambiguity of actions in the LR table and with conflicts on the entry. Then I verified functionality of my implemented program by series of tests, where I assessed the accuracy of object detection and total time required for parsing.
Keywords:
deformační gramatiky; LR parser; LR tabulka; syntaktická analýza; Tomita parser; řetězové kódy