Introduction to Compiler Design (Undergraduate Topics in Computer Science)
Format: PDF / Kindle (mobi) / ePub
This textbook is intended for an introductory course on Compiler Design, suitable for use in an undergraduate programme in computer science or related fields.
Introduction to Compiler Design presents techniques for making realistic, though non-optimizing compilers for simple programming languages using methods that are close to those used in "real" compilers, albeit slightly simplified in places for presentation purposes. All phases required for translating a high-level language to machine language is covered, including lexing, parsing, intermediate-code generation, machine-code generation and register allocation. Interpretation is covered briefly.
Aiming to be neutral with respect to implementation languages, algorithms are presented in pseudo-code rather than in any specific programming language, and suggestions for implementation in several different language flavors are in many cases given. The techniques are illustrated with examples and exercises.
The author has taught Compiler Design at the University of Copenhagen for over a decade, and the book is based on material used in the undergraduate Compiler Design course there.
Additional material for use with this book, including solutions to
selected exercises, is available at http://www.diku.dk/~torbenm/ICD
information science. From core foundational and theoretical material to final-year topics and applications, UTiCS books take a fresh, concise, and modern approach and are ideal for self-study or for a one- or two-semester course. The texts are all authored by established experts in their fields, reviewed by an international advisory board, and contain numerous examples and problems. Many include fully worked solutions. For further volumes: www.springer.com/series/7592 Torben Ægidius Mogensen
table-driven LL(1) parsing 65 Fig. 2.19 Input and stack during table-driven LL(1) parsing 66 Fig. 2.20 Removing left-recursion from Grammar 2.11 68 Fig. 2.21 Left-factorised grammar for conditionals 69 Fig. 2.22 SLR table for Grammar 2.9 72 Fig. 2.23 Algorithm for SLR parsing 72 Fig. 2.24 Example SLR parsing 73 Fig. 2.25 Example grammar for SLR-table construction 73 Fig. 2.26 NFAs for the productions in Grammar 2.25 74 Fig. 2.27 NFAs for the productions in Grammar 2.25 with epsilon
insert run-time checks to catch cases when an index is outside the bounds of the array. Some of these checks can be removed by the compiler. One way of doing this is to see if the tests on the index are subsumed by earlier tests or ensured by assignments. For example, assume that, in the loop shown above, a is declared to be a k×k array. This means that the entry test for the loop will ensure that j is always less than the upper bound on the array, so this part of the index test can be
empty register stack), the OS will restore earlier saved parts of the stack. Suggested exercises: 9.3. 9.12 Further Reading Calling conventions for various architectures are usually documented in the manuals provided by the vendors of these architectures. For example, the calling convention of the ARM processor is described in . Additionally, the calling convention for the MIPS microprocessor is shown in . Functions declared inside other functions require more complex mechanisms than
holds. Exercise A.5 Prove that if elements are drawn from a finite universe U and F is a monotonic function over sets of elements from U , then there exists an n such that X = Fn ( U ) is the unique maximal solution to the set equation X = F ( X ). Index A Abstract syntax Accept Action Activation record Alias Allocation Alpha Alphabet ARM Array Assembly Assignment Associative Attribute inherited synthesised B Back-end Biased colouring Binding dynamic static C C Call