(Subject Code: BCS-305) for Bachelor of Technology

1 COMPILER DESIGN LECTURE NOTES (Subject Code: BCS-305) for Bachelor of Technology in Computer Science and Engineering & Information Technology Department of Computer Science and Engineering & Information Technology Veer Surendra Sai University of Technology (Formerly UCE, Burla) Burla, Sambalpur, Odisha Lecture Note Prepared by: Prof. D. Chandrasekhar Rao Prof. Kishore Kumar Sahu Prof. Pradipta Kumar Das BCS-305 SYLLABUS COMPILER DESIGN (3-1-0) Credit-04 Module-I (10 Lectures) Introduction to Compiling: Compilers, Analysis of the source programe, The phases of a compiler, Cousins of the compiler,The grouping of phases, Compiler-construction tools A Simple One-Pass Compiler.

2 Overview, Syntax definition, Syntax-directed translation, Parsing, A translator for simpleexpressions, Lexical analysis, Incorporating a symbol table, Abstract stack machines, Putting thetechniques together Lexical Analysis: The role of the lexical analyzer, Input buffering, Specification of tokens, Recognition of tokens,A language for specifying lexical analyzers, Finite automata, From a regular expression to an NFA, Design of a lexical analyzer generator, Optimization of DFA-based pattern matchers Module-II (15 Lectures) Syntax Analysis.

3 The role of the parser, Context-free grammars, Writing a grammar, Top-down parsing, Bottom-up parsing, Operator-precedence parsing, LR parsers, Using ambiguous grammars, Parsergenerators Syntax-Directed Translation: Syntax-directed definitions, Construction of syntax trees, Bottom-up evaluation of S-attributed definitions, L-attributed definitions, Top-down translation, Bottom-up evaluation of inheritedattributes, Recursive evaluators, Space for attribute values at compile time, Assigning space atcompile time, Analysis of syntax-directed definitions Module-III (6 Lectures) Type Checking.

4 Type systems, Specification of a simple type checker, Equivalence of type expressions, Typeconversions, Overloading of functions and operators, Polymorphic functions, An algorithm forunification Run-Time Environments: Source language issues, Storage organization, Storage-allocation strategies, Access to nonlocal names, parameter passing, Symbol tables, Language facilities for dynamic storage allocation,Dynamic storage allocation techniques, Storage allocation in Fortran Module-IV (9 Lectures) Intermediate Code Generation: Intermediate languages, Declarations, Assignment statements, Boolean expressions, Casestatements, Back Patching, Procedure calls Code generation.

5 Issues in the design of a code generator, The target machine, Run-time storage management,Basic blocks and flow graphs, Next-use information, A Simple code generator, Registerallocation and assignment, The dag representation of basic blocks, Peephole optimization,Generating code from dags, Dynamic programming code-generation algorithm, Code-generatorgenerators Code Optimization: Introduction, The Principal sources of optimization, Optimization of basic blocks, Loops in flowgraphs, Introduction to global data-flow analysis, Iterative solution of data-flow equations, Code-improving transformations, Dealing with aliases, Data-flow analysis of structured flow graphs,Efficient data-flow algorithms, A tool for data-flow analysis, Estimation of types, Symbolicdebugging of optimized code.

6 Text Books: 1. Compilers Principles, Techniques, & Tools, by , & , PearsonEducation 2. Principle of Compiler Design, and Ullman, Addition Wesley of CSE - 2 - LESSION PLAN Course Code: BCS-303 COMPILER DESIGN(3-0-0) 6th Semester Lecture Classes: 40 Lecture-1 Overview of systems, why we study programming languages?, attributes of a good language, classification of programming languages. Ref: Principles of programming languages, Rabi Sethi Lecture-2 Introduction to Compiler, Cousins of Compiler(Translator, assembler, interpreter, loader, linker etc), Phases of Compilers. Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-3 Operation in each phases of a Compiler, lexical analyzer, syntax analyzer, semantics analyzer, symbol table manager, error handler, intermediate code generator, code optimizer, code generator.

7 Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-4 Compiler Construction Tools, Parser generators, Scanner generators, syntax directed translation engines, automatic code generator, data flow engine. Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-5 Role of the lexical analyzer, issues in lexical analysis, tokens, patterns, lexemes. Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-6 Lexical errors and error recovery actions, Input buffering. Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-7 Specification of tokens, Strings and languages, Finite automata, DFA, NFA. Ref: Principle of Compiler Design, , Rabi Sethi, Automata Theory, KLP Mishra, N.

8 Chandrasekharan Automata Theory, AV Aho, JD Ullman Lecture-8 Equivalence of NFA and DFA, Conversion of NFA to DFA. Ref: Automata Theory, KLP Mishra, N. Chandrasekharan Automata Theory, AV Aho, JD Ullman Lecture-9 Minimizing states of DFA, -NFA, Ref: Automata Theory, KLP Mishra, N. Chandrasekharan Automata Theory, AV Aho, JD Ullman Lecture-10 Regular Expression, regular grammar, Conversion of regular expression into NFA Ref: Automata Theory, KLP Mishra, N. Chandrasekharan Automata Theory, AV Aho, JD Ullman Lecture-11 A language for specifying lexical analyzer, Design of lexical analyzer generator Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-12 The role of Parser, Syntactic errors and recovery actions Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-13 Context free Grammar, Parse Tree, Parse tree Derivation, Left most Derivation, Right most derivation, ambiguity.

9 Ref: Automata Theory, KLP Mishra, N. Chandrasekharan Automata Theory, AV Aho, JD Ullman Lecture-14 Eliminating ambiguity, predictive parsing, Recursive decent parsing, predictive parsing using tables. Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-15 Top down parsing, bottom up parsing, shift reduce parsing using the ACTION/GOTO Tables. Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-16 Table construction, SLR, LL, LALR Grammar, Practical consideration for LALR grammar. Ref: Principle of Compiler Design, , Rabi Sethi, Automata Theory, KLP Mishra, N. Chandrasekharan Lecture-17 Syntax directed translation, Syntax directed definition, bottom up evaluation of S-attributed definition.

10 Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-18 L-attribute definition, top-down translation, bottom up evaluation of inherited attributes. Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-19 Recursive evaluators, space for attribute values at compile time, assigning space at compiler construction time, analysis of syntax directed definitions. Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-20 Semantic actions, semantic analysis, symbol tables, types and type checking. Ref: Principle of Compiler Design, , Rabi Sethi, Lecture-21 Run time Environment, Activation Records, run time storage organization.