Generalities - Introduction

• What are the components of a compiler?
• What are the difference between interpreted and compiled languages?
• What makes a compiler “good” (size of executable, quality of optimization, bug detection, etc.)?
• What is the difference between call by value and call by reference?
• What is the difference between a name, an identifier, a location, a variable, a value and a litteral?
• What is the difference between a formal parameter (argument) and the actual parameter?
• What is the difference between imperative and declarative programming languages?
• Understand how a transition table, a transition diagram and a transition function can be mapped to each other in DFAs (cf. for instance p. 5 of those notes).

Converting NFA to DFA will not be required, I am assuming you know it from Theory and will not assess it.

Lexical Analysis

• Define regular expression and the |, *, - (range), ?, +, . and ϵ symbols.
• Understand the difference between a token’s type and its value.
• Know that comments, pre-processor directive, macros, tabs, blank, spaces, …, are not tokens.
• Understand that the lexical analysis process a stream of characters to output a stream of tokens.
• Have basic understanding of .lex files and how to use them.
• Be able to map a simple regular expression to a DFA or NFA (you can practise on-line).
• Understand that, in case of ambiguity, the longest match is used to break ties between regular expression, and then the order of the expressions.

Parsing

• Define context-free grammar and Backus-Naur form.
• Know how to convert a regular expression with recursion into a context-free grammar, and reciprocally.
• Define grammar (terminal symbol, non-terminal symbol, production rule, start symbol).
• Find simple derivations and map them to parse trees.
• Understand the difference between left-recursive and right-recursive regular expressions.
• Be able to identify when a grammar is ambiguous.
• Express e.g. the precedence or associativity of operators based on their production rules.
• Understand a basic recursive descent parsing.
• Understand that every ambiguous grammar is not LL(1), but that not being ambiguous does not imply being LL(1).
• Understand the general version of the algorithm that remove left-recursion (you can find it, illustrated, on this page).
• Understand that 1 symbol of look-ahead may not always be enough.
• Be able to “simulate” the execution of an automata implementing an LR(0) algorithm on a simple grammar.
• Have basic understanding of bison’s rules and structure, as well as its features (associativity, precedence, resolution of conflicts, …) and limitations (limited to LALR(1) grammar, cannot handle all ambiguous cases, …).

Representations of Programs

You should be able to define, read and construct the following representations of programs:

• Abstract Syntax Trees
• Abstract Parse Trees
• Concrete Parse Trees
• Control Flow Graph
• Syntax-Directed Translation (adding semantic actions (for instance, in Bison) to control flow graphs)
• Directed Acyclic Graph of arithmetic expression (with sharing)
• Three-address Code and its implementations (quadruples, triples and indirect triples)
• Dominator tree (and its connected notions of dominance frontier)

as well as

• Understand the benefits of static single assignment form and how to obtain it
• Be able to detect loops in control flow graph and name their components (header, latches, exiting blocks, pre-header, etc.), as well as being able to rotate them.

LLVM

• General history and motivation
• Standard commands (opt, clang, llvm-dis, llvm-as, lli, llc, …) and options (-emit-llvm, -O0, -o, …)
• Basic understanding of the thre forms of intermediate representation
• Basic understanding of the structure of ll files (modules, functions, peripheral entities, local values, target data layout, types, attributes, etc.)

Optimization and Analysis Passes

Understand the benefits and overall function of the following optimization or analysis passes:

• Global Value Numbering
• Elimination of dead code
• Constant folding
• Hoisting loop-invariant
• Auto-vectorization
• SimplifyCFG
• Early common subexpression elimination
• Global variable optimizer
• LoopClosedSSA
• LoopSimplify
• LoopUnswitch

Security

• Understand the possible security gaps in compilers
• Understand the possibility of compiler bombs
• Name some examples of optimizations producing un-safe code from safe code
• Understand how Ken Thompson’s Reflection on Trusting Trust attack works, and what a Quine is

Misc

• The difference between dynamically and statically typed
• The difference between type inference and type synthesis
• How casting / conversion works internally

Resources