This thesis focuses on modern methods of language description. It introduces several controlled grammars, describing in detail the tree controlled grammar. The thesis is based on relatively new technique of syntax analysis using tree controlled grammars. The process of this analysis is described in detail, followed by a design of parallel-processing of this analysis. We managed to succesfully implement this design, speed up the syntax analysis and therefore achieve the main goal of the thesis.

This work deals with advanced models of context-free grammars and explores the possibilities of adaptation and usefulness for deterministic parsing of non-context-free sructures by deep parsing method. It introduces adapted model of context-free grammar named LL programmed grammar and adapted deep pushdown automaton that makes deterministic parsing of non-context-free structures possible.

Multygeneratic system is based on cooperation action of infinity count of context-free grammars. All this context free-grammars parallel and synchronous derivate individual sentential form. During generation came in each specific derivation step to checking of correction of each generated sentential forms. This checking can be made by different ways. Solution is then so-called multistring (vector of strings), so by the help of this is defined generated language.

The composition and reuse of existing textual languages is a frequently re-occurring problem. One possibility of composing textual languages lies on the level of parser specifications which are mainly based on context-free grammars and regular expressions. Unfortunately most mainstream parser generators provide proprietary specification languages and usually do not provide strong abstractions for reuse. New forms of parser generators do support modular language development, but they can often not be easily integrated with existing legacy applications. To support modular language development based on mainstream parser generators, in this paper we apply the Invasive Software Composition (ISC) paradigm to parser specification languages by using our Reuseware framework. Our approach is grounded on a platform independent metamodel and thus does not rely on a specific parser generator.

Combinatory categorial grammar (CCG) is a mildly-context sensitive formalism that is well-established in computational linguistics. At the basis of the grammar are a lexicon and a rule system: The lexicon assigns syntactic categories to the symbols of a given input string, and the rule system specifies how adjacent categories can be combined, yielding a derivation tree whose nodes are labeled by categories. In this thesis, we focus on composition rules, which are present in all variants of the grammar. Vijay-Shanker and Weir famously show that CCG can generate the same class of string languages as tree-adjoining grammar, linear indexed grammar, and head grammar. Their equivalence proof relies on two particular features of the grammar: ε-entries, which are lexicon entries for the empty word, and rule restrictions, which allow to restrict the rule set on a per-grammar basis. However, modern variants of CCG tend to avoid these features. This raises the question how this changes the generative and computational power of CCG. Another important feature is the rule degree, which determines how complex a certain category involved in a rule application may be. The goal of this thesis is to shed light on the effects that changing these features has. When modeling natural language, one is not only interested in the acceptability of a sentence, but also in its underlying structure. Therefore, we study the sets of constituency trees that CCG can generate, which are obtained by relabeling sets of derivation trees. We first provide a new proof of an analogous result by Buszkowski, showing that when only application rules are allowed, a proper subset of regular tree languages can be generated by CCG. Then, we show that when composition of first degree is included, CCG can generate exactly the regular tree languages. On the other hand, pure CCG, which allows all rules up to some degree, is shown to not even generate all local tree languages. Our main result on the generative capacity of CCG is its strong equivalence to tree-adjoining grammar. This means that these formalisms can generate the same class of tree languages. This is even the case when only composition rules of second degree and no ε-entries are used, showing that a CCG with these properties already has its full expressive power. Our constructions also provide an effective procedure for the removal of ε-entries. Regarding computational complexity, ε-entries and high rule degrees are in fact problematic. Kuhlmann, Satta, and Jonsson studied the universal recognition problem for CCG, which asks whether some given string is generated by some given grammar, considering both as part of the input. They prove that this problem is EXPTIME-complete if ε-entries are included, and NP-complete if not. We refine this result and show that the runtime is exponential only in the maximum rule degree of the grammar. Hence, when the rule degree is bounded by a constant, parsing becomes polynomial in the grammar size. This also holds when substitution rules are included in the rule system.

In this thesis, three methods are investigated to express context-free tree languages by regular tree grammars. The first method is a characterization. We show restrictions to context-free tree grammars such that, for each restricted context-free tree grammar, a regular tree grammar can be constructed that induces the same tree language. The other two methods are approximations. An arbitrary context-free tree language can be approximated by a regular tree grammar with a restricted pushdown storage. Furthermore, we approximate weighted context-free tree languages, induced by weighted linear nondeleting context-free tree grammars, by showing how to approximate optimal weights for weighted regular tree grammars.

This thesis considers the problem of assigning a sentence its syntactic structure, which may be discontinuous. It proposes a class of models based on probabilistic grammars that are obtained by the automatic refinement of a given grammar. Different strategies for parsing with a refined grammar are developed. The induction, refinement, and application of two types of grammars (linear context-free rewriting systems and hybrid grammars) are evaluated empirically on two German and one Dutch corpus.

The thesis examines the theory of formal languages in the field of context-free grammars. It focuses mainly on the possibilities and models of collaborating grammars to solve a common problem. In this context, it presents grammatical systems that have been designed as a formal means for describing distributed and parallel processing. After introducing to the problematics, the thesis focuses on the practical use of these mechanisms in the translation controlled syntax, and therefore the second part of the thesis deals with the implementation of a dynamic syntactic analyzer that uses more grammars during the analysis. With respect to the greatest user friendliness and the possible didactic use, the application is implemented using modern web technologies HTML5, JavaScript, AngularJS, CSS3, LESS and more.

This thesis provides a summary of knowledge of grammar systems. The thesis proposes modifications of parallel oriented grammar systems to be usable in sequential parsing. Concept of grammar systems is extended to level of entire parsers, that are grouped into parsing system. Then the properties of these systems are examined. The aim of thesis is to introduce approaches to syntactic analysis based on grammar systems. Thesis is based on context-free methods of syntactic analysis, extending them and connecting them together. Great attention is dedicated to increase generative capacity of LL and LR parsing. There were created context-free structures within this thesis, which are capable to generate context-sensitive languages. This work also provides a simple recipe for implementation of these structures. We introduced generic concept of parsing, that enlarge generative power of conventional parsing methods. Using presented techniques it is possible to extend many of often used languages with context-sensitive elements, especially elements contradicting with pumping lemma.

This thesis is a continuation of my bachelor thesis, which is dedicated to syntax analysis based on deep pushdown automata. In theorical part of this thesis is defined everything fundamental for this work, for example deep syntax-directed translation, pushdown automata, deep pushdown automata, finite transducer and deep pushdown transducer.   The second part of this thesis is dedicated to the educational program for students of IFJ. In this part is defined strucure of this program and its parts. All part of program are analyzed from a theoretical and practical point of view.