B. Teufel / S. Schmidt / T. Teufel C 2 Compiler Concepts Springer-Verlag Wien NewY ork Dr. Bernd Teufel ART Informationssysteme GmbH, Uberlingen Dr. Stephanie Schmidt Institut filr Informatik, Universitat Zurich, Prof. Dr. Thomas Teufel Arbeitsbereich Technische Informatik III, Technische Universitat Hamburg-Harburg This work is subjekt to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machines or similar means, and storage in data banks. © 1993 Springer-Verlag/Wien Printed on acid-free paper With 70 Figures ISBN-13: 978-3-211-82431-3 e-ISBN-13: 978-3-7091-9274-0 DOl: 10.1007/978-3-7091-9274-0 Preface Writing a compiler is a very good practice for learning how complex problems could be solved using methods from software engineering. It is extremely important to program rather carefully and exactly, because we have to remember that a compiler is a program which has to handle an input that is usually incorrect. Therefore, the compiler itself must be error-free. Referring to Niklaus Wirth, we postulate that the grammatical structure of a language must be reflected in the structure of the compiler. Thus, the complexity of a language determines the complexity of the compiler (cf. Compilerbau. B. G. Teubner Verlag, Stuttgart, 1986). This book is about the translation of programs written in a high level programming language into machine code. It deals with all the major aspects of compilation systems (including a lot of examples and exercises), and was outlined for a one session course on compilers. The book can be used both as a teacher's reference and as a student's text book. In contrast to some other books on that topic, this text is rather concentrated to the point. However, it treats all aspects which are necessary to understand how compilation systems will work. Chapter One gives an introductory survey of compilers. Different types of compilation systems are explained, a general compiler environment is shown, and the principle phases of a compiler are introduced in an informal way to sensitize the reader for the topic of compilers. Chapter Two may be thought of as the definition module of the text. Terminology for grammars and languages as well as basic analysing techniques are introduced. Finally, the definition of the programming language PUO is given - this language will be used in the following Chapters to explain particular methods. PUO was introduced by Niklaus Wirth as an example of a very simple programming vi language consisting of all important structures and features to exemplify and demonstrate the major compiler concepts. Since this language fulfils this purpose very good, we did neither choose another more complex language, such as PASCAL or MODULA-2, nor did we define our own language to have a medium for demonstration. Chapter Three is about lexical analysis and organization of symbol tables. Since finite automata are very convenient models for describing how the symbols of formal languages (generated by regular grammars, cf. Chapter 2) should be analyzed, an introduction to finite automata is given before scanners themselves are considered. Symbol tables as a compiler's central information structure are introduced and several forms for their organization are discussed. Finally, the code for lexical analysis of PUO is given. Chapter Four deals with parsers. The Chapter is subdivided according to the two p~incipal analyzing techniques: Top-down analysis and bottom-up analysis. The most efficient top-down and bottom-up parsers are based on context-free LL grammars and LR-grammars, respectively. Thus, those grammars are introduced before the parsing methods themselves are explained. Both analysing methods are introduced using simple examples. Finally, the code for a recursive descent parser for PUO is given. Chapter Five considers the semantic meaning of programs: Semantic and type analysis. Syntactical structures of a source code are semantically analyzed by interpreting the meaning of that source code, i.e. by generating an internal representation of the source code. Several forms of internal representations (intermediate codes) are discussed before techniques of syntax-directed translation and type checking are introduced. Finally, a code fragment for the generation of an intermediate code for PUO is given. Chapter Six is about error handling. Compilers are systems which in most cases have to deal with an incorrect input. Thus, error handling is an important part of a compiler. Possible errors are characterized and classified before error handling and recovery techniques for lexical and syntactical analysis are discussed. Finally, several techniques are exemplified considering again PUO. Chapter Seven is about code generation and code optimization. Storage allocation techniques (static, staCk, and heap allocation), parameter passing, as well as addressing methods are explained. Code generation is that part of a compiler which strongly depends on the target hardware. However, some basic steps are common to every code generation phase and, therefore, a general code generation algorithm is introduced. Finally, major optimization techniques are discussed. vii Chapter Eight concludes this book with a few remarks on the influences of hardware development on programming language and compiler design. A great number of Exercises is separately included to allow the reader to assess his understanding of the book's content. Acknowledgement We would like to thank Anke John for her numerous valuable comments. Her interest and encouragement in this book are appreciated greatly. Bernd Teufel Ulm Stephanie Schmidt ZOrich Thomas Teufel Hamburg Contents 1 General Remarks on Complier Theory ...................................................... 1 1.1 Types of Compilation Systems ..................................................................... 3 1.2 Compiler Environments ................................................................................. 4 1.3 Analysis and Synthesis ................................................................................. 6 2 Formal Aspects ...................................................................................................... 9 2.1 Backus-Naur Form (BNF) .............................................................................. 10 2.2 Formal Languages ............................................... ;. ........................................ 12 2.3 Analyzing Techniques ................................................................................... 22 2.4 Syntax Graphs ................................................................................................ 27 2.5 The Programming Language PUO .............................................................. 29 3 Lexical Analysis and Symbol Tables .......................................................... 32 3.1 Finite Automata ............................................................................................... 33 3.2 The Scanner .................................................................................................... 43 3.3 Symbol Tables ................................................................................................ 46 3.4 Lexical Analysis of PUO ................................................................................ 52 x 4 Syntax Analysis and Parser Construction ................................................ 57 4.1 ToP'lown Analysis ......................................................................................... 57 4.1.1 LL-grammars ....................................................................................... 57 4.1.2 Recursive Descent Strategy ............................................................. 64 4.1.3 Tabular Parsing .................................................................................. 73 4.2 Bottom-up Analysis ........................................................................................ 78 4.2.1 LR(k)-grammars ................................................................................. 78 4.2.2 Shift-Reduce Analysis ....................................................................... 80 4.2.3 LR-Parser ............................................................................................ 82 4.3 Recursive Descent Parser for PUO ............................................................. 93 5 Semantic and Type Analysis ........................................................................... 10 0 5.1 Intermediate Codes ........................................................................................ 101 5.2 Syntax-directed Translation .......................................................................... 105 5.3 Type Checking ................................................................................................ 111 5.4 Intermediate Code Generation for PUO ..................................................... 113 6 How to Handle Errors ......................................................................................... 118 6.1 Error Classification ......................................................................................... 119 6.2 Effects of Errors ............................................................................................... 122 6.3 Error Handling in Lexical Analysis .............................................................. 122 6.4 Error Handling in Syntax Analysis ............................................................... 124 6.5 Semantic Errors .............................................................................................. 125 6.6 PLIO Error Recovery ....................................................................................... 126 7 Code Generation and Optimization ............................................................ 130 7.1 Storage Allocation .......................................................................................... 131 7.1.1 Static Storage Allocation ................................................................... 132 7.1.2 Dynamic Storage Allocation ............................................................. 133 7.2 Parameter Passing ......................................................................................... 138 7.3 Variable Addressing ...................................................................................... 139 7.4 Code Generation ............................................................................................ 142 7.5 Code Optimization ......................................................................................... 147 xi 8 Impacts of Modern Hardware Developments .......................................... 153 8.1 Computer Architectures vs. Programming Languages ........................... 153 8.2 Instruction Sets and Microcode .................................................................... 154 8.3 RISC Architectures ......................................................................................... 157 Exercises ........................................................................................................................ 159 References ..................................................................................................................... 170 Index ................................................................................................................................. 173