Notes of Compiler Design
                         BLC-502
                           UNIT-1
       ForDiploma in Computer Engineering
                   Final Year-2020-21
                             By
                          Salim Istyaq
                       (Assistant Professor)
                   Electrical Engineering Section
                      University Polytechnic
                  A.M.U. Aligarh-202002, U.P. India
                  Email: saleemishtiyak@gmail.com
                                                      1
            Introduction to compilers:
            TRANSLATOR:
            It is a program that performs the following two important tasks :-
            1) Translating users oriented language program (i.e. source program) into an equivalent machine
            oriented language program (i.e. target program).
            2)  Providing diagnostic  messages  (i.e. error  detection)  whenever  specification  of  the  source
            language are violated by the programmer.
                               Data                 Result
                                            HLL
                                                            Machine Oriented Program
            Source Program        Translator                                              Result
                                                                  //////////////
            COMPILER:
            Compiler is a program that reads a program written in HLL and translates it into an equivalent
            machine language program. As an important part of this, compiler reports to its user the presence of
            errors in the source program.
                                   Compiler
            HLL Program            Compiler     Machine oriented Program
            There   are two parts of compilation process
            1) Analysis part
            2) Synthesis part
            ANALYSIS: The analysispart breaks up the source program into constituent pieces and creates an
            intermediate representation  of  the  source  program.  It  is  also  concerned  with  determining  the
            meaning. We must know the rules according to which the source language text is constructed. In
            order to derive meaning, we must know the rule according to which the source language statements
            are constructed. In other words, we must know the grammar of the source language. Further we
            should also know how to determine the meaning of a statement once its grammatical structure is
            real. These rules of grammar and rules of meaning are called syntax and semantics of the translated
            program language.
                                                                                                            2
      SYNTHESIS: Synthesis  part  constructs  the  desired  target  program  from  an  intermediate
      representation.
      TOKEN:
      Lines  of  program  can  be  positioned  into  subsequences  called  tokens.  Token  is  a  sequence  of
      characters whose significance is possessed collectively rather than individually.
      Five different types of tokens are:-
         1) Constants : 1,2,3,0, 4.5
         2) Identifier : x, sum, i, j, fact, etc
         3) Operator symbols : +,-,  =,   **,  :=
         4) Keywords : for, if , while
         5) Punctuation symbol: parentheses, brackets, comma, semicolon.
      The analysis phase consists of three parts :-
      1) LEXICAL ANALYSIS OR (LINEAR ANALYSIS):
      It performs a micro level examination of the input text in order to identify the lexical unit occurring
      in it & to determine their syntax categories. The stream of characters making up the source program
      is read from left to right and grouped into tokens. This process is called scanning. For ex. Position =
      initial + rate * 60.
      The following statements in the above statement appear:
         1) The identifier position
         2) The assignment symbol
         3) The identifier initial
         4) The operator +
         5) The identifier rate
         6) The operator *
         7) The number 60
      The other functions of lexical analysis are:
           1) To classify the token into their respective syntax categories.
           2) To  built  the  tables  for  particular  syntax  categories.    For  e.g.  Tables  of  simple
           variables, dimension variable or table of constant etc.
       2) SYNTAX ANALYSIS:
       It  determines  the  syntactic  structure  at  the  input  statements.  To  check  the validity  of  the
       statement in the source language tokens, are grouped hierarchically into nested collections with
       collective meaning. The best way to represent the syntactic structure is to perform a syntax tree
       also known as parse tree.
                                                 3
                              =    position
                         Initial     +
                                                * Rate
                                                            60
                      e.g. :   A=B+I
                                              =    A
                                              B       +
                                                                   I
              SEMANTICANALYSIS:
              It performs certain checks on semantic errors to ensure that components of a program fit together
              meaning fully. It uses the structure determined by the syntax analysis phase to identify the operators
              and operand of expressions and statements i.e. processing of declarative statements.
              DECLARATIVESTATEMENTS:
              Items of information are edited to the various lexical tables. For e.g. the type, length and dimensions
              of variable.
              PROCESSING OF EXECUTABLE STATEMENT:
              Information from the lexical tables is used to determine the syntactic validity of the input statement.
              An important component of semantic analysis is type checking. Here a compiler checks that each
              operator  has operand  that  is permitted by  the  source  language specification. Semantic  analysis
              reveals certain aspects of the program structure which are important for the synthesis of the target
              text information regarding these aspects is put into structure tables for appropriate use later on.
                                                              ↓ Source Program
                             Lexical Errors     
                                                       Lexical Analysis                                     Symbol table
                                                                        ↓ Token
                            Syntax Errors       
                                                    Syntax Analysis or Parsing
                                                                                                           Constant Table
                                                                        ↓  Syntax Tree
                           Semantic Errors           Semantic Analysis
                                                                                                        Dimension Table  etc.
                                                                        ↓ Intermediate Code (to synthesis Phase)
                                                                                                                              4