Translation of Array References in Compiler Design

Translation of Array References

We can access the elements of an array stored in consecutive blocks very easily and quickly. In a programming language like C and Java, the size of an array is one less than the number of the element stored in an array. We can categorize an array mainly in two types:

  • One Dimensional Array
  • Multi-Dimensional Array

The location of the ith element of an array ‘A’ having width ‘w’ of each array element is:

base + i * w

Here, the base is the relative address of the storage allocated for the array.

One Dimensional Array

The element of a one-dimensional array is numbered in the form of low, low + 1, and so on. We can rewrite the above formula for the ith element of an array as follows:

A[low] = base + (i – low) * w

The above expression can also be written as:

i * w + (base – low * w)

Multi-Dimensional Array

We can store the multi-dimensional array in two types:

  1. Row-Major
  2. Column-Major

Row-major: A[1, 1], A[1, 2], A[1,3], A[2, 1], A[2, 2], A[2, 3]

Column-major: A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3]

Translation Scheme for Array Elements

The translation scheme for an array element for the three-address statement is given below. This scheme consists of production and semantic action.

L.addr: Temporary variable

L.type: Pointer to symbol table entry for the array name

L.array: Array name

Production RuleSemantic Action
S => id = E;     |    L = E;{ gen ( top.get (id.lexeme) ‘=’  E.addr ); } {gen(L.array.base‘[‘ L.addr ‘]’ ‘=’ 0 E.addr ); }
E => E1 + E2          | id        | L    {E.addr = new Temp (); gen(E.addr ‘=’ E1.addr ‘+’ E2.addr ); }   {E.addr = top.get(id.lexeme ); }    {E.addr = new Temp (); gen(E.addr ‘=’ L.array.base‘[‘ L.addr ‘]’);}
L => id [ E ]{L.array = top.get(id.lexeme ); L.type = L.array.type.elem ; L.addr = new Temp (); gen (L.addr ‘=’ E.addr ‘*’ L.type.width ); }
L => L1 [ E ]{L.array = L1.array ; L.type = L1.type .elem ; t = new Temp (); L.addr = new Temp (); gen( t ‘=’ E.addr ‘*’ L.type.width ); gen(L.addr ‘=’ L1.addr ‘+’ t ); }

Related Topics

Three-Address Code

Three-Address Code If there is at most one operator on the right side of the instruction, then the instruction will be the three-address code so that no arithmetic expressions are permitted....

2 minutes read.

Parsing in Compiler Design

Parsing is the term used to describe the process of converting data between different formats. The parser can carry out this operation. The parser is a part of the translator...

4 minutes read.

Code Generation

Code Generation The last phase of the compiler is code generation. It is the compiler's back-end that makes multiple passes over the IR before generating the target program. The code generator's...

4 minutes read.

Syntax Analysis Compiler Design

Syntax Analysis This article will describe the parsing method used in the compiler. The grammatical rule of programming language can be constructed with the help of context-free grammars or BNF (Backus–Naur...

3 minutes read.

LEX

LEX Lex is a tool/computer program that generates a Lexical analyzer. Lex is developed by Vern Paxson in C around 1987. Lex works together with the YACC parser generator. It allows...

3 minutes read.

Regular Expression | Compiler Design

Regular Expression A regular expression is a set of patterns that can match a character or string. It can also match alternative characters or strings. The grammar defined by the regular...

3 minutes read.

LR Parser Compiler Design

LR Parser LR parsing is a type of bottom-up parsing that is used to parse the large class of grammars. Here "L" stands for left-to-right scanning of the input "R" stands...

6 minutes read.

Optimization of Basic Blocks in Compiler Design

Optimization of Basic Blocks We can apply the optimization process on a basic block. While optimization, there is no need to change the set of expressions computed by the block. The basic...

3 minutes read.

Machine-Independent Optimizations in Compiler Design

Machine-Independent Optimizations The main aim of machine-independent optimization is to improve the generated intermediate code so that compiler can get better target code. Eliminating unwanted code from the object code or replacing...

8 minutes read.

Syntax-Directed Translation

Syntax-Directed Translation A context-free-grammar with some additional rules is known as a syntax-directed definition. In SDT, attributes are associated with grammar symbols and rules are associated with productions. The attributes can...

3 minutes read.

Derivation and Parse Tree in Compiler Design

Derivation and Parse Tree In this article, we will learn Derivation and Parse Tree. Derivations The parse tree can be constructed by taking a derivational view in which production is treated as rewriting...

4 minutes read.

LR Parser in Compiler Design

LR Parser The most popular type of bottom-up parsing is LR(K) parsing. The LR() parser scans the input from left – to – right, which is the actual abbreviation of L...

2 minutes read.

Switch Case Statement Compiler Design

Case Statement The “case” or “switch” statement is available in various languages. The following is the syntax for the case statement: switch (E)  {             case V1: S1             case V2: S2 ...

1 minute read.

Storage Allocation

Storage Allocation The storage allocation represents memory management. The allocation of memory can be done in the following ways: Static AllocationStack AllocationHeap Management Static Allocation: It is a procedure used for the allocation of...

1 minute read.

Basic Blocks and Flow Graphs in Compiler Design

Basic Blocks and Flow Graphs In this section, we are going to learn how to work with basic block and flow graphs in compiler design. Basic Block The basic block is a set...

3 minutes read.

Phases of Compiler

Phases of Compiler The compilation process of a compiler goes through various phases. Each phase of the compiler takes the output from the previous as an input. Here we will see all...

2 minutes read.

Bottom-Up Parsing in Compiler Design

Bottom-Up Parsing A bottom-up parsing constructs the parse tree for an input string beginning from the bottom (the leaves) and moves to work towards the top (the root). Bottom-up parsing is...

6 minutes read.

Compiler Design Tutorial

Our compiler design tutorial will provide all the information about compiler from basic to advanced level. This compiler tutorial will help the student for their semester as well as for...

3 minutes read.

CLR Parsing Compiler Design

CLR Parsing CLR parsing refers to the canonical lookahead. We will use the canonical collection of LR(1) items for the construction of the CLR(1) parsing table. Generally, CLR(1) parsing has more...

6 minutes read.

Translation of Array References in Compiler Design

Translation of Array References We can access the elements of an array stored in consecutive blocks very easily and quickly. In a programming language like C and Java, the size of...

2 minutes read.