Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is three-address code in compiler design?
2.1.
General illustration
2.2.
Examples
3.
3 Address Code is used in Compiler Applications
3.1.
Intermediate Representation (IR)
3.2.
Code Optimization
3.3.
Register Allocation
3.4.
Code Generation
3.5.
Target Independence
4.
Implementation of Three Address Code
4.1.
Quadruple 
4.1.1.
Benefits of Quadrule
4.1.2.
Drawbacks of Quadrule
4.1.3.
Example
4.2.
Triples 
4.2.1.
Benefits of Triples
4.2.2.
Drawbacks of Triples 
4.2.3.
Example
4.3.
Indirect Triples 
4.3.1.
Benefits of Indirect Triples
4.3.2.
Drawbacks of Indirect Triples
4.3.3.
Example
5.
Frequently Asked Questions
5.1.
What are the three address codes?
5.2.
How do I create a 3 address code for declaration?
5.3.
What are three-address code operators?
5.4.
How do you write a 3 address code for a loop?
5.5.
What is 3 address code grammar?
6.
Conclusion
Last Updated: Apr 25, 2024
Easy

Three address code in Compiler

Author Aditya kumar
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Three-address code is simple to construct and convert to machine code. It employs just three places and one operator to describe an expression, and the value computed at each instruction is saved in a compiler-generated temporary variable. Three address codes in the compiler determine the sequence of operations.

Three Address Code

Also, see, Phases of Compiler

What is three-address code in compiler design?

Three-address code, often known as TAC or 3AC, is an intermediate code in computer science that is used by optimizing compilers to help in the implementation of code-improving transformations. At most, three operands can be used in a TAC instruction, which is normally made up of an assignment and a binary operator. For illustration, t1:= t2 + t3. Despite the possibility of instructions with fewer operands, the name of these statements comes from their use of three operands.

Since three-address code is used as an intermediate language within compilers, the operands will most likely not be physical memory addresses or processor registers but rather symbolic addresses that will be transformed into actual addresses during register allocation. Because three-address code is often generated by the compiler, operand names are frequently numbered sequentially.

General illustration

a = b op c 

 

Where a, b, or c stand for operands such as names, constants, compiler-generated temporaries, and op stands for the operator.

There can only be one operator on the right side of instruction in a three-address code; no built-up arithmetic expressions are allowed. As a result, a source-language statement like x+y*z might be translated into a three-address instruction sequence.

t₁=y*z
t₂=x+t₁

 

Where t₁ and t₂ are temporary names produced by the compiler. The unwinding of multi-operator arithmetic expressions and nested flow-of-control statements make three-address code ideal for target-code creation and optimization. Using names for the intermediate values computed by a computer makes it simple to rearrange three-address codes.

diagram of a general illustration of Three Address Code

Examples

1. Convert a = (-c * b) + (-c * d)   into three address code.

Solution

t₁ = -c
t₂ = b*t₁
t₃ = -c
t₄ = d * t₃
t₅ = t₂ + t₄
a = t₅

 

In the target program, t is utilized as a register.

2. For the following code, write the three address codes.

for(i = 1; i<=10; i++) { a[i]=x * 5; }

 

Solution

i=1
L:t1=x*5 
t2=&a
t3=sizeof(int)
t4=t3*i 
t5=t2+t4 
*t5=t1
i=i+1 
if i<10 goto L
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

3 Address Code is used in Compiler Applications

Three-address code (3AC) is a crucial concept in compiler design and has several important applications in the compilation process:

Intermediate Representation (IR)

3AC serves as an intermediate representation of the source code. It simplifies the complexity of high-level language constructs into a format that's easier to analyze, optimize, and translate into machine code. It provides a structured representation of program semantics that retains essential information while abstracting away from the specifics of the source language.

Code Optimization

3AC facilitates various optimization techniques such as constant folding, common subexpression elimination, dead code elimination, and loop optimizations. Because 3-address code is relatively simple and uniform, it becomes easier for compilers to apply optimization algorithms to improve the efficiency and performance of generated code.

Register Allocation

Register allocation is a critical optimization phase where the compiler assigns variables and temporary values to processor registers. 3AC can be transformed into a form suitable for register allocation algorithms, helping compilers efficiently utilize available hardware resources.

Code Generation

Once the code has been optimized and registered allocated, 3-address code can be translated into the target machine code. The simplicity and structured nature of 3AC make code generation more manageable and enable compilers to produce efficient and correct machine code for different target architectures.

Target Independence

3-address code abstracts away from the intricacies of specific hardware architectures, allowing compilers to generate code for various target platforms from the same intermediate representation. This level of abstraction makes it easier to port compilers across different architectures and optimize code for multiple platforms.

Implementation of Three Address Code

There are three different ways to express three address codes:

  • Quadruple
     
  • Triples
     
  • Indirect Triples

Quadruple 

It is a structure that has four fields: op, arg1, arg2, and result. The operator is denoted by op, arg1, and arg2 denote the operands, and the result is used to record the outcome of the expression.

These quadruples play a crucial role in breaking down high-level language statements into more digestible parts, facilitating compilation-stage analysis and optimization procedures.

Benefits of Quadrule

  • For global optimization, it's simple to restructure code.
     
  • Using a symbol table, one may rapidly get the value of temporary variables.

Drawbacks of Quadrule

  • There are a lot of temporary items.
     
  • The establishment of temporary variables adds to the time and space complexity.
     

Example

Convert a = -b * c + d  into three address codes.

The following is the three-address code:

t₁ = -b
t₂ = c + d
t₃ = t₁ * t₂
a = t₃

 

Quadruples are used to symbolize these statements:

#OpArg1Arg2Result
(0)unimusb-t₁
(1)+cdt₂
(2)*t₁t₂t₃
(3)=t₃-a

Triples 

Instead of using an additional temporary variable to represent a single action, a pointer to the triple is utilized when a reference to another triple's value is required. As a result, it only has three fields: op, arg1, and arg2.

Triples

Benefits of Triples

  • Triples make it easier to analyze and optimize code by disassembling difficult high-level language constructs into smaller, more manageable parts
     
  • Triples facilitate error, data flow, and control flow analysis of code, facilitating improved debugging and comprehension
     

Drawbacks of Triples
 

  • Temporaries are difficult to rearrange since they are implicit.
     
  • It's tough to optimize since it necessitates the relocation of intermediary code. When a triple is relocated, all triples that relate to it must likewise be changed. The symbol table entry can be accessed directly using the pointer.
     

Example

Convert a = -b * c + d into three address codes.

The following is the three-address code:

t₁ = -b 
t₂ = c + dM 
t₃ = t₁ * t₂
a = t₃

 

The following triples represent these statements:

#OpArg1Arg2
(0)unimusb-
(1)+cd
(2)*(0)(1)
(3)=(2)-

Also See, Top Down Parsing

Indirect Triples 

This approach employs a pointer to a list of all references to computations that are created and kept separately. Its usefulness is comparable to quadruple representation, however, it takes up less space. Temporaries are easy to rearrange since they are implicit.

Benefits of Indirect Triples

  • For languages that use dynamic memory allocation and pointer manipulation, indirect triples are essential for representing complex pointer operations and memory accesses
     
  • They simplify the intricate address calculations needed for nested structures, multi-dimensional arrays, and other memory architectures
     

Drawbacks of Indirect Triples

  • Indirect triples can increase the complexity of the intermediate representation and optimization phases of the compiler, complicating the design and implementation of the compiler
     
  • Due to the additional pointer dereferencing and memory access operations required by using indirect triples, there may be performance overhead that could slow down execution
     

Example

Convert a = b * – c + b * – c into three address codes.

The following is the three-address code:

t1 = uminus c
t2 = b * t1
t3 = uminus c
t4 = b * t3
t5 = t2 + t4
a = t5
#OpArg1Arg2
(14)unimusc-
(15)*(14)b
(16)unimusc-
(17)*(16)b
(18)+(15)(17)
(19)=a(18)

List of pointers to the table

#Statement
(0)(14)
(1)(15)
(2)(16)
(3)(17)
(4)(18)
(5)(19)

Frequently Asked Questions

What are the three address codes?

Three-address code is a simple, intermediate code to construct and convert to machine code. It employs just three places and one operator to describe an expression, and the value computed at each instruction is saved in a compiler-generated temporary variable. 

How do I create a 3 address code for declaration?

For declaration in 3-address code, assign memory addresses to variables: temp = allocate_memory(type, size).

What are three-address code operators?

Three-address code operators include arithmetic (+, -, *, /), logical (&&, ||), comparison (==, !=, <, >, <=, >=), and assignment (=).

How do you write a 3 address code for a loop?

Write a 3-address code for a loop using labels and conditional jumps:

L1: condition
  if_false L2
  loop_body
  goto L1
L2: next_instruction

What is 3 address code grammar?

3-address code grammar is a notation used in compiler design to represent intermediate code with three operands. It typically consists of instructions with the format: result = operand1 operator operand2, facilitating code optimization and translation into machine code.

Conclusion

In this article, we have discussed the three address codes. We have discussed how to implement three address codes and their need. We have also discussed three ways to implement three address codes: quadruple, triple, and indirect. So basically, the compiler uses three address codes to determine the sequence of operations.

Recommended Reading:

Check out some of the amazing Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingBasics of C, Basics of JavaOperating SystemsComputer Networks, etc., along with some Contests and Test Series only on Coding Ninjas Studio. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow. 

Happy Learning, Ninja!🥷✨

Previous article
The Intermediate language
Next article
Types and Declarations
Live masterclass