Wednesday, 13 May 2015

Six phases of Compiler with an Example

                  In this post, we will see six phases of compiler along with an example. We will start with tools required for any high level language program from its composing to its execution and then we will move to six phase of compilation.

Tools required for any High Level Language Program            

             For any program in High Level Language, we require following applications(softwares, tools).

1. Editor

2. Preprocessor
3. Compiler
4. Assembler
5. Linker
6. Loader

1. Editor

            Editor is a tool used to write a program. e.g. gedit, Notepad, Wordpad, MS Word etc.

2. Preprocessor

            Preprocessor expands the program. It adds preprocessor directives definitions in the program wherever they are called. e.g. header files, constant definitions, macros etc.

3. Compiler

            It is important application. It converts high level language program to low level language program(Assembly Language/Machine Language). It includes six phases, that we will see in the next part of this post.

4. Assembler

            It is a tool, which accepts assembly language code and converts it into the machine language(executable) code. This executable code has relocatable logical addresses.

5. Linker

            It is the tool which links program to the global variables.

6. Loader 

            Loader loads the program from secondary storage(Hard disk, usb storage etc.) to the main memory(RAM) to get executed by the processor. Loader uses the relocatable logical addresses and save the executable code into the actual address space in the main memory.

Six phases of Compiler:

           Now we will see six phases of compiler with an example.
           Let us take one statement which is common in many High Level Languages.
           Here, x,a,b,c are identifiers and =,+,* are operators.

1. Lexical Analyzer

           High level language program has several parts. e.g. keywords, macros, identifiers, operators etc. These are called as tokens. Lexical analyzer accepts the high level language program and tokenize it. These tokens are saved into the symbol table. To find out the tokens, lexical analyzer uses regular expressions(patterns). It matches the words from programs with regular expressions and identify whether which token it is.
            For above example,
            (For simplicity, I have mentioned like this. We can also write it as id op id1 op1 id2 op2 id3 where id,id1,id2,id3 represents identifiers and op,op1,op2 represents operators).

2. Syntax Analyzer(Parser)

             Syntax analyzer prepares a parse tree from input it got from above step.
Parse tree is useful to decide the sequence of operations or priorities of operations.
             For above example,

3. Semantic Analyzer

             Semantic analyzer checks the semantics of a expression(statement). This means, it checks whether all the entities in the statement are as per the rules or not. For example, we can not assign the new value to the constant or constant value should not be on the left hand side of a = operator. Such kinds of rules are checked by the semantic analyzer.
             Above example, is semantically correct.

4. Intermediate Code generator

            Intermediate code generator, generates code in terms of temporary variables.
            For above example, intermediate code will be as follows,

5. Code Optimizer 

          Code optimizer optimizes(in this case, reduces) the size of code if it is possible.
          For above example,

6. Code Generator

          Code generator generates the assembly code in terms of registers from the input it got from above steps.
        For above example (suppose id1,id2,id3 are saved to registers AX,BX,CX respectively), then assembly code will be

Check Other Posts on Compiler

Next: LEX and YACC programs for arithmetic expression evaluation

Previous: Common Lisp Programming Tutorial with Examples