CS 335: Compiler Design

Units: 3-0-3-12
Pre-requisites: ESC101, CS210, CS220, CS330

Course Contents:

  1. Compiler structure: analysis-synthesis model of compilation, various phases of a compiler, tool based approach to compiler construction.

  2. Lexical analysis: interface with input, parser and symbol table, token, lexeme and patterns. Difficulties in lexical analysis. Error reporting. Implementation. Regular definition, Transition diagrams.

  3. Syntax analysis: CFGs, ambiguity, associativity, precedence, top down parsing, recursive descent parsing, transformation on the grammars, predictive parsing, bottom up parsing, LR parsers (SLR, LALR, LR).

  4. Syntax directed definitions: inherited and synthesized attributes, dependency graph, evaluation order, bottom up and top down evaluation of attributes, L- and S-attributed definitions.

  5. Type checking: type system, type expressions, structural and name equivalence of types, type conversion, overloaded functions and operators, polymorphic functions.

  6. Run time system: storage organization, activation tree, activation record, stack allocation of activation records, parameter passing mechanisms.

  7. Intermediate code generation: intermediate representations, translation of declarations, assignments, control flow, boolean expressions and procedure calls. Implementation issues.

  8. Code generation and instruction selection: issues, basic blocks and flow graphs, register allocation, code generation, dag representation of programs, code generation from dags, peep hole optimization, code generator generators, specifications of machine.

  9. Introduction to Dataflow Anaysis (Reaching Definitions and Live Variable Analysis).

  10. Introduction to compilation for modern architectures (superscaler out-of-order, VLIW, GPU etc.).

Books and References:

  1. AV Aho, MS Lam, R Sethi, JD Ullman, Compiler Design: Principles, Techniques and Tools, 2nd Ed., Prentice-Hall, 2006
  2. AW Appel, J Palsberg, Modern Compiler Implementation in Java, Cambridge University Press, 2002
  3. AW Appel, M Ginsburg, Modern Compiler Implementation in C, Cambridge University Press, 2004.

Other references:

  1. K Cooper, L Torczon, Engineering a Compiler, 2nd Ed., Morgan Kaufmann, 2011
  2. KC Louden, Compiler Construction: Principles and Practice, Cengage Learning, 1997
  3. D Grune, H Bal, C Jacobs, K. Langendoen, Modern Compiler Design, Wiley, 2000
  4. Michael L Scott, Programming Language Pragmatics, 3rd Ed., Morgan Kaufmann, 2009
  5. S Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann/Elsevier(India), 2003.

Back to list of courses