Abstract
dc:descriptionIn recent years, due to the increased demand for computing power, combined with the requirement for portability, a large increase in the application field of embedded systems is observed. An Embedded System (ES) may be defined as a special purpose system with limited physical size, which performs a specific and predetermined task. Indeed, depending on the time constraints of the application, ES can be divided into two broad categories: those where real-time applications must be handled strictly (hard real time embedded) and those where time restrictions do not matter that much (soft real time embedded). In order to carry out the desired task, an ES is usually equipped with a microcontroller or even a microprocessor and has the lowest possible power requirements and relatively low cost. Therefore, instead of selecting a general purpose system, the usage of a system that can perform only a particular task but is small in size, has low power consumption, increased time requirements and low cost is preferred for specific applications. With the growing use of ES, there is a shift in applications from the field of pure software running on general purpose hardware to the field of specialized hardware/software coexistence (dedicated hardware). This shift has been significantly influenced by the progress in programmable hardware and more specifically of FPGA (Field Programmable Gate Arrays), which are hardware units that can be hardware programmed in order to execute a specific task. Thus, the programming goes to a new level, where the programmer is no longer required to write source code that will run on a specific processor but the code describes the hardware itself. The description is made with special Hardware Description Languages (HDL), typical HDL are Yerilog and YHDL. The main purpose of this thesis is the implementation in hardware (FPGA) of appropriate algorithms that add “intelligence'’ to an ES, through the recognition of sentences that belong in a context free grammar (CFG) and through the evaluation of the corresponding attributes for sentences belonging to an attribute grammar (AG). A grammar is defined as a system of production rules that produce strings. The grammar categories, as defined by Chomsky, vary but in the specific thesis only CFG and an extension of them, AG, will be used. For the syntactic recognition of a sentence, suitable algorithms are used to determine whether or not a sentence belongs to a given grammar. These binary algorithms, which only respond with a yes or a no for each sentence, are called recognizers. In the case that during the recognition, a parse tree is also constructed for the given sentence, the algorithm is called parser. Furthermore, a platform for the automatic production of intelligent ES is proposed. Rather than describing the ES in classical Yerilog or YHDL, it is described at a higher level using the symbolism of attribute grammars. The implementation of attribute grammars is based on the parallel implementation of Earley’s algorithm and is an extension of the latter, allowing its implementation with smaller space and time requirements. Moreover, it has been properly extended in order to be capable to also handle attribute grammars and evaluate the corresponding attributes, defining the semantics of the grammar. To evaluate these attributes, a unit to perform the necessary actions is essential. During this work, different architectures for the syntactic analysis and the attribute evaluation have been used. More specifically, to evaluate the attributes depending on the requirements in computing power and size, the following has been chosen; the usage of a microcontroller, an external general purpose microprocessor, an internal general purpose microprocessor and finally the usage of special purpose processor specially designed for the needs of each application.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Dimopoulos, Alexandros
- Δημόπουλος, Αλέξανδρος
Subjects
dc:subject × 11Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/17758