The GNAT compilation system is a full implementation of Ada95 for a variety of machines and operating systems. GNAT is part of the GCC suite of compilers, and as such it is distributed under the GNU Public licence, with the suitable modified library licences that allow its full use in industrial contexts.
The GNAT system was first developed as an academic project at New York University (its was originally the acronym for the GNU NYU Ada Translator, but it is now a name with no encrypted meaning). Ada Core has taken over maintenance and development of the system since 1995. A version of the system is now part of the GCC sources, which has made Ada 95 into one of the core GCC languages.
GNAT is nowadays a mature technology used for large-scale industrial projects, as well as research and education in compiler technology. Though the system continues to evolve as it is ported to new targets, as more sophisticated optimizations are implemented (and as occasional bugs are fixed), the architecture of GNAT has been stable for a number of years. The purpose of the present document is to make this architecture more accessible to users and researchers. The sources of GNAT are very carefully documented, but a program of half-a-million lines is a daunting object to approach, and we hope that this document will make this approach easier.
Understanding a compilation system requires mastering two complementary subjects: the semantics of the programming language being implemented, and the algorithms that realize the translation and implement the run-time semantics. We have structured this document to serve as bridge between the two entities that are the ultimate authorities on each: the Ada95 reference manual, and the full sources of GNAT. We expect that the user of this document will navigate between it, the ARM, and GNAT, as need and curiosity dictate. For this reason the document has extremely numerous links to both, integrating them into a hypertext that is flexible, reasonably complete, and easy to navigate.
The code generator for GNAT is the GCC back-end, whose portability has allowed GNAT to be implemented on many targets. The architecture of GCC has been the subject of many publications, and we do not discuss any of it here. Therefore, this book is concerned only with the front-end of a full compilation system. This is large enough a task!
The standard description of a compiler front-end distinguishes between the context-free portions of the translation (lexical and syntactic translation), and the context-sensitive phase (static semantics). In this book we focus mostly on the second phase, for reasons of space, technical interest, and personal competence.
The book should be of interest to software practitioners interested in compiler technology, language experts who want to examine the implementation of complex constructs in a modern programming language, compiler writers looking for ideas, and software engineers interested in Ada95, in concurrency, in distributed programming and in real-time systems. Finally, the book will be useful to those who want to experiment with language extensions, and want to modify portions of GNAT to implement new constructs in Ada95 or the forthcoming Ada 2005 revision of the language.
In an educational context, the GNAT front-end is an interesting adjunct to courses in programming languages, compilers, and operating systems. The GNAT front-end translates a modern, complex imperative language with a rich type system, object-oriented features, and genericity. These central aspects of modern languages (Ada95, C++, Java, C#, etc.) are seldom discussed in detail in texts on Compilers. The user of this book will find therein a summary of the central implementation choices made in GNAT, and pointers to the detailed algorithms in the sources.
The GNAT run-time supports concurrency (tasking, protected objects) on a variety of operating systems, by means of a mostly-target-independent interface, whose primitives are close to those of the POSIX standard. As such, it can be a useful adjunct in a discussion of Operating Systems, of the semantics of concurrency, and on the efficiency of various synchronization primitives.
The book is not intended to be a stand-alone text in Compilers, nor a reference in which to learn Ada. The reader is assumed to have some familiarity with the language, and with basic compilation techniques, such as would be a found in a senior course in Programming Languages. We have included brief descriptions of the more interesting constructs in the language, to motivate the issues of implementation that we want to discuss. We have also included numerous language fragments to illustrate specific translation techniques. Many of these fragments present not just a source program, but its rewriting and expansion into a simpler form that is more amenable to translation into machine language.
In order to facilitate the use of the book, it is distributed in several formats: HyperText Markup Language (HTML), PostScript (PS), and Portable Document Format (PDF). The HyperText version is the recommended format because it is linked with the GNAT sources, what allows the reader to analyze additional details not discussed in this book. The other formats facilitate its printing.
The book is structured in four parts:
As explained above, the book does not discuss the implementation of the scanner and the parser, which are more conventional portions of any compiler. The interested reader will nevertheless find much elegant algorithms in those sections of the sources. The scanner is engineered to handle multiple character encodings, and the parser has what is considered to be the best set of error recovery strategies of any Ada compiler in use. We trust that compiler engineers will find a wealth of ideas in those sources.
The GNAT compiler is the product of several hundred person-years of work, starting with the NYU team that created the first validated Ada83 translator more than 20 years ago, and continuing today with the dedicated and enthusiastic members of Ada Core Technologies, and the myriad supportive users of GNAT whose suggestions keep improving the system. It is impractical to aknowledge all of the above by name, but we must express our very special thanks and admiration for Robert Dewar, chief architect, team leader, creator of some of the most interesting algorithms in GNAT, tireless enforcer of good programming practices, and an unsurpassable example of how to write impeccable software.
Part of this work has been developed under grant of the Spanish Government, reference code PR2002-0290.
Edmond Schonberg is professor and deputy Chair of the Department of Computer Science at New York University, and one of the founders of Ada Core Technologies. He has a PhD in Physics from The University of Chicago, and a BA in piano performance from the National Conservatory in Lima, Peru. His research interests are in programming languages, compilers, and optimization. He was part of the team that created Ada/Ed, the first complete translator for Ada83, and was one of the leaders of the GNAT project at New York University, that built the first prototype compiler for Ada95.
Javier Miranda studied Computer Science Engineering at the University of Las Palmas de Gran Canaria. He finished his studies on 1990 by implementing a Modula-2 compiler and went to the Technical University of Madrid to do his PhD under the direction of Angel Alvarez and Sergio Arévalo, on the design of an Ada extension for programming distributed systems. The experimental integration of this work into the GNAT compiler led him to become familiar with the internal details of the GNU Ada compiler. On 2003 he went to New York to collaborate with Edmond Schonberg on the writing of this book, which summarizes the experience achieved during these years. Currently his main line of research is the integration of the new Ada 2005 features into the GNAT compiler.