Course Details

1. Discuss the trends in programming languages and machine architecture that are shaping compilers.
2. Recall the relationship between compiler design and computer-science theory.
3. Examine the basic principles and techniques that form the construction of compiler.
4. Identify the difficulties in developing modern compilers, and describe the techniques used to support such features.
5. Appraise the theory and practice of compiler design.
6. Design, construct, implement, and test/verify a compiler for a simple programming language

Introduction to Compiling: What is a compiler? Language processors. High level overview  of the structure of a typical compiler (the analysis-synthesis model of compilation, Phases of a compiler: Lexical analysis, Syntax analysis, Semantic analysis, Intermediate code generation, Code optimization, Code generation, Symbol-table management, The grouping of phases into passes, Compiler-construction tools). The evolution of programming languages. The science of building a compiler. Applications of compiler technology.

Lexical Analysis: The role of the lexical analyzer. Lexical analysis versus parsing. Tokens, patterns, and lexemes. Attributes for tokens. Lexical errors. Input buffering. Alphabet, Languages, and Strings definitions. Operations on languages (union, concatenation, kleene closure, positive closure). Regular expressions. Regular definitions. Transition diagrams. Finite automata (NFA, DFA). From regular expressions to automata. The lexical-analyzer generator tool Lex.

Syntax Analysis: The role of the parser. Syntax error handling. Error-recovery strategies. Context-free grammars (Definition of terminals, nonterminals, start symbol, and productions. Notational Conventions, Derivations, Parse trees. Ambiguity. Verifying the language generated by a grammar. Context-free grammars versus regular expressions). Writing a grammar (Eliminating ambiguity. Elimination of left recursion. Left factoring). Top-down parsing (Recursive-descent parsing. FIRST and FOLLOW. LL(1) grammars. Nonrecursive predictive parsing. Error recovery in predictive parsing). Bottom-up parsing (Reductions. Handle pruning. Shift-reduce parsing. Conflicts during shift-reduce parsing). LR(k) parsers (Items and the LR(0) automaton. The LR-parsing algorithm. Constructing SLR-parsing tables. Viable prefixes). The canonical-LR and LALR parsers. Constructing LALR parsing tables. Using ambiguous grammars (precedence and associatively to resolve conflicts. The “Dangling-Else” ambiguity. Error recovery in LR parsing). Parser Generator tool yacc.

Syntax-Directed Translation: Syntax-directed definition (SDD). Inherited and synthesized attributes. Dependency graphs. “S-attributed” and “L-attributed” classes of SDD’s. Applications of syntax-directed translation (Construction of syntax trees. The structure of a Type). Syntax-directed translation (SDT) schemes (Postfix translation schemes, parser-stack implementation of postfix SDT’s, SDT’s with actions inside productions, eliminating left recursion from SDT’s, SDT’s for L-attributed definitions), Implementing L-attributed SDD’s.

Type Checking: Rules for type checking. Static and dynamic checking of types. Flow-of-control checks. Uniqueness checks. Name-related checks. Type expressions. Error recovery. Type conversions. Overloading of functions and operators.

Intermediate-Code Generation: Intermediate languages. Variants of syntax trees (Directed acyclic graphs). Three-Address code. Types of three-address statements. Syntax-directed translation into three-address code. Implementation of three-address statements. Declarations. Control -flow translation of Boolean expressions. Short-circuit code. Backpatching. Intermediate code for procedures.

Code Generation: Issues in the design of a code generator. The target language. Addresses in the target code. Basic blocks and flow graphs. A simple code generator. Register allocation and assignment. Peephole optimization.

Code Optimization: Criteria for code-improving transformations. Causes of redundancy. Global common subexpressions. Copy propagation. Dead-code elimination. Code motion. Induction variables and reduction in strength.

• A.V. Aho, M.S. Lam, R. Sethi and J.D. Ullman, Compilers - Principles, Techniques, and Tools, 2nd Ed., Addison-Wesley, 2007

• R. Hunter, The Essence of Compilers, Prentice Hall, 1999
• T. Mason and D. Brown, lex & yacc, 2nd Ed., O’Reilly Media, 1995
• Notes/Manuals on Lexical-analyzer (lex/flex) and Parser (yacc/bison) generator tools are available on the Course’s Web Site.

Students are taught the course through lectures by means of computer presentations.

Further, demonstration of useful tools for generating lexical- and syntax-analyzers is provided in laboratories.

Homework consists of practical problems aiming to help students familiarising with the theory and practice of compiler design.

Central to the course is the project where students are required to develop a compiler for a simple programming language.

Lecture notes and presentations are available through the web for students to use in combination with the textbooks.