No description available.

Specifications of digital hardware systems are typically written in a natural language. The objective of this research is automatic information extraction from specifications to aid model generation for system level design automation. This is done by automatic extraction of the noun phrases and the verbs from the natural language specification statements. First, the natural language sentences are parsed using a chart parser. Then, a noun phrase and verb extractor scans these charts to obtain the noun phrases with their frequencies of occurrence. The noun phrases are then classified by semantic types. Also the verbs are automatically assigned their respective roots and classified. Finally, each sentence is summarized as a sequence of "chunks": noun phrases, verbs and prepositions. Vectors are generated from these chunks and imported into MS Excel for plotting occurrence graphs of noun phrases and verbs with respect to the sentences in which they occur. Finally, inter-term dependencies between noun phrases, and between noun phrases and verbs were studied. The frequencies of occurrence, the classification of chunks, the occurrence graphs and the inter-term dependencies together give useful information about the subject, the hardware components and the behavior of a system described by a natural language specification document. / Master of Science

The objective of this research was to extract simple noun phrases from natural language texts using two different grammars: stochastic context-free grammar (SCFG) and non-statistical context free grammar (CFG). Precision and recall were calculated to determine how many precise and correct noun phrases were extracted using these two grammars. Several text files containing sentences from English natural language specifications were analyzed manually to obtain the test-set of simple noun-phrases. To obtain precision and recall, this test-set of manually extracted noun phrases was compared with the extracted-sets of noun phrases obtained using the both grammars SCFG and CFG. A probabilistic chart parser was developed by modifying a deterministic parallel chart parser. Extraction of simple noun-phrases with the SCFG was accomplished using this probabilistic chart parser, a dictionary containing word probabilities along with the meaning, context-free grammar rules associated with rule probabilities and finally an algorithm to extract most likely parses of a sentence. The probabilistic parsing algorithm and the algorithm to determine figures of merit were implemented using C++ programming language. / Master of Science

This PhD thesis deals with the use of structural methods of objects identification for industrial robots operation. First, the present state of knowledge in the field is described, i.e. the whole process of objects recognition with the aid of common methods of the syntactic analysis. The main disadvantage of these methods is that is impossible to recognize objects whose digitalized image is corrupted in some ways (due to excessive noise or image disturbances), objects are therefore deformed. Further, other methods for the recognition of deformed objects are described. These methods use structural description of objects for object recognition, i.e. methods which determine the distance between attribute descriptions of images. The core part of this PhD thesis begins in Chapter 5, where deformation grammars, capable of description of all possible object deformations, are described. The only complication in the analysis is the ambiguity of the deformation grammar, which lowers the effectiveness of the analysis. Further, PhD thesis deals with the selection and modification of a proper parser, which is able to analyze a deformation grammar effectively. Three parsers are described: the modified Earley parser, the modified Tomita parser and the modified hybrid LRE(k) parser. As for the modified Earley’s parser, ways of its effective implementation are described. One of the necessary parts of the object recognition is providing the invariances, which this PhD thesis covers in detail, too. Finally, the results of described algorithms are mentioned (successfulness and speed of deformed objects recognition) and suggested testing environment and implemented algorithms are described. In conclusion, all determined possibilities of deformation grammars and their results are summarized.

Title: Pattern matching in compilers Author: Ondřej Bílka Department: Department of Applied Mathematics Supervisor: Jan Hubička, Department of Applied Mathematics Abstract: In this thesis we develop tools for effective and flexible pattern matching. We introduce a new pattern matching system called amethyst. Amethyst is not only a generator of parsers of programming languages, but can also serve as an alternative to tools for matching regular expressions. Our framework also produces dynamic parsers. Its intended use is in the context of IDE (accurate syntax highlighting and error detection on the fly). Amethyst offers pattern matching of general data structures. This makes it a useful tool for implement- ing compiler optimizations such as constant folding, instruction scheduling, and dataflow analysis in general. The parsers produced are essentially top-down parsers. Linear time complexity is obtained by introducing the novel notion of structured grammars and reg- ularized regular expressions. Amethyst uses techniques known from compiler optimizations to produce effective parsers. Keywords: Packrat parsing, dynamic parsing, structured grammars, functional programming 1

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.

The OpenModelica Compiler-Compiler parser generator (OMCCp) is an LALR(1) parser generator implemented in the MetaModelica language with parsing tables generated by the tools Flex and GNU Bison. The code generated for the parser is in MetaModelica 2.0 language which is the OpenModelica compiler implementation language and is an extension of the Modelica 3.2 language. OMCCp uses as input an LALR(1) grammar that specifies the Modelica language. The generated Parser can be used inside the OpenModelica Compiler (OMC) as a replacement for the current parser generated by the tool ANTLR from an LL(k) Modelica grammar. This report explains the design and implementation of this novel Lexer and Parser Generator called OMCCp. Modelica and its extension MetaModelica are both languages used in the OpenModelica environment. Modelica is an Object-Oriented Equation-Based language for Modeling and Simulation.

Dans cette thèse, nous nous intéressons aux relations qui peuvent exister entre des prédicats verbaux(ex : to regulate) et des prédicats nominaux (ex : regulation) dont les structures argumentales mettent enjeu des informations communes. Nous nous livrons à une formalisation des conditions dans lesquelles se réalisent des relations d’équivalence entre les constructions verbales et nominales. La mise en évidence de l’équivalence des structures argumentales de ces deux types de constructions est fondamentale pour pouvoir réaliser, par exemple, des systèmes d’extraction automatique d’informations très performants. En se basant sur les données du lexique The Specialist Lexicon, nous proposons une prédiction raisonnable du comportement syntaxique des arguments nominaux, de différents groupes nominaux prédicatifs(GNpréd), lorsqu’ils sont en position de postmodifieur. Cette étude nous a conduit à concevoir un ensemble d’algorithmes et à développer une plate-forme, Predicate DB, qui nous a permis de produire un lexique de nominalisations. Pour chaque entrée appartenant à ce lexique, nous avons caractérisé ses structures argumentales et ses réalisations dans des GNpréd dont les arguments sont marqués par des prépositions spécifiques. / In this thesis, we focus on the relation that may exist between verbal predicates (e.g., regulate)and nominal predicates (e.g., regulation) whose argument structures involve common information.We make a formalization of the conditions in which equivalent relations between verbal and nominalconstructions are carried out. Bringing out the equivalence of argument structures between these twotypes of constructions is fundamental for achieving, for example, very efficient Information Extractionsystems. Based on data from the Specialist Lexicon, we propose a reasonable prediction of the syntacticbehavior of nominal arguments, which belong to different predicate noun phrases (PNPs), when theyare in postmodifier position. This study has led us to design a set of algorithms and develop a platform,PredicateDB, to produce a lexicon of nominalizations. For each entry belonging to this lexicon, we havedefined its argument structures and achievements in PNPs whose arguments are marked by specificprepositions.

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.

Operatorless Prolog text is LL(1) in nature and any standard LL parser generator tool can be used to parse it. However, the Prolog text that conforms to the ISO Prolog standard allows the definition of dynamic operators. Since Prolog operators can be defined at run-time, operator symbols are not present in the grammar rules of the language. Unless the parser generator allows for some flexibility in the specification of the grammar rules, it is very difficult to generate a parser for such text. In this thesis we discuss the existing parsing methods and their modified versions to parse languages with dynamic operator capabilities. Implementation details of a parser using Javacc as a parser generator tool to parse standard Prolog text is provided. The output of the parser is an “Abstract Syntax Tree” that reflects the correct precedence and associativity rules among the various operators (static and dynamic) of the language. Empirical results are provided that show that a Prolog parser that is generated by the parser generator like Javacc is comparable in efficiency to a hand-coded parser.