Crafting a Compiler

1. Introduction.


Overview and History of Compilation.



What Compilers Do.



Interpreters.



Syntax & Semantics of Programming Languages.



Organization of a Compiler.



Compiler Design & Programming Language Design.



Architectural Influences of Computer Design.



Compiler Variants.



Program Development Environment.



2. A Simple compiler.


An Informal Definition of the ac Language.



Structure of an ac Compiler.



Formal Syntax Definition of ac.



The Scanner's Job.



The Parser's Job.



Semantic Analysis.



Code Generation.



3. Scanning.


Overview of a



Regular Expressions.



Finite Automata & Scanners.



The Lex Scanner Generator.



Other Scanner Generators.



Practical Considerations of Building a Scanner.



Translating Regular Expressions & Finite Automata.



Summary.



4. Grammars and Parsing.


Context-free grammars: Concepts & Notation.



Properties of Context-Free Grammars.



Transforming Extended Grammars.



Parsers and Recognizers.



Grammar Analysis Algorithms.



5. LL Parsing.


The LL(1) Predict() Function.



Recursive-Descent LL(1) parsers.



Table-Driven LL(1)Parsers.



Making Grammars LL(1).



The "if-then-else" Problem in LL(1) Parsing.



Properties of LL(1) Parsers.



6. LR Parsing.


Shift-Reduce Parsers.



LR(0) Table Construction.



Conflict Diagnosis.



SLR(k) Table Construction.



LALR(k) Table Construction.



LR(k) Table Construction.



7. Abstract Syntax Trees.


Overview.



Synthesized and Inherited Attributes.



Bottom-up Translation.



Top-down Translation.



Abstract Syntax Trees.



Summary.



8. Symbol Tables.


9. Semantic Analysis of Expression.


Declaration Processing Fundamentals.



Semantic Processing of Simple Declarations.



Semantic Processing for Simple Names and Expressions: AnIntroduction to Type Checking.



10. Semantic Analysis of Control Structures.


Semantic Processing for Control Structures.



Semantic Processing for Procedure Declarations and Calls.



11. Run-Time Storage Organization.


Static Allocation.



Stack Allocation.



Heap Allocation.



12. A Simple View of Code Generation.


Assemble Language and Binary Formats.



Translating ASTs.



Code Generation for ASTs.



Declaration of Scalar Variables and Constants.



Translating Simple Expressions.



Translating Predefined Operators.



Pointer and Reference Manipulations.



Type Conversion.



Assignment Operators.



13. Code Generation for Control Structures, and Subprograms.


Code Generation for Control Structures.



Code Generation for Subprogram Calls.



14. Processing Data Structure Declarations and References.


Semantic Processing for Records and Static Arrays.



Semantic Processing for Pointers and References.



Semantic Processing for General Array Types.



Semantic Processing for Variant Records and Other Union Types.



Semantic Processing for Modules and Classes.



Code Generation for Simple Record and Array References.



Multidimensional Array Organization and References.



Referencing Variant Records and Records with Dynamic Objects.



Code Generation for Pointers and References.



Code Generation for Modules and Classes.



15. Advanced Code Generation.


Translating Expression Trees.



Translating Expression Dags.



Register Allocation Using Graph Coloring.



Automatic Instruction Selection.



Peephole Optimization.



16. Optimization.


Introduction.



Intermediate Languages.



Introduction to data flow frameworks.



Available Expressions.



Dominance.



Live Variables.



Data Flow Frameworks.



Data Flow Graph.



Meet Lattice.



Transfer Functions.



Bit-vectoring problems.



Evaluating Data Flow Frameworks.



Properties of monotone data flow frameworks.



Rate of convergence.



Distributive frameworks.



Static Single Assignment (SSA) Form.



Definition.



Computation.



Optimizations based on SSA Form.



Constant Propagation.



Value Numbering.



Register Assignment. 0201385937T04062001