• ES Español
• EN English

5.35. Compilers (Mandatory)

5.35.1. Justification ↑ Back to top

This course provides a deep understanding of how high-level languages are transformed into executable machine code. The study of compilers allows students to understand language semantics, memory management, and code optimization, which are fundamental skills for designing domain-specific languages and high-performance software engineering.

5.35.2. Generales Goals ↑ Back to top

1. Understand the phases of a compiler and construction tools.
2. Implement lexical and syntactic analyzers based on grammars.
3. Generate and optimize intermediate code for a specific architecture.

5.35.3. Contribution to Outcomes ↑ Back to top

AG-C08) Problem Analysis: Identifies, formulates, and analyzes complex computing problems. (Usage)

AG-C12) Applies computer science theory and software development fundamentals to produce computer-based solutions. (Usage)

5.35.4. Content ↑ Back to top

5.35.4.1. Program Analysis and Analyzers (20 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Aho et al., 2006; Appel, 2004)

Topics

1. Relevant program representations, such as basic blocks, control-flow graphs, def-use chains, and static single assignment
2. Undecidability and consequences for program analysis
3. Flow-insensitive analysis, such as type-checking and scalable pointer and alias analysis
4. Flow-sensitive analysis, such as forward and backward dataflow analyses
5. Path-sensitive analysis, such as software model checking and software verification
6. Tools and frameworks for implementing analyzers
7. Role of static analysis in program optimization and data dependency analysis during exploitation of concurrency
8. Role of program analysis in (partial) verification and bug-finding
9. Parallelization:
10. Analysis for auto-parallelization
11. Analysis for detecting concurrency bugs enumerate

Learning Outcomes

1. Explain the difference between dataflow graph and control flow graph [Explain]
2. Explain why non-trivial sound program analyses must be approximate [Explain]
3. Argue why an analysis is correct (sound and terminating) [Argue]
4. Explain why potential aliasing limits sound program analysis and how alias analysis can help [Explain]
5. Use the results of a program analysis for program optimization and/or partial program correctness [Use]

5.35.4.2. Language Translation and Execution (24 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Aho et al., 2006; Appel, 2004)

Topics

1. Execution models for JIT (Just-In-Time), compiler, interpreter
2. Use of intermediate code, e.g., bytecode
3. Limitations and benefits of JIT, compiler, and interpreter
4. Cross compilers/transpilers
5. BNF and extended BNF representation of context-free grammar
6. Parse tree using a simple sentence such as arithmetic expression or if-then-else statement
7. Execution as native code or within a virtual machine
8. Language translation pipeline: syntax analysis, parsing, optional type-checking, translation/code generation and optimization, linking, loading, execution
9. Run-time representation of core language constructs such as objects (method tables) and functions that can be passed as parameters to and returned from functions (closures)
10. Secure compiler development

Learning Outcomes

1. Explain and understand the differences between compiled, JIT, and interpreted language implementations, including the benefits and limitations of each [Explain]
2. Differentiate syntax and parsing from semantics and evaluation [Differentiate]
3. Use BNF and extended BNF to specify the syntax of simple constructs such as if-then-else, type declaration and iterative constructs for known languages such as C++ or Python [Use]
4. Illustrate the parse tree using a simple sentence/arithmetic expression [Apply]
5. Illustrate translation of syntax diagrams to BNF/extended BNF for simple constructs such as if-then-else, type declaration, iterative constructs, etc [Apply]
6. Illustrate ambiguity in parsing using nested if-then-else/arithmetic expression and show resolution using precedence order [Apply]
7. Discuss the benefits and limitations of garbage collection, including the notion of reachability [Debate]

5.35.4.3. Run-time Behavior and Systems (20 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Aho et al., 2006; Cooper and Torczon, 2011)

Topics

1. Process models using stacks and heaps to allocate and deallocate activation records and recovering environments using frame pointers and return addresses during a procedure call including parameter-passing examples
2. Schematics of code lookup using hash tables for methods in implementations of object-oriented programs
3. Data layout for objects and activation records
4. Object allocation in heap
5. Implementing virtual entities and virtual methods; virtual method tables and their application
6. Run-time behavior of object-oriented programs
7. Compare and contrast allocation of memory during information exchange using parameter-passing and non-local variables (using chain of static links).
8. Dynamic memory management approaches and techniques: malloc/free, garbage collection (mark-sweep, copying, reference counting), regions (also known as arenas or zones)
9. Just-in-time compilation and dynamic recompilation
10. Interface to operating system (e.g., for program initialization)
11. Interoperability between programming languages including parameter-passing mechanisms and data representation:
12. Big endian, little endian
13. Data layout of composite data types such as arrays enumerate
14. Other common features of virtual machines, such as class loading, threads, and security checking
15. Sandboxing

Learning Outcomes

1. Discuss benefits and limitations of automatic memory management [Debate]
2. Explain the use of metadata in run-time representations of objects and activation records, such as class pointers, array lengths, return addresses, and frame pointers [Explain]
3. Compare and contrast static allocation vs stack-based allocation vs heap-based allocation of data elements [Compare]
4. Explain why some data elements cannot be automatically deallocated at the end of a procedure/method call (need for garbage collection) [Explain]
5. Discuss advantages, disadvantages, and difficulties of just-in-time and dynamic recompilation [Debate]
6. Discuss the use of sandboxing in mobile code [Debate]
7. Identify the services provided by modern language run-time systems [Analyze]

5.35.5. Bibliography ↑ Back to top

Aho, A. V., Lam, M. S., Sethi, R., and Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools. Pearson, 2nd edition.

Appel, A. W. (2004). Modern Compiler Implementation in Java. Cambridge University Press, 2nd edition.

Cooper, K. and Torczon, L. (2011). Engineering a Compiler. Morgan Kaufmann, 2nd edition.