MCA-243
Compiler Design
How a program becomes machine code — lexical analysis with Lex, parsing with YACC, syntax-directed translation, optimisation and code generation.
- Semester
- Semester 3
- Credits
- 3
- Scheme
- 3 lectures a week
- Contact hours
- 43 across four units
- Category
- Core Elective - III
What the paper is
Compiler Design is the paper that connects everything else: Theory of Computations supplies the automata and grammars, Data Structures supplies the symbol table and the trees, and Computer Architecture supplies the target. It is the classic capstone for that reason.
It follows the phases in order, and the order is the syllabus: lexical analysis, parsing top-down then bottom-up, syntax-directed definitions, type checking, intermediate code, optimisation, and code generation. Each phase consumes what the last one produced.
Units I and II are the most examinable and the most mechanical. Constructing an LL(1) parse table, or the item sets for an SLR parser, is a procedure you can practise to reliability — and the marks are for the procedure, not for describing it.
What to concentrate on
- FIRST and FOLLOW sets, then an LL(1) parse table, then an SLR item set construction — these three procedures are the backbone of the paper. Practise each on a small grammar until they are quick and accurate.
- Left recursion removal and left factoring are short, certain marks and a prerequisite for the table construction above. Do not leave them to the exam hall.
- For Unit III, three-address code generation for expressions and control flow is the standard question. Have the pattern for if-else and while loops ready rather than deriving it.
Syllabus, unit by unit
Summarised from the approved scheme. Hours are the contact hours the scheme allots, which is a fair guide to where the marks sit.
Unit I · Introduction, lexical analysis and top-down parsing
13 hours- Concept of compilers and the phases of a compiler; context-free grammar
- Registers of a microprocessor, assembly language and programming
- Lexical analysis and its implementation with Lex or Flex
- Top-down parsing: recursive descent, operator precedence and LL(1) parsers
Unit II · Bottom-up parsing and syntax-directed definitions
10 hours- SLR, LR(k) and LALR parsers
- Implementation of a parser using YACC or Bison
- Inherited and synthesised attributes, the dependency graph, evaluation order
- Bottom-up and top-down evaluation of attributes; L-attributed and S-attributed definitions
Unit III · Type checking, intermediate code and optimisation
10 hours- Type systems and expressions, structural and name equivalence, type conversion, overloaded functions and operators, polymorphic functions
- Intermediate representation; translation of declarations and assignments
- Intermediate code for control flow, Boolean expressions and procedure calls
- Code optimisation: sources of optimisation, optimisation of basic blocks and loops
- Global dataflow analysis, iterative data flow equations, code improving transformations, aliases, data flow analysis of structured flow graphs
Unit IV · Code generation and the run-time system
10 hours- Code generation issues, basic blocks and flow graphs, register allocation
- DAG representation of programs and code generation from DAGs
- Peephole optimisation, code generator generators, machine specification
- Run-time system: storage organisation, activation trees and records, parameter passing, the symbol table, dynamic storage allocation
- Error detection and recovery: ad-hoc and systematic methods
How it is examined
- Question 1 is compulsory, covers the whole syllabus, and is made of objective or short-answer questions. It carries 12 marks.
- The rest of the paper is four units matching the four above. Each unit sets two questions and you attempt one, so there are four more answers at 12 marks each.
- Examiners are asked to map every question to a course outcome using Bloom's taxonomy, which is why questions are phrased as “apply”, “analyse” or “evaluate” rather than only “explain”.
The pass mark is 40 out of 100 in every paper.
Learning objectives
- The concept of a lexical analyser and the working of the Lex tool
- The concept of a syntactic analyser and the working of the YACC tool
- Code generation and code optimisation
- Algorithms and data structures for compilation; compilers and cross-compilers
Assumed beforehand
- Programming language
- Theory of Computation
Paired in the scheme with MCA-267 Lab based on Core Elective III.
Books it is taught from
- TB1Alfred V. Aho and Jeffrey D. Ullman, “Compilers: Principles, Techniques and Tools”, Pearson Education, 1st edition, 2006
- TB2Levine, Mason and Brown, “Lex & Yacc”, O'Reilly, 2nd edition, 1992
- TB3Alfred V. Aho and Jeffrey D. Ullman, “Principles of Compiler Design”, Narosa Publications, 5th edition, 2002
- TB4Morris Mano, “Computer System Architecture”, Pearson Education, 3rd edition, 1993
Notes for MCA-243
Lecture notes, question papers and assignments filed against MCA-243 are in the library. Everything there has been checked by a moderator before it appears, and an account is free — new ones are approved by hand, which is what keeps the shelf clean.