Compiler convert the parse tree into intermediate language code. A language between source and target code. Use register name but has unlimited.
It is not possible for compiler to generate machine code directly in one phase first convert source program code into intermediate code.
Reason to convert source code into Intermediate code
- Machine Independent code So can executed on different platform.
- The task of code optimization easy.
- Because code is optimize so efficient code generation.
Intermediate code representation
Different way to represent intermediate code that are
- Abstract Syntax tree.
- Directed Acyclic graph.
- Post-fix Notation.
- 3-Address code.
Abstract Syntax Tree
It contains operands at leaf node and operator as interior node.Syntax tree is condensed form of the parse tree.It does not contain any redundant information.
Example Draw Syntax tree of Expression p*q+r
First evaluate p*q because * has high precedence than +. Syntax tree cannot be changed to parse tree.
Postfix Notation
That is also known as reverse Polish notation .Operator are written after their operands.Infix expression is converted into postfix using stack.To solve particular expression first convert into infix to postfix using stack.
Infix
(p+q)
After conversion postfix
pq+
Example
calculate the value of postfix expression 23+4*3*
Solution
scanned Symbol stack
2 2
3 2,3
+ 5
4 5,4
* 20
3 20,3
* 60
So solution of postfix expression is 60.Expression Evaluated using stack.
Steps Evaluation postfix expression
- Step 1 : Add right parenthesis at the end of the expression.
- Step 2: Scan expression left to right until right parenthesis not occurred.
- Step 3: If operand occurred put it in stack.
- Step 4: if operator occur.Remove top two element from the stack .Evaluate top two element.Again store result in stack.
- step 5. Set result equal to the top element of the stack.
- Exit.
Directed Acyclic graph
Directed acyclic graph represent a single basic block.That is graph with no cycle which show how value computed by each statement in basic block is used in subsequent statement in the block.
Leaf node are labeled by identifier.
Interior node contain operator or computed value.
Example
Construct DAG for the following instruction.
p=a+b.
q=p+c.
Solution
3-Address code
As their name in Three address code three addresses are used to represent any statement two address for statement and one address for result.
Instruction used in Three address operator
- Assignment Instruction.That is p=a+b.
- Copy Instruction q=p.
- Unconditional Jump goto L.
- Conditional Jump if a goto L.
- Procedure calls param a call f return y.
Representation of 3-Address Statement
- Quadruples.
- Triples.
- Indirect Triples.
Quadruples
In Quadruple structure which contain 4 fields
operator
Argument 1
Argument 2
Result
For example
Find the 3-Address code of the statement p+q*r+d
Solution
3-Address code of statement
T1=q*r
T2=p+T1
T3=T2+d
Triples
In Triples structure which contain 3 field
operator
Argument 1
Argument 2
Temporary variable are not used in triples.Use a number in parenthesis to represent pointer to that particular record of symbol table.
For example
Find the 3-Address code of the statement p+q*r+d
Solution
position operator argument 1 argument 2
(0) * q r
(1) + p (0)
(2) + (1) d
Here (0) represent a pointer which refer result q*r.
Here (1) represent a pointer which refer result (0) added with p.
Here (2) represent a pointer which refer result(1) added with d.
Indirect Triples
All the pointers used in triples are indexed such that one pointer will reference another pointer and that pointer will consist of the triple.
Two tables are maintain in Indirect Triples
For example
Find the 3-Address code of the statement p+q*r+d
Solution
position statement
(0) (100)
(1) (101)
(2) (102)
Position operator argument 1 argument 2
(100) * q r
(101) + p (100)
(102) + (101) d
representation in compiler){kind=link}
0 Comments