gnat-book.pdf
Number of Pages: 268
GNAT: The GNU Ada Compiler
June, 2004 Copyright (C) Javier Miranda and Edmond Schonberg
jmiranda@iuma.ulpgc.es, schonberg@cs.nyu.edu
Applied Microelectronics Research Institute University of Las Palmas de Gran Canaria Canary Islands Spain Computer Science Department New York University U.S.A. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any latter published by the Free Software Foundation; with the Invariant Sections being “GNU General Public Documentation License”, the Front-Cover text being “GNAT: The GNU Ada Compiler”, and the Back-Cover text being “Copies published by the Free Software Foundation raise funds for GNU development.” ii Contents
I First Part: Introduction 7
1 The GNAT Project 9
1.1 GCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 The GNAT Compiler . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Compilation Model . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 Traditional Compilation Model . . . . . . . . . . . . . . 13 1.3.2 GNAT Compilation Model . . . . . . . . . . . . . . . . . 13 1.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Overview of the Front-end Architecture 19
2.1 The Scanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 The Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.1 The Abstract Syntax Tree . . . . . . . . . . . . . . . . . 22 2.3 The Semantic Analyzer . . . . . . . . . . . . . . . . . . . . . . . 24 2.4 The Expander . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Error Recovery 31
3.1 Scanner Error Recovery . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.1 Use of the Casing of Identifiers . . . . . . . . . . . . . . 32 iii iv
CONTENTS
3.2 Parser Error Recovery . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.1 The Parser Scope-Stack . . . . . . . . . . . . . . . . . . 33 3.2.2 Example 1: Use of indentation . . . . . . . . . . . . . . . 34 3.2.3 Example 2: Handling Semicolon Used in Place of ’is’ . . 34 3.2.4 Example 3: Handling ’is’ Used in Place of Semicolon . . 36 3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
II Second Part: Semantic Analysis 39
4 Scopes and Visibility 41
4.1 Flags and Data Structures . . . . . . . . . . . . . . . . . . . . . . 41 4.2 Analysis of Records, Tasks and Protected Types. . . . . . . . . . . 45 4.3 Analysis of Packages . . . . . . . . . . . . . . . . . . . . . . . . 46 4.4 Analysis of Private Types . . . . . . . . . . . . . . . . . . . . . . 47 4.4.1 Private Entities Visibility . . . . . . . . . . . . . . . . . . 48 4.4.2 Private Type Declarations . . . . . . . . . . . . . . . . . 49 4.4.3 Deferred Constants and Incomplete Types . . . . . . . . . 51 4.4.4 Limited Types . . . . . . . . . . . . . . . . . . . . . . . 51 4.4.5 Analysis of Child Units . . . . . . . . . . . . . . . . . . . 51 4.4.6 Analysis of Subunits . . . . . . . . . . . . . . . . . . . . 52 4.5 Name Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5 Overload Resolution 55
5.1 Resolution Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 56 5.1.1 Additional Details for the Bottom-Up Pass . . . . . . . . 57 CONTENTS v5.1.2 Data Structures . . . . . . . . . . . . . . . . . . . . . . . 59 5.1.3 Additional Details for the Top-Down Pass . . . . . . . . . 60 5.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6 Analysis of Discriminants 63
6.1 Analysis of Discriminants . . . . . . . . . . . . . . . . . . . . . . 64 6.2 Analysis of Discriminants in Derived Types . . . . . . . . . . . . 67 6.3 Discriminals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7 Generic Units 71
7.1 Generic Units . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.1.1 Analysis of Generic Units . . . . . . . . . . . . . . . . . 72 7.1.2 Instantiation of Generic Units . . . . . . . . . . . . . . . 75 7.1.3 Parameter Matching . . . . . . . . . . . . . . . . . . . . 75 7.1.4 Private Types . . . . . . . . . . . . . . . . . . . . . . . . 80 7.2 Nested Generic Units . . . . . . . . . . . . . . . . . . . . . . . . 80 7.2.1 Analysis of Nested Generic Units . . . . . . . . . . . . . 80 7.2.2 Instantiation of Nested Generic Units . . . . . . . . . . . 81 7.3 Generic Child Units . . . . . . . . . . . . . . . . . . . . . . . . . 84 7.3.1 Analysis of Generic Child Units . . . . . . . . . . . . . . 84 7.3.2 Instantiation of Child Generic Units . . . . . . . . . . . . 85 7.4 Delayed Instantiation of Bodies . . . . . . . . . . . . . . . . . . . 89 7.5 Detection of Instantiation Circularities . . . . . . . . . . . . . . . 90 7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
8 Freezing Analysis 93 vi
CONTENTS
8.1 Freezing Types and Subtypes . . . . . . . . . . . . . . . . . . . . 94 8.2 Freezing Expressions . . . . . . . . . . . . . . . . . . . . . . . . 95 8.3 Freezing Objects . . . . . . . . . . . . . . . . . . . . . . . . . . 96 8.4 Freezing Subprograms . . . . . . . . . . . . . . . . . . . . . . . 96 8.5 Freezing Packages . . . . . . . . . . . . . . . . . . . . . . . . . 97 8.6 Freezing Generic Units . . . . . . . . . . . . . . . . . . . . . . . 97 8.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
III Third Part: Expansion 99
9 Expansion of Tasks 101
9.1 Task Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 9.2 Task Termination . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.3 Task Abortion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.4 Expansion of Task Type Declarations . . . . . . . . . . . . . . . . 104 9.5 Task Body Expansion . . . . . . . . . . . . . . . . . . . . . . . . 105 9.6 Example of Task Expansion . . . . . . . . . . . . . . . . . . . . 106 9.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
10 Expansion of Rendezvous and related Constructs 109
10.1 Entry Identification . . . . . . . . . . . . . . . . . . . . . . . . . 110 10.2 Entry-Call Expansion . . . . . . . . . . . . . . . . . . . . . . . . 110 10.2.1 Expansion of Simple Entry-Calls . . . . . . . . . . . . . 112 10.2.2 Expansion of Conditional and Timed Entry-Calls . . . . . 112 10.3 Asynchronous Transfer of Control . . . . . . . . . . . . . . . . . 113 10.3.1 ATC Implementation Models . . . . . . . . . . . . . . . . 114 CONTENTS vii 10.3.2 Expansion of ATC . . . . . . . . . . . . . . . . . . . . . 116 10.4 Expansion of Accept Statements . . . . . . . . . . . . . . . . . . 117 10.4.1 Simple Accept Expansion . . . . . . . . . . . . . . . . . 117 10.4.2 Timed and Selective Accept . . . . . . . . . . . . . . . . 118 10.4.3 Count Attribute Expansion . . . . . . . . . . . . . . . . . 120 10.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
11 Expansion of Protected Objects 121
11.1 The Proxy Model . . . . . . . . . . . . . . . . . . . . . . . . . . 123 11.1.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . 124 11.2 Expansion of Protected Types . . . . . . . . . . . . . . . . . . . . 125 11.2.1 Expansion of Protected-Type Specification . . . . . . . . 125 11.2.2 Expansion of Protected Subprograms . . . . . . . . . . . 127 11.2.3 Expansion of Entry Barriers . . . . . . . . . . . . . . . . 129 11.2.4 Expansion of Entry bodies . . . . . . . . . . . . . . . . . 129 11.2.5 Table to Barriers and Entry-Bodies . . . . . . . . . . . . . 130 11.2.6 Expansion of Entry Families . . . . . . . . . . . . . . . . 130 11.3 Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 11.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
12 Expansion of Controlled-Types 133
12.1 Implementation Overview . . . . . . . . . . . . . . . . . . . . . 134 12.1.1 Exceptional Block Exit . . . . . . . . . . . . . . . . . . . 135 12.1.2 Finalization of Anonymous Objects . . . . . . . . . . . . 136 12.1.3 Finalization of Dynamically Allocated Objects . . . . . . 136 12.1.4 Problems Related to Mutable Objects . . . . . . . . . . . 137 12.1.5 Controlled Class-Wide Objects . . . . . . . . . . . . . . . 137 viii
CONTENTS
12.2 Expansion Activities for Controlled-Types . . . . . . . . . . . . . 138 12.2.1 Expansion of Assignment . . . . . . . . . . . . . . . . . 139 12.2.2 Expansion of Anonymous Controlled Objects . . . . . . . 140 12.2.3 Objects with Controlled Components . . . . . . . . . . . 141 12.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
13 Expansion of Tagged-Types 145
13.1 Tagged and Polymorphic Objects . . . . . . . . . . . . . . . . . . 146 13.2 The Dispatch Table . . . . . . . . . . . . . . . . . . . . . . . . . 147 13.3 Primitive Operations . . . . . . . . . . . . . . . . . . . . . . . . 149 13.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
IV Fourth Part: Run-Time 155
14 Tasking 157
14.1 The Ada Task Control Block . . . . . . . . . . . . . . . . . . . . 157 14.2 Task States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 14.3 Task Creation and Termination . . . . . . . . . . . . . . . . . . . 159 14.4 Run-Time Subprograms for Task Creation and Termination . . . . 163 14.4.1 GNARL.Enter Master . . . . . . . . . . . . . . . . . . . 165 14.4.2 GNARL.Create Task . . . . . . . . . . . . . . . . . . . . 165 14.4.3 GNARL.Activate Tasks . . . . . . . . . . . . . . . . . . 166 14.4.4 GNARL.Tasks Wrapper . . . . . . . . . . . . . . . . . . 168 14.4.5 GNARL.Complete Activation . . . . . . . . . . . . . . . 168 14.4.6 GNARL.Complete Task . . . . . . . . . . . . . . . . . . 169 14.4.7 GNARL.Complete Master . . . . . . . . . . . . . . . . . 169 CONTENTS ix 14.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
15 The Rendezvous 171
15.1 The Entry-Call Record . . . . . . . . . . . . . . . . . . . . . . . 172 15.2 Entries and Queues . . . . . . . . . . . . . . . . . . . . . . . . . 173 15.3 Accepted-Calls Stack . . . . . . . . . . . . . . . . . . . . . . . . 174 15.4 Selective Accept . . . . . . . . . . . . . . . . . . . . . . . . . . 174 15.5 Run-Time Rendezvous Subprograms . . . . . . . . . . . . . . . . 176 15.5.1 GNARL.Call Simple . . . . . . . . . . . . . . . . . . . . 176 15.5.2 GNARL.Call Synchronous . . . . . . . . . . . . . . . . . 176 15.5.3 GNARL.Task Do Or Queue . . . . . . . . . . . . . . . . 177 15.5.4 GNARL.Task Entry Call . . . . . . . . . . . . . . . . . . 177 15.5.5 GNARL.Accept Trivial . . . . . . . . . . . . . . . . . . 177 15.5.6 GNARL.Accept Call . . . . . . . . . . . . . . . . . . . . 178 15.5.7 GNARL.Complete Rendezvous . . . . . . . . . . . . . . 178 15.5.8 GNARL.Exceptional Complete Rendezvous . . . . . . . 178 15.5.9 GNARL.Selective Wait . . . . . . . . . . . . . . . . . . 179 15.5.10 GNARL.Task Count . . . . . . . . . . . . . . . . . . . . 180 15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
16 Protected Objects 181
16.1 The Lock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 16.2 Run-Time Subprograms . . . . . . . . . . . . . . . . . . . . . . . 182 16.2.1 GNARL.Protected Entry Call . . . . . . . . . . . . . . . 182 16.2.2 GNARL.PO Do Or Queue . . . . . . . . . . . . . . . . . 183 16.2.3 GNARL.Service Entries . . . . . . . . . . . . . . . . . . 184 16.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 x
CONTENTS
17 Time and Clocks 187
17.1 Delay and Delay Until Statements . . . . . . . . . . . . . . . . . 187 17.2 Timed Entry Call . . . . . . . . . . . . . . . . . . . . . . . . . . 189 17.3 Timed Selective Accept . . . . . . . . . . . . . . . . . . . . . . . 190 17.4 Run-Time Subprograms . . . . . . . . . . . . . . . . . . . . . . . 190 17.4.1 GNARL.Timed Delay . . . . . . . . . . . . . . . . . . . 190 17.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
18 Exceptions 193
18.1 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 18.1.1 Exception Id . . . . . . . . . . . . . . . . . . . . . . . . 193 18.1.2 The Exceptions Table . . . . . . . . . . . . . . . . . . . . 194 18.2 Run-Time Subprograms . . . . . . . . . . . . . . . . . . . . . . . 195 18.2.1 GNARL.Raise . . . . . . . . . . . . . . . . . . . . . . . 195 18.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
19 Interrupts 197
19.1 POSIX Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 19.1.1 Reserved Signals . . . . . . . . . . . . . . . . . . . . . . 199 19.2 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 19.2.1 Interrupts Manager: Basic Approach . . . . . . . . . . . . 202 19.2.2 Server Tasks: Basic Approach . . . . . . . . . . . . . . . 203 19.2.3 Interrupt-Manager and Server-Tasks Integration . . . . . . 203 19.3 Run-Time Subprograms . . . . . . . . . . . . . . . . . . . . . . . 207 19.3.1 GNARL.Install Handlers . . . . . . . . . . . . . . . . . . 207 19.3.2 GNARL.Attach Handlers . . . . . . . . . . . . . . . . . 207 19.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 CONTENTS xi
20 Abortion 211
20.1 Run-Time Subprograms . . . . . . . . . . . . . . . . . . . . . . . 214 20.1.1 GNARL.Task Entry Call . . . . . . . . . . . . . . . . . . 215 20.1.2 GNARL.Locked Abort To Level . . . . . . . . . . . . . 215 20.1.3 GNARL.Locked Abort To Level . . . . . . . . . . . . . 215 20.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
V Fifth Part: Appendix 219
A How to add new Keywords, Pragmas and Attributes 221
A.1 Drago . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 A.2 First Step: Addition of new Keywords . . . . . . . . . . . . . . . 222 A.3 Second step: Addition of new tokens . . . . . . . . . . . . . . . . 223 A.4 Third Step: Update the Scanner Initialization . . . . . . . . . . . 224 A.5 Addition of Pragmas an Attributes . . . . . . . . . . . . . . . . . 225 A.6 Addition of New Syntax Rules . . . . . . . . . . . . . . . . . . . 225 A.6.1 First step: Addition of New Node Kinds . . . . . . . . . . 226 A.6.2 Second Step: High-level specification of the new nodes . . 227 A.6.3 Third Step: Automatic modification of the frontend . . . . 228 A.6.4 Fourth Step: Update of the Parser . . . . . . . . . . . . . 228 A.7 Verification of the Semantics . . . . . . . . . . . . . . . . . . . . 229 A.8 Tree expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 A.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
B Glossary 231 C GNU Free Documentation License 237 xii
CONTENTS
1. APPLICABILITY AND DEFINITIONS . . . . . . . . . . . . . . . 238 2. VERBATIM COPYING . . . . . . . . . . . . . . . . . . . . . . . . 239 3. COPYING IN QUANTITY . . . . . . . . . . . . . . . . . . . . . . 240 4. MODIFICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 5. COMBINING DOCUMENTS . . . . . . . . . . . . . . . . . . . . . 243 6. COLLECTIONS OF DOCUMENTS . . . . . . . . . . . . . . . . . 243 7. AGGREGATION WITH INDEPENDENT WORKS . . . . . . . . . 244 8. TRANSLATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 9. TERMINATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 10. FUTURE REVISIONS OF THIS LICENSE . . . . . . . . . . . . . 245 ADDENDUM: How to use this License for your documents . . . . . . 245 List of Figures
1.1 GNAT Compiler. . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 GNAT Front-End Phases. . . . . . . . . . . . . . . . . . . . . . . 12 1.3 GNAT Overall Structure. . . . . . . . . . . . . . . . . . . . . . . 14 2.1 Architecture of the GNAT Scanner . . . . . . . . . . . . . . . . . 20 2.2 Structure of the GNAT Parser . . . . . . . . . . . . . . . . . . . . 21 2.3 Abstract Syntax Tree Construction. . . . . . . . . . . . . . . . . . 22 2.4 Abstract Syntax Tree Packages. . . . . . . . . . . . . . . . . . . . 23 2.5 Abstract Syntax Subtree associated with the package body rule. . . 24 2.6 Abstract Syntax Tree Decoration. . . . . . . . . . . . . . . . . . . 24 2.7 Structure of the Semantic Analyzer. . . . . . . . . . . . . . . . . 25 2.8 Abstract Syntax Tree Nodes Dispatching. . . . . . . . . . . . . . 26 2.9 Abstract Syntax Tree Expansion. . . . . . . . . . . . . . . . . . . 27 2.10 Architecture of the GNAT Expander . . . . . . . . . . . . . . . . 28 4.1 The Scope Stack . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2 List of entities in the same scope. . . . . . . . . . . . . . . . . . . 43 4.3 Lists of homonym entities. . . . . . . . . . . . . . . . . . . . . . 44 4.4 The matrix of entities. . . . . . . . . . . . . . . . . . . . . . . . . 45 4.5 Analysis of a record. . . . . . . . . . . . . . . . . . . . . . . . . 46 xiii xiv
LIST OF FIGURES
4.6 Analysis of a protected type. . . . . . . . . . . . . . . . . . . . . 47 4.7 Visible and Private Entities . . . . . . . . . . . . . . . . . . . . . 49 4.8 Reference to the Full-View Entity . . . . . . . . . . . . . . . . . 50 4.9 Swapping of the Private Declaration and the Full View . . . . . . 50 4.10 Deferred Constants Handling . . . . . . . . . . . . . . . . . . . . 51 7.1 Step 1: Copy the original generic AST. . . . . . . . . . . . . . . . 73 7.2 Step 2: Analyze and decorate the copy. . . . . . . . . . . . . . . . 74 7.3 Step 3: Remove local references in the original AST. . . . . . . . 74 7.4 Instantiation of generic units. . . . . . . . . . . . . . . . . . . . . 75 7.5 Nested generic packages. . . . . . . . . . . . . . . . . . . . . . . 81 7.6 Analysis of generic package Gen Pkg 1. . . . . . . . . . . . . . . 82 7.7 Analysis of nested generic package Gen Pkg 2. . . . . . . . . . . 83 7.8 Saving global references. . . . . . . . . . . . . . . . . . . . . . . 83 7.9 Instantiation of nested generic units. . . . . . . . . . . . . . . . . 84 7.10 Sequence of steps to instantiate Child Instance . . . . . . . . . . . 88 10.1 Data structures associated to an entry-call. . . . . . . . . . . . . . 111 11.1 Proxy Model: Call-Back Implementation. . . . . . . . . . . . . . 125 11.2 Proxy Model: In-Line Implementation. . . . . . . . . . . . . . . . 125 13.1 Dispatch Table Example. . . . . . . . . . . . . . . . . . . . . . . 148 14.1 Run-Time Information Associated with Each Task. . . . . . . . . 158 14.2 Definition of Parent, Activator, Master of Task and Master Within. 161 14.3 GNARL Subprograms Called During the Task Life-Cycle . . . . . 163 15.1 Data structures associated to an entry-call. . . . . . . . . . . . . . 172 LIST OF FIGURES xv 15.2 Entry Queues. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 15.3 Simple Accept. . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 16.1 Graphical Representation of the Protected Object. . . . . . . . . . 183 17.1 GNARL Subprograms for the Delay Statement. . . . . . . . . . . 188 17.2 GNARL Subprograms for the Delay Statement in an Ada Program without Tasks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 17.3 GNARL Subprograms for the Delay Statement in an Ada Program with Tasks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 17.4 GNARL Subprograms for Timed Entry Call. . . . . . . . . . . . . 190 17.5 GNARL Subprograms for Timed Selective Accept. . . . . . . . . 191 18.1 Exception Identifier Record . . . . . . . . . . . . . . . . . . . . . 194 18.2 Occurrence Identifier. . . . . . . . . . . . . . . . . . . . . . . . . 195 18.3 Hash Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 19.1 Reserved Interrupts Table. . . . . . . . . . . . . . . . . . . . . . 201 19.2 Table of User-Defined Interrupt-Handlers. . . . . . . . . . . . . . 202 19.3 Basic Automaton Implemented by the Interrupts Manager . . . . . 203 19.4 Server Tasks Signal Handling. . . . . . . . . . . . . . . . . . . . 204 19.5 Basic Automaton Implemented by the Server Tasks. . . . . . . . . 205 19.6 Simplified Server Tasks Automaton. . . . . . . . . . . . . . . . . 206 19.7 Server Tasks Automaton. . . . . . . . . . . . . . . . . . . . . . . 206 19.8 List of Interrupt Handlers in Non-Nested Style. . . . . . . . . . . 208 20.1 GNARL Subprograms for the Abort Statement. . . . . . . . . . . 214 20.2 Entry Calls Stack. . . . . . . . . . . . . . . . . . . . . . . . . . . 216 A.1 GNAT utility programs. . . . . . . . . . . . . . . . . . . . . . . . 228 xvi
LIST OF FIGURES
A.2 New parser structure. . . . . . . . . . . . . . . . . . . . . . . . . 229 A.3 GNAT semantic utility program . . . . . . . . . . . . . . . . . . 229 Preface
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 main-tenance 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 con-tinues 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 daunt-ing 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. 12
Preface
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.
Audience
The book should be of interest to software practitioners interested in compiler technology, language experts who want to examine the implementation of com-plex 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 sys-tem, 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 concur-rency, 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 Preface 3senior course in Programming Languages. We have included brief descriptions of the more interesting constructs in the language, to motivate the issues of im-plementation 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.
Use of this Book
In order to facilitate the use of the book, it is distributed in several formats: Hyper-Text 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.
Structure of the Book
The book is structured in four parts:
>
Part I: Introduction . The three chapters in this part present an overview of the GNAT compilation system, the architecture of the front-end, the data-structures used in the abstract representation of a program, and the error diagnostic and recovery techniques implemented in the GNAT parser and semantic analyzer.
>
Part II: Semantic Analysis . Here we discuss the implementation strategies for the more interesting and complex aspects of the language, from the point of view of their translation into a low-level target independent representa-tion. The topics include the analysis of scope and visibility, type checking and overloading, discriminants, generics, and freezing rules.
>
Part III: Expansion . This part describes the first step in the synthesis of an object program, namely the transformation of the first target-independent representation into a simpler one, whose semantic level is close to that of C and which is therefore easier to translate into machine language. The complexity of this phase is a reflection of the richness of modern program-ming languages. Constructs that present interesting expansion challenges, 4
Preface
and which we discuss at length, include aggregates, tagged types, controlled types, protected objects, tasks, and everything having to do with intertask communication.
>
Part IV: The Run-Time . In this part, we discuss the structure of the run-time system. We discuss the following in some detail: tasking (creation, activation, termination, abortion), rendezvous, protected objects, clocks and delay statements, exceptions, interrupts, and finally asynchronous transfer of control.
>
Part V: Appendix . This appendix describes how to modify the GNAT front-end to implement language extensions. We sketch the techniques nec-essary to add keywords, pragmas, attributes, and new constructs to the lan-guage. As explained above, the book does not discuss the implementation of the scan-ner 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.
Acknowledgements
The GNAT compiler is the product of several hundred person-years of work, start-ing 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 sug-gestions 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 interest-ing 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. Preface 5
Short Biography
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 Technolo-gies. 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 inter-ests 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´ evalo, 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 ex-perience achieved during these years. Currently his main line of research is the integration of the new Ada 2005 features into the GNAT compiler. New York and the Canary Islands, June, 2004 6
Preface Part I First Part: Introduction
> 7
Chapter 1 The GNAT Project
GNAT is an acronym for GNU Ada Translator; a Front-End and Run-Time system for Ada 95 that uses the GCC back-end as a retargettable code generator, and is distributed according to the guidelines of the Free Software Foundation . GNAT was initially developed by two cooperating teams:
>
New York University Team . This group, led by Prof. Robert B.K. Dewar, and Edmond Schonberg was responsible for the development of the front-end of the compiler.
>
Florida State University Team . This group, also known as the POSIX Ada Real-Time Team, was led by Prof. Theodore P. Baker, and was responsible for the first design of the concurrency components of the run-time library. The NYU project was sponsored by the U.S. government from 1991 to 1994. In August, 1994 the members of the NYU team created the company Ada Core Technologies, Inc. , which provides technical support to industrial users of GNAT and has transformed GNAT into an industrial-strength, full-featured compiler: GNAT Pro). This compiler includes a modern tool suite and environment for the development of Ada-based software (i.e. GPS). Nowadays Ada Core continues investing resources to port GNAT to new architectures and operating systems, and has an active participation in the new revision of Ada (Ada 2005). Ada Core pe-riodically makes available public versions of the compiler to the Ada community at large. This chapter introduces the main components of GNAT. It is structured as fol-lows: Section 1.1 briefly introduces GCC; Section 1.2 presents the main compo-910
CHAPTER 1. THE GNAT PROJECT
nents of the GNAT compiler. Finally, Section 1.3 gives an overview of the GNAT compilation model.
1.1 GCC
GCC [Sta04] is the compiler system of the GNU environment. GNU (a self-referential acronym for ’GNU is Not Unix’) is a Unix-compatible operating sys-tem, being developed by the Free Software Foundation, and distributed under the GNU Public License (GPL). GNU software is always distributed with its sources, and the GPL enjoins anyone who modifies GNU software and redistributes the modified product to supply the sources for the modifications as well. Thus, en-hancements to the original software benefit the software community at large. GCC is the centerpiece of the GNU software. It is a compiler system with multiple front-ends and a large number of hardware targets. Originally designed as a compiler for C, it now includes front-ends for C ++ , Objective-C, Ada, For-tran, Java, and treelang. Technically, the crucial asset of the GCC is its mostly language-independent and target-independent code generator, which produces ex-cellent quality-code both for CISC and RISC machines. Remarkably, the machine dependences of the code generator represent less than 10% of the total code. To add a new target to GCC, an algebraic description of each machine instruction must be given using a Register-Transfer Language (RTL). Most of the code gen-eration and optimization then uses the RTL, which GCC maps when necessary into the target machine language. Furthermore, GCC produces high-quality code, comparable to that of the best commercial compilers.
1.2 The GNAT Compiler
The first decision involved choosing the language in which GNAT compiler should be written. GCC is fully written in C, but for technical reasons, as well as non-technical ones, it was inconceivable to use anything but Ada for GNAT itself. In fact, the definition of the Ada language depends heavily on hierarchical libraries, and cannot be given except in Ada 95, so that it is natural for the compiler and the environment to use child units throughout. The GNAT team started using a relatively small subset of Ada83, and in typi-cal fashion, extended the subset whenever new features became implemented. Six months after the coding started in earnest, they were able to bootstrap the com-1.2. THE GNAT COMPILER 11 piler, and abandon the commercial compiler they had been using up to that point. As soon as more Ada95 features were implemented, they were able to write GNAT in Ada95. The GNAT compiler is composed of two main parts: the Front-End and the
Back-End (cf. Figure 1.1). The front-end of is written in Ada 95, and the back-end is the GCC back-end extended to meet the needs of Ada semantics (i.e. exceptions support).
> Source (Ada) > Front-End > (GNAT) > Back-End > (GCC) > Object (.o) > Compiler
Figure 1.1: GNAT Compiler. The front-end comprises five phases (cf. Figure 1.2): Lexical Analysis (Scan-ning), Syntax Analysis (parsing), Semantic Analysis, Expansion, and GIGI phases. The scanner analyzes the input characters and generates the associated Tokens .The parser verifies the syntax of the tokens and creates the Abstract Syntax Tree (AST). The semantic analyzer performs all static legality checks on the program and decorates the AST with semantic attributes. The expander transforms high-level AST nodes (nodes representing tasks, protected objects, etc.) into equivalent AST fragments built with lower-level abstraction nodes and, if required, calls to Ada Run-Time library routines. 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 (see the backward ar-row from the expander to the semantic analyzer). At the end of this process the
GIGI phase transforms the AST into a tree which is read by the GCC back-end (GNAT to GNU transformation phase). This phase is really an interface between the GNAT front-end and the GCC back-end. In order to bridge the semantic gap between Ada and C, several GCC code generation routines have been extended, and others added, so that the burden of translation is also assumed by GIGI and GCC whenever it is 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 genera-tor is extended only when the extension is likely to be of benefit to more than one language. 12
CHAPTER 1. THE GNAT PROJECT
> code > (Ada) (Ada) (Ada) (Ada) > GCC tree fragments > (C) GiGi Scanner Parser Semantic Analyzer > Decorated tree > Expander > Expanded and decorated tree > back-end GCC > Source Syntax tree
Figure 1.2: GNAT Front-End Phases. All these phases communicate by means of a 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. It is worth men-tioning that strictly speaking GNAT does not use a symbol table. Rather, all se-mantic information concerning program entities is stored in defining occurrences of these entities directly in the AST. There is a further unusual recursive aspect to the structure of GNAT. The pro-gram library (described in the next section) does not hold any intermediate rep-resentation of compiled units. As a result, if the expander generates a call to a Run-Time Library routine, the compiler requires the specification of the corre-sponding Run-Time package to be analyzed as well (see the backward arrow from the expander to the parser).
1.3 Compilation Model
The notion of program library is one of the fundamental contributions of Ada to software engineering. The library guarantees that type safety is maintained across compilations, and prevents the construction of inconsistent systems by excluding obsolete units. In most Ada compilers, the library is a complex structure that holds intermediate representations of compiled units, information about depen-dences between compiled units, symbol tables, etc. GNAT has chosen a different approach: the separate files that constitute the program are separately compiled, and each compilation produces a corresponding object file. These object files are then linked together by specifying a list of object files in a program. Thus, the 1.3. COMPILATION MODEL 13 Ada library consists of a set of such object files (there is no library file as such). In the following sections we briefly present both alternatives.
1.3.1 Traditional Compilation Model
In the traditional model, an Ada library is a data structure that gathers the results of a set of compilations of Ada source files. A compilation is performed in the context of such a library, and the information in the library is used to enforce type consistency between separately compiled modules. Unlike some other language environments, all such type checking is performed at compile time, and Ada guar-antees at the language level that separately compiled modules of a complete Ada program are type consistent. In this model, building an Ada program consists of selecting a main program (a parameterless procedure compiled into the Ada library), and all the modules on which this main program depends, and bound them into a single executable program. A definite order of compilation is enforced by the language semantics and implemented by means of the Ada library. Basically, before a compilation unit is compiled, the specification of all the units on which it depends must be compiled first. This gives the Ada compiler a fair amount of freedom in the compilation order. An important consequence of this model is the notion of obsolete unit. If a unit is recompiled, then units which depend on it become obsolete, and must be recompiled. Again, the Ada library is the data structure used to implement this requirement. In the Ada Reference Manual [AAR95, Chapter 10], there are specific refer-ences to a Library File , and this is often taken to mean that the Ada Library should be represented using a file in the normal sense. Most Ada systems do in fact im-plement the Ada library in this manner. However, it is generally recognized that the Ada Reference Manual does not require this implementation approach. In this view, an Ada library is a conceptual entity that can be implemented in any manner that supports the required semantics. In fact the monolithic library approach is ill-adapted to multi-language systems, and has been responsible for some of the awkwardness of interfacing Ada to other languages.
1.3.2 GNAT Compilation Model
GNAT has chosen a completely different approach: sources are independently compiled to produce a set of objects, and the set of object files thus produced is 14
CHAPTER 1. THE GNAT PROJECT
submitted to the binder/linker to generate the resulting executable (cf. Figure 1.3). This approach removes all order of compilation considerations, and eliminates the traditional monolithic library structure. The library itself is implicit, and object files depend only on the sources used to compile them, and not on other objects. There are no intermediate representations of compiled units, so that unit decla-rations appearing in context clauses of a given compilation are always analyzed anew. Dependency information is kept directly in the object files (in fact, they are kept in a small separate file, conceptually linked to the object file), and amounts to a few hundred bytes per unit.
> Source (Ada) > Compiler > (GNAT)
Run Time System
> (GNARL) > Object code > Object code > Object code
Binder
> (GNAT) Linker Executable
Figure 1.3: GNAT Overall Structure. Given the speed of the GNAT front-end, this approach is no less efficient than the conventional library mechanism, and has the following advantages over it: 1. The compilation of an Ada unit is identical to the compilation of a module or file in another language: the result of the compilation of one source is one object file. 2. Given that inlining is always done from the source, there is no requirement that the entities to be inlined should be compiled first. It is even possible for two bodies to inline functions defined in each other, without fear of cir-cularities. Thus inlining works in a much more flexible way than in normal Ada compilers. 3. The standard system utilities to copy, rename and remove files can be re-used to copy, rename and remove object modules. 4. Since GNAT uses the same compilation model as other languages, it is also much easier to build programs where various parts of the program are built 1.3. COMPILATION MODEL 15 in different languages. Furthermore, GCC is committed to common system standard conventions for calling sequences, object module formats, includ-ing debugging information, and data structure layouts, so it is also easy to integrate Ada with any language supported by GCC. GNAT even makes possible to write multi-language programs whose main program is not itself written in Ada. 5. It is more compatible with conventional configuration management tools than the conventional library structure (tools ranging from the simple UNIX
make program to sophisticated compilation management environments). In the GNAT model, a source file contains a single compilation unit, and a compilation is represented as a series of source files, each of which contains one compilation unit. Furthermore there is a direct mapping from unit names to file names, so that from a unit name one can always determine the name of the file that contains the source for that unit. The default file naming convention is as follows: (1) The file name is the expanded name of the unit, with dots replaced by minus sign, (2) The extension “.ads” is used for specifications, and the extension “.adb” for bodies. Only the body produces an object file, so the fact that the spec-ification and body have the same file name does not cause difficulties. The object file conceptually contains the Ada Library Information for that source (extension “.ali”) whose most important component is a recording of the time stamps of the compilation units on which a compiled unit depends. In this model the compilation of a source file may require other source files. These include: 1. The corresponding specification for a body. 2. The parent specification of a child library spec. 3. Specifications of with’ed units. 4. Parent body for a subunit. 5. Bodies of inlined subprograms. 6. Bodies of instantiated generics. The key understanding is that in GNAT, dependencies are not established from one compilation unit to another, but from object files to corresponding source files. In this context GNAT is re-interpreting the Ada “order of compilation” rules to be 16
CHAPTER 1. THE GNAT PROJECT
“dependency on source files” rules. The rules regarding compilations that obsolete other compilations are similarly reinterpreted. For example, a rule that says: The body of package cannot be compiled until its specification has been compiled , is re-interpreted to mean: The body of package cannot be compiled unless the source of its specification is available . One interesting consequence of this approach is that if all the sources of a program are available, there are in fact no restrictions on the order of compilation. This feature facilitates the parallel compilation of Ada programs. The main argument against the GNAT model is that the compiler is constantly recompiling the specification of with’ed units. However, the alternative is not better. In traditional Ada library-based systems, the result of a compilation is to place information, typically some kind of intermediate tree, in the library. A subsequent with clause then fetches this tree from the library. In practice, this tree information can be huge, often much bigger than the source. Furthermore, it is generally a complex interlinked data structure. Thus it is not clear that re-reading and recompiling the source is less efficient than writing and reading back in these trees. It’s true that recompiling means redoing syntax and semantic checking, but this causes less Input/Output than reading and writing linked structures. On the contrary, the GNAT model gives all the previously discussed advantages.
The Binder
Ada establishes the rules which determine valid orders of elaboration [AAR95, Section 10.2]. It is also possible to construct programs for which no possible order of elaboration exists. Such programs are illegal, and must be diagnosed prior to execution. Because this work can not be established until all the object files are available, GNAT needs an special pre-linker (the binder ) which establishes a valid sequence of calls to the initialization procedures for specifications and bodies (cf. Figure 1.3). Part of the processing in the GNAT binder ascertains that the program is con-sistent by looking at time stamps in the ALI files associated with the compilation units required for the program. The binder consistency checks can be done in one of three modes: 1. From ALI files only. 2. From ALI files and any corresponding sources that can be located. 3. From ALI files and all corresponding sources, which must be available. 1.4. SUMMARY 17 Despite the clear advantages of operating in “source file” mode (second and third alternative), it is more useful for the GNAT binder to operate in “ali files only” mode. Not only is this mode faster, since no source files need to be accessed, but more importantly, it means that GNAT programs can be linked from objects even if the sources are not available. This is indispensable when linking libraries that for proprietary reasons may be distributed without the sources for their bodies. Therefore it is the mode implemented in the GNAT Binder.
1.4 Summary
This introductory chapter has presented the overall structure of the GNAT project. The compiler has two main parts: the front-end and the back-end . The front-end
comprises five phases which communicate by means of an Abstract Syntax Tree .The back-end is the GCC target independent code generator, what gives two main advantages: portability and excellent-quality code generation. The most novel aspect of the GNAT architecture is the source-based organi-zation of the library. In most Ada compilers the library is a monolithic complex structure that holds intermediate representations of compiled units. GNAT library model follows the traditional model used by nearly all languages throughout the entire history of programming languages: there is no centralized library, a source file contains a single compilation unit, and a compilation specifies a source file and generates a single object file. This model is fully conformant with the prescribed semantics given in the Ada Reference Manual and, at the same time, enables the use of many well-known configuration management tools (i.e. UNIX make), sim-plifies the construction of multi-language programs, and allows the parallel com-pilation of the Ada programs. Because the Ada language gives the rules which govern the order of elaboration of the compilation units the GNAT model needs a special pre-linker (the binder) which verifies the object files and generates a valid order of elaboration. 18
CHAPTER 1. THE GNAT PROJECT Chapter 2 Overview of the Front-end Architecture
The GNAT front-end comprises four phases that communicate by means of a com-pact Abstract Syntax Tree (AST): lexical analysis, syntax analysis, semantic anal-ysis, and expansion. This chapter provides an overview of the architecture of these phases. It is structured as follows: Section 2.1 presents the scanner architecture; Section 2.2 gives an overview of the parser, describes the high-level specification of the AST nodes and presents the mechanisms used to resynchronize it in case of syntax errors; Section 2.3 describes the architecture of the semantic analyzer, and finally Section 2.4 discusses the architecture of the expander.
2.1 The Scanner
For efficiency reasons no automatic tool was used to generate the GNAT scanner. It is a subprogram of the parser that reads input characters, identifies the next token, and returns it to the parser. To give support to various operating systems and to multiple languages, it is engineered to handle multiple character encodings (cf. Package Csets ). Figure 2.1 presents its architecture: package Scn has most of the implementation of the scanner; package Scans contains the Tokens definition and the state of the automaton. Finally, package Snames has the standard names (Ada keywords, pragmas and attributes). Low level package Namet handles name storage and look up, and package Opt has the global flags set by command-line switches and referenced throughout the compiler. 19 20
CHAPTER 2. OVERVIEW OF THE FRONT-END ARCHITECTURE
> Source File > Lexical Analyzer > scn scans > snames token > Syntax Analyzer > namet opt > High Level Low Level > Next_Token
Figure 2.1: Architecture of the GNAT Scanner
2.2 The Parser
The GNAT parser is a hand-coded recursive descent parser. The main reasons which justify this choice (rather than the traditional academic choice of a table-driven parser generated by a tool) were [CGS94, Section 3.2]:
>
Better error messages . GNAT generates clear and precise error messages. Even in case of serious structural errors, including the interchange of “;” and “is” between specification and body of a subprogram, the parser posts a precise and intelligible message. Bottom-up parsers have serious difficulties with such errors.
>
Clarity . The GNAT parser follows faithfully the grammar given in the Ada Reference Manual [AAR95]. This has clear pedagogical advantages be-cause the parser can be easily read in conjunction with the ARM, and makes it easier to maintain, for example to add new error recovery techniques. The Ada grammar given the ARM is ambiguous, and a table-driven parser would be forced to modify the grammar to make it acceptable to LL (1) or LALR (1) techniques. No such problem arises for a recursive descent parser, be-cause when necessary the parser can perform arbitrary look-ahead.
>
Performance . The GNAT parser is as fast as any Ada table driven parser, and arguably faster than a LALR parser. In most of the cases the parser is guided by the next token provided by the scanner. However, when dealing with ambiguous syntax rules the parser saves the state of the scanner, and issues repeated calls to look-ahead the following tokens and thus resolve the ambiguity (cf. Save Scan State and Restore Scan State in package Scans ). 2.2. THE PARSER 21 In addition to syntax verification, the GNAT parser builds the Abstract Syntax Tree (AST), that is to say the structured representation of the source program. This tree is subsequently used by the semantic analyzer to perform all the static checks on the program, that is to say all the context-sensitive legality rules of the language. At the architectural level the main subprogram of the GNAT parser is an Ada function ( Par ) that is called to analyze each compilation unit. The parser code is organized as a set of packages (subunits of the top-level function) each of which contains the parsing routines associated with one chapter of the Ada Reference Manual [AAR95]. For example, package Par.Ch2 contains all the parsing sub-programs associated with the second chapter of the Ada Reference Manual (cf. Figure 2.2). In addition, the name of the parsing subprograms follow a fixed rule: Prefix “ P ” followed by the name of the corresponding Ada syntax rule (for ex-ample, P Compilation Unit ).
> Ch2 Par > . . . . . > Endh Sync Tchk Labl Load Util > Ch3 Ch13
Figure 2.2: Structure of the GNAT Parser The GNAT Parser also has several additional sub-units: Package Endh , con-tains subprograms to analyze the finalization of the syntax scopes; package Sync ,contains subprograms to resynchronize the parser after syntax errors (cf. Chap-ter 3); package Tchk , contains subprograms that simplify the verification of to-kens; procedure Labl handles implicit label declarations; procedure Load