Pearl Centre, S.B. Marg, Dadar (W), Mumbai  400 028.   Tel. 4232 4232 
                                                                                                                                                                                                                                                                                                       
                                                              CS : COMPUTER SCIENCE AND INFORMATION TECHNOLOGY 
                                                                                                                                                                                                                                                                                                       
                                                                                                                                                                                                                                    Compiler Design 
                                                                                                                                                                                                                                                                                                       
                                                          
                                                                                                                                                                                                                                                                                                       
                                                                                                                                                                                                                                                                                Index 
                                                                                                                                                                                                                                                                                                       
                                                          
                                                          
                                                          
                                                               Sr.                                                   Contents     Topics                                                                                                                                                                                                                                                                                                                                                                         Pg. 
                                                             No.                                                                                                                                                                                                                                                                                                                                                                                                                                                 No. 
                                                            1.    Introduction to Compiling and Programming Language Constructs 
                                                                                                                                                                                                                 Compilers 1 
                                                                                                                                                                                                                 Phases of Compilation                                                                                                                                                                                                                                                                                  4 
                                                                                                                                                                                                                 Compiler Writing Tools                                                                                                                                                                                                                                                                                 7 
                                                                                                                                                                                                                 Cross Compiler                                                                                                                                                                                                                                                                                         8 
                                                                                                                                  Notes                                                                          The Grouping of Phases                                                                                                                                                                                                                                                                                 9 
                                                                                                                                                                                                                 Programming Language Constructs                                                                                                                                                                                                                                                                     10 
                                                                                                                                                                                                                 Storage Management in Compiler                                                                                                                                                                                                                                                                      18 
                                                                                                                                                                                                                 Comparison of compiler and Interpreters                                                                                                                                                                                                                                                             20 
                                                                                                                                                                                                                 LMR (Last Minute Revision)                                                                                                                                                                                                                                                                          21 
                                                                                                            Assignment1                                                                                         Questions                                                                                                                                                                                                                                                                                           23 
                                                                                                              Test Paper1                                                                                       Questions 26 
                                                            2.    Lexical Analysis and Finite Automata 
                                                                                                                                                                                                                 Lexical Analysis                                                                                                                                                                                                                                                                                    30 
                                                                                                                                                                                                                 Design of Lexical Analyzer                                                                                                                                                                                                                                                                          33 
                                                                                                                                                                                                                 Finite State Automata                                                                                                                                                                                                                                                                               33 
                                                                                                                                  Notes                                                                          Regular Expression                                                                                                                                                                                                                                                                                  35 
                                                                                                                                                                                                                 A language for specifying Lexical Analyzers                                                                                                                                                                                                                                                         44 
                                                                                                                                                                                                                 Lex Specifications                                                                                                                                                                                                                                                                                  44 
                                                                                                                                                                                                                 LMR (Last Minute Revision)                                                                                                                                                                                                                                                                          46 
                                                                                                            Assignment2                                                                                         Questions                                                                                                                                                                                                                                                                                           48 
                                                                                                              Test Paper2                                                                                       Questions 52 
            Sr.        Contents     Topics                                                    Pg. 
            No.                                                                               No. 
            3.    Syntactic Specification of Programming Language and Parsing Techniques 
                                        Introduction 56 
                                        The Role of the Parser                                 56 
                                        Error Recovery Strategies                              57 
                                        ContextFree Grammar                                   58 
                         Notes          Parser and Parse Trees                                 60 
                                        Ambiguity 61 
                                        Elimination of Left Recursion                          63 
                                        Parsing Techniques                                     66 
                                        LMR (Last Minute Revision)                             83 
                     Assignment3       Questions                                              88 
                     Test Paper3       Questions 92 
            4.    Syntax Directed Translation, Symbol Table and Error Handling 
                                        Syntax directed Translation                            95 
                                        Syntax directed Definition                             95 
                                        Symbol Table                                           99 
                         Notes          Data Structures for Symbol Tables                     100 
                                        Error Handling                                        103 
                                        Error seen by each phase                              104 
                                        LMR (Last Minute Revision)                            106 
                     Assignment4       Questions                                             108 
                     Test Paper4       Questions 111 
            5.    Runtime Environment, Code Generation 
                                        Runtime Environment                                   115 
                         Notes          Storage Organization                                  116 
                                        Intermediate Code Generation                          119 
                                        LMR (Last Minute Revision)                            122 
                     Assignment5       Questions                                             126 
                     Test Paper5       Questions 130 
           Sr.      Contents     Topics                                            Pg. 
           No.                                                                     No. 
          Solved Examples                                                          134 
          Practice Problems                                                        170 
          SOLUTIONS   
               Assignments         Answer Key                                      177 
                                   Model Solutions                                 178 
                Test Papers        Answer Key                                      188 
                                   Model Solutions                                 189 
             Practice Problems     Answer Key                                      199 
                                   Model Solutions                                 200 
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           
           Topic 1 : Introduction to Compiling and Programming Language Constructs 
                                                        
           COMPILERS 
                                                        
                
                       A compiler is a program that reads a program written, in one language 
               i.e. the source language and translates it into an equivalent program in 
                       another language i.e. the target language. 
                        
            
            
            
            
                    Source                       Compiler                          Target 
                   program                                                        program 
            
            
            
                                                      Error 
                                                   Message 
            
           There are two parts of compilation: 
           1) Analysis    
           2) Synthesis 
            
           1)  The Analysis part breaks up the source program into constituent pieces and creates 
               an intermediate representation on the source program. 
           2) The Synthesis part constructs the desired target program from the intermediate 
            representation.  
                
           The Context of a Compiler 
           A source program may be divided into modules stored in separate files. A task of 
           collecting the source program is sometimes entrusted to a distinct program, called a 
           preprocessor. The target program created by the compiler may require further processing 
           before it can be run. 
            
            
            
            
            
            
            
            
            
            
            
            
            
                                                                      GATE/CS/CD/SLP/Ch.1_Notes/Pg.1