The compiler is composed of two main parts: the front-end and the back-end (cf. Figure ). The front-end of the GNAT compiler is thus written in Ada95. The back-end of the compiler is the back-end of GCC proper, extended to meet the needs of Ada semantics [SGC94, Section 3.1].
The front-end comprises five phases (cf. Figure ): lexical analysis, syntactic analysis (parsing), semantic analysis, AST expansion, and finally AST transformation into an equivalent C tree (this stage is labeled GiGi (GNAT to GNU transformation). These phases communicate by means of a rather compact Abstract Syntax Tree (AST). The implementation details of the AST are hidden by several procedural interfaces that provide access to syntactic and semantic attributes. The layering of the system, and the various levels of abstraction, are the obvious benefits of writing in Ada, in what one might call ``proper'' Ada style. It is worth mentioning that strictly speaking GNAT does not use a symbol table. Rather, all semantic information concerning program entities is stored in defining occurrences of these entities directly in the AST [SGC94, Section 3.1].
As the figure shows, the Scanner starts analyzes the input file and generates the associated Tokens. The Parser analyzes the syntax of the tokens and creates the Abstract Syntax Tree (syntactic analysis). The Semantic Analyzer performs name and type resolution (that is, it resolves all the possible ambiguities of the source code), decorates the AST with various semantic attributes, and as by-product performs all static legality checks on the program. After that, the Expander transforms high level AST nodes (nodes representing tasks, protected objects, etc.) into nodes which call to Ada Run-Time library routines. (Multi-tasking constructs are generally implemented by a combination of high-level source code transformations and calls to Ada Run-Time Library [DIB94, Section 4.2.1]).
Most of the expander activity results in the construction of additional AST fragments. Given that code generation requires that such fragments carry all semantic attributes, every expansion activity must be followed by additional semantic processing on the generated tree. This recursive structure is carried further: some predefined operations (i.e. exponentiation) are defined by means of a generic procedure. The expansion of the operation results in the generic instantiation (and corresponding analysis) of this generic procedure [SGC94, Section 3.3]. At the end of this process the GIGI phase transforms the AST into a tree understable by the GCC backend. This phase is an interface between the GNAT front-end and the GCC back-end. In order to bridge the semantic gap between Ada and C, several code generation routines in GCC have been extended, and others added, so that the burden of translation is also assumed by Gigi and GCC whenever it would be awkward or inefficient to perform the expansion in the front-end. For example, there are code generation actions for exceptions, variant parts and accesses to unconstrained types. As a matter of GCC policy, the code generator is extended only when the extension is likely to be of benefit to more than one language [SGC94, Section 3.4].
There is a further unusual recursive aspect to the structure of GNAT. The program library (described in greater detail below) does not hold any intermediate representation of compiled units. As a result, package declarations are analyzed whenever they appear in a context clause. Furthermore, if a generic unit, or an inlined unit G, is defined in a package P, then the instantiation or inlining of G in the current compilation requires that the body of P be analyzed as well. Thus the library manager, the parser and the semantic analyzer can be activated from within semantic analysis (note the backward arrows in figure ) [SGC94, Section 3.3].