Compiler construction

· Module I

Introduction to compilers - Different Phases. Lexical Analysis - input buffering - specification of tokens - Recognition of tokens - lexical Analyser generators - lex - Finite Automata - Regular expressions to finite automata .

· Module II

Syntax Analysis. Context free grammar – Derivations and parse trees - Ambiguity - Elimination of ambiguity - Elimination of left recursion – Left factoring. The role of a Parser - Top down parsing - Recursive descent parsing - predictive parsers Construction of predictive parsing tables. Bottom Up Parsing - Shift reduce parsing Operator precedence parsing - precedence relations and functions. LR parsers - LR parsing algorithms - LR grammars - Construction of SLR, Canonical and LALR parsing tables. Parser generators - Case study - Yacc

· Module III

Syntax directed Translation. Syntax directed definitions - Synthesised and inherited attributes - Dependency graphs. Construction of syntax trees - syntax tree. Bottom up evaluation of S-attributed definition - L -attributed definitions. Type checking - type systems - static and dynamic type checking

Run time Environment. Storage organisation schemes - Activation records - Compile time layout. Storage allocation strategies - static allocation - stack allocation - heap allocation. Accessing non-local names. Parameter passing mechanisms.

· Module IV

Symbol tables -representing scope information. Intermediate code generation - intermediate languages - declaration and assignment statements. Code generation. issues - memory management - instruction selection - register allocation. Runtime storage allocation.- basic blocks and flow graphs. Code optimisation. Principal sources of optimisation - function preserving transformations - common subexpressions - copy propagation - dead-code elimination - loop optimisation - code motion - strength reduction