Compiler is a translator or system software that take input as Program written in c,c++ and convert it into machine level language.That process is complex and difficult task that is not possible to whole conversion process in one go (or one phase).
So that Process of compilation that convert source code into assembly code is divided into sub-task that is called phase.One phase output is input of another phase.
Different phase of compiler or Structure of compiler
- Lexical analysis.
- Syntax Analysis.
- Semantic Analysis.
- Intermediate code Generation.
- Code optimization.
- Code generation.
Symbol table management and error handling also done during compilation process.
Source program is input for this phase and it read source program character by character and group them into tokens .
Put tokens into symbol table.
Example
what is output produce by lexical analysis phase on input string b=a+4.
Solution
Find Token and their type (because main aim of phase lexical analysis is to convert source code into tokens.
IDENTIFIER a,b
ASSIGN OPERATOR =
ADD OPERATOR +
CONSTANT 4
After finding out the tokens and store them into symbol table.
Syntax Analysis
That is second phase of compiler that is also called parser. Syntax Analyzer creates the syntactic structure of the program and their relationship.parser construct parse tree from various token obtained from lexical analyzer.
Mainly two type of parser
- Top-down parser.
- Bottom-up parser.
Example
construct parse tree for the statement A=B*C+20
Solution
First find Token of the statement
id1 A
id2 B
id3 C
Parse tree of the statement
Semantic Analysis
Semantic refers to the meaning of a program . Semantic Analysis performed function that are
- Type Checking
- Implicit type conversion.
- Conversion from infix to post-fix.
- Storing type in Symbol table.
- executing arithmetic expression.
In type checking check or verify operator and operand that check type compatibility between oprator and operand.
changing one type into another automatically when datatype of operands of an operator mismatch.
SDT(Syntax Directed Translation)
Grammar+Semantic rules=SDT.
parse tree->Semantic Analysis->Annotated parse tree.
Grammar
S->S#A|A
A->A&B|B
B->id
Rules
S.val=S.val*A.val;
A.val=A.val+B.val;
B.val=id.val;
Rules tell about the action. # means perform *.
Example Evaluate 5#3&4.
Solution
5*3+4=19.
Intermediate Code Generation
After checking type in previous phase that code is converted into intermediate code. That is machine Independent code.So that is executed on different platform. It make code optimizer task easy.
Types of Intermediate code representation
- Syntax tree.
- Post-fix Notation.
- Direct Acyclic Graph.
- Three Address code(Quadruples,Triples,Indirect triples
Example
Translate (a+b) int post-fix form.
Solution
ab+
using stack convert infix into postfix.
Code optimization
It convert Intermediate representation of source program into efficient code(faster running code).That phase use technique to improve the efficiency of object code.Increase in efficiency is concerned with size and running time of object program.
- Local optimization.
- Loop optimization.
- Global data flow Analysis.
Local optimization
- common sub-expression elimination.
- Constant folding.
- Dead code Elimination.
Loop optimization
- code motion
- Induction variable elimination.
- reduction in strength.
Global data flow Analysis
Analysis the flow of data from one block to another block of a program. The whole program is divided into block and make flow graph and apply optimization called data flow analysis.
Code Generation
That phase convert optimize code into Assembly code.It allocates memory locations for variable in the program.output of the code generation is
- Absolute code.
- Relocatable code.
- Assembly code.
It is the final phase in the process of compilation.It take intermediate code as input and convert into Assembly code.
0 Comments