Basics of Compiler Design

1 Basics of Compiler DesignAnniversary editionTorben gidius MogensenDEPARTMENT OF COMPUTER SCIENCEUNIVERSITY OF COPENHAGENP ublished Torben gidius Mogensen 2000 of Computer ScienceUniversity of CopenhagenUniversitetsparken 1DK-2100 CopenhagenDENMARKBook homepage: torbenm/BasicsFirst published 2000 This edition: August 20, 2010 ISBN 978-87-993154-0-6 Contents1 is a Compiler ? .. phases of a Compiler .. learn about compilers? .. structure of this book .. the lecturer .. to use ..72 Lexical .. expressions .. finite automata .. a regular expression to an NFA .. finite automata .. an NFA to a DFA.

2 Set equations .. subset construction .. versus speed .. of DFAs .. states .. and lexer generators .. generators .. Properties of regular languages .. Relative expressive power .. Limits to expressive power .. Closure properties .. Further reading ..46 Exercises ..463 Syntax .. grammars .. to write context free grammars .. trees and ambiguity .. precedence .. ambiguous expression grammars .. sources of ambiguity .. analysis .. parsing .. parsing revisited .. A larger example .. LL(1) parsing .. Recursive descent .. Table-driven LL(1) parsing.

3 Conflicts .. Rewriting a grammar for LL(1) parsing .. Eliminating left-recursion .. Left-factorisation .. Construction of LL(1) parsers summarized .. SLR parsing .. Constructing SLR parse tables .. Conflicts in SLR parse-tables .. Using precedence rules in LR parse tables .. Using LR-parser generators .. Declarations and actions .. Abstract syntax .. Conflict handling in parser generators .. Properties of context-free languages .. Further reading .. 105 Exercises .. 105 CONTENTSiii4 Scopes and Symbol .. tables .. of symbol tables.

4 Persistent symbol tables .. simple imperative symbol table .. issues .. or separate name spaces .. reading .. 118 Exercises .. 1185 .. structure of an interpreter .. small example language .. interpreter for the example language .. expressions .. function calls .. a program .. and disadvantages of interpretation .. reading .. 130 Exercises .. 1306 Type .. Design space of types .. for type checking .. checking expressions .. checking of function declarations .. checking a program.

5 Type checking .. reading .. 143 Exercises .. 1437 Intermediate-Code .. an intermediate language .. intermediate language .. translation .. code from expressions .. of translation .. statements .. operators .. logical operators .. control statements .. structured data .. values .. and unions .. Translating declarations .. Example: Simple local declarations .. Further reading .. 172 Exercises .. 1738 Machine-Code .. jumps .. complex instructions .. instructions .. reading.

6 188 Exercises .. 1889 Register .. analysis .. allocation by graph colouring .. redundant moves .. explicit register numbers .. reading .. 206 Exercises .. 20610 Function Introduction .. The call stack .. Activation records .. Prologues, epilogues and call-sequences .. Caller-saves versus callee-saves .. Using registers to pass parameters .. Interaction with the register allocator .. Accessing non-local variables .. Global variables .. Call-by-reference parameters .. Nested scopes .. Variants.

7 Variable-sized frames .. Variable number of parameters .. Direction of stack-growth and position of FP .. Register stacks .. Functions as values .. Further reading .. 229 Exercises .. 22911 Analysis and Data-flow analysis .. Common subexpression elimination .. Available assignments .. Example of available-assignments analysis .. Using available assignment analysis for common subex-pression elimination .. Jump-to-jump elimination .. Index-check elimination .. Limitations of data-flow analyses .. Loop optimisations.

8 Code hoisting .. Memory prefetching .. Optimisations for function calls .. Inlining .. Tail-call optimisation .. Specialisation .. Further reading .. 254 Exercises .. 25412 Memory Introduction .. Static allocation .. Limitations .. Stack allocation .. Heap allocation .. Manual memory management .. A simple implementation ofmalloc()andfree().. Joining freed blocks .. Sorting by block size .. Summary of manual memory management .. Automatic memory management .. Reference counting.

9 Tracing garbage collectors .. Scan-sweep collection .. Two-space collection .. Generational and concurrent collectors .. Summary of automatic memory management .. reading .. 277 Exercises .. 27713 Bootstrapping a Introduction .. Notation .. Compiling compilers .. Full bootstrap .. Further reading .. 288 Exercises .. 288A Set notation and Basic concepts and notation .. Operations and predicates .. Properties of set operations .. Set-builder notation .. Sets of sets .. Set equations.

10 Monotonic set functions .. Distributive functions .. Simultaneous equations .. 297 Exercises .. 297 List of expressions .. algebraic properties of regular expressions .. of an NFA .. NFA fragments from regular expressions .. for the regular expression (a|b) ac.. NFA construction for regular expression shorthands .. NFA for[0-9]+.. of a DFA .. constructed from the NFA in figure .. Non-minimal DFA .. Minimal DFA .. Combined NFA for several tokens .. Combined DFA for several tokens .. A 4-state NFA that gives 15 DFA states .. regular expressions to context free grammars.