COMPILER DESIGN
                              LECTURE NOTES  
                                         ON         
                             COMPILER DESIGN 
                                              
                                             
                                             
                                             
                                    Prepared by 
                          Dr. Subasish Mohapatra 
                                                   
                                             
                                                   
                                         Welcome 
                                             
                                             
              Department of Computer Science and Application 
            College of Engineering and Technology, Bhubaneswar 
                Biju Patnaik University of Technology, Odisha  
                                                                     SYLLABUS 
                                                     Compiler Design (3-0-0) 
                MODULE – 1  (Lecture hours: 13) 
                Introduction: Overview and phases of compilation.                                                                (2-hours) 
                Lexical  Analysis:  Non-deterministic  and  deterministic  finite  automata  (NFA  &  DFA),  regular 
                grammar, regular expressions and regular languages, design of a lexical analyzer as a DFA, lexical 
                analyser generator.                                                                                                  (3-hours)  
                Syntax Analysis: Role of a parser, context free grammars and context free languages, parse trees and 
                derivations, ambiguous grammar. 
                Top Down Parsing: Recursive descent parsing, LL(1) grammars, non-recursive predictive parsing, error 
                reporting and recovery. 
                Bottom Up Parsing: Handle pruning and shift reduces parsing, SLR parsers and construction or SLR 
                parsing tables, LR(1) parsers and construction of LR(1) parsing tables, LALR parsers and construction 
                of efficient LALR parsing tables, parsing using ambiguous grammars, error reporting and recovery, 
                parser generator.                                                                                                 (8-hours)  
                 
                MODULE – 2  (Lecture hours: 14) 
                Syntax Directed Translation: Syntax directed definitions (SDD), inherited and synthesized attributes, 
                dependency  graphs,  evaluation  orders  for  SDD,  semantic  rules,  application  of  syntax  directed 
                translation.                                                                                                      (5-hours)  
                Symbol Table: Structure and features of symbol tables, symbol attributes and scopes.       (2-hours) 
                Intermediate Code Generation: DAG for expressions, three address codes - quadruples and triples, 
                types  and declarations,  translation  of expressions, array  references, type checking  and conversions, 
                translation  of  Boolean  expressions  and  control  flow  statements,  back  patching,  intermediate  code 
                generation for procedures.                                                                                        (7-hours)  
                 
                MODULE – 3 (Lecture hours: 8) 
                Run  Time  Environment:  storage  organizations,  static  and  dynamic  storage  allocations,  stack 
                allocation, handlings of activation records for calling sequences.                                                    (3-hours)  
                Code  Generations:  Factors  involved,  registers  allocation,  simple  code  generation  using  stack 
                allocation, basic blocks and flow graphs, simple code generation using flow graphs.             (3-hours)  
                  Elements of Code Optimization: Objective, peephole optimization, concepts of elimination of local 
                  common sub-expressions, redundant and un-reachable codes, basics of flow of control optimization.        
                                                                                                                                   (2-hours) 
                                                    CONTENTS 
             Lecture-1      Introduction to compiler & its phases 
             Lecture-2      Overview of language processing system 
             Lecture-3      Phases of a Compiler 
             Lecture-4      Languages 
             Lecture-5      Converting RE to NFA (Thomson Construction) 
             Lecture-6      Lexical Analysis 
             Lecture-7      Lexical Analyzer Generator 
             Lecture-8      Basics of Syntax Analysis 
             Lecture-9      Context-Free Grammar 
             Lecture-10     Left Recursion 
             Lecture-11     YACC 
             Lecture-12     Top-down Parsing 
             Lecture-13     Recursive Predictive Parsing 
             Lecture-14     Non-recursive Predictive Parsing-LL(1) 
             Lecture-15     LL(1) Grammar 
             Lecture-16     Basics of Bottom-up parsing 
             Lecture-17     Conflicts during shift-reduce parsing 
             Lecture-18     Operator precedence parsing 
             Lecture-19     LR Parsing 
             Letcure-20     Construction of SLR parsing table 
             Lecture-21     Construction of canonical LR(0) collection 
             Lecture-22     Shift-Reduce & Reduce-Reduce conflicts 
             Lecture-23     Construction of canonical LR(1) collection 
             Lecture-24     Construction of LALR parsing table 
             Lecture-25     Using ambiguous grammars 
             Lecture-26     SYNTAX-DIRECTED TRANSLATION 
             Lecture-27     Translation of Assignment Statements 
             Lecture-28     Generating 3-address code for Numerical Representation of Boolean expressions 
             Lecture-29     Statements that Alter Flow of Control 
             Lecture-30     Postfix Translations 
             Lecture-31     Array references in arithmetic expressions 
             Lecture-32     SYMBOL TABLES 
             Lecture-33     Intermediate Code Generation 
             Lecture-34     Directed Acyclic Graph 
             Lecture-35     Flow of control statements with Jump method 
             Lecture-36     Backpatching 
             Lecture-37     RUN TIME ADMINISTRATION 
             Lecture-38     Storage Organization 
             Lecture-39     ERROR DETECTION AND RECOVERY 
             Lecture-40     Error Recovery in Predictive Parsing 
             Lecture-41     CODE OPTIMIZATION 
             Lecture-42     Local Optimizations