This thesis deals with path-controlled grammars, which are grammars that place restrictions on the paths in a derivation tree of a context-free grammar. The goal of this thesis is to create an algorithm for conversion between the path-controlled grammars and the state grammars, which is a di erent type of regulated grammars. Another goal is to study the generative power of path-controlled grammars based on the conversion algorithm. The conversion algorithm is implemented and tested on a number of path-controlled grammars. Also, its complexity is discussed. Finally, a parsing tool for path-controlled grammars is implemented. Complexity of this tool is analyzed as well.
Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:234906 |
Date | January 2015 |
Creators | Adamec, Ondřej |
Contributors | Soukup, Ondřej, Křivka, Zbyněk |
Publisher | Vysoké učení technické v Brně. Fakulta informačních technologií |
Source Sets | Czech ETDs |
Language | Czech |
Detected Language | English |
Type | info:eu-repo/semantics/masterThesis |
Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0016 seconds