Compiler Design
Compiler Design tests the pipeline from source text to machine code, with heavy emphasis on parsing and a lighter touch on runtime organisation and optimisation. Questions are typically: build a FIRST/FOLLOW set, identify a conflict class, or count entries in a parsing table.
Phases and passes
Lexical analysis (regular expressions to NFA to DFA), syntax analysis (CFG, parsing), semantic analysis (type checking), intermediate code generation, optimisation, code generation - with the symbol table shared across all phases.
Parsing
- LL(1): no left recursion, no common prefixes, and for each non-terminal the FIRST sets of alternatives are disjoint and never intersect FOLLOW.
- SLR(1) uses FOLLOW sets for reductions, CLR(1) uses item lookaheads, LALR(1) merges CLR states with identical cores - merging can create reduce–reduce conflicts but never shift–reduce conflicts.
- Any ambiguous grammar is neither LL(1) nor LR.
Translation and runtime
- S-attributed definitions use only synthesised attributes and are evaluated bottom-up; L-attributed definitions add inherited attributes evaluated left to right.
- An activation record holds actual parameters, return address, saved registers, local variables and temporaries.
Worked example
Grammar: S → A a, A → b | ε. FIRST(A) = {b, ε}, so FIRST(S) = {b, a}. FOLLOW(A) = {a}. The LL(1) table has M[A, b] = A → b and M[A, a] = A → ε, with no other entries for A - the grammar is LL(1).
Traps that cost marks
- Forgetting that FOLLOW of the start symbol contains $.
- Assuming left-recursion elimination changes the language; it only changes the grammar.
- Confusing the number of LR(0) items with the number of states.