search
Log In
63 votes
9.3k views

For a C program accessing $\mathbf{X[i] [j] [k]}$, the following intermediate code is generated by a compiler. Assume that the size of an integer is $32$ bits and the size of a character is $8$ bits. 

t0 = i ∗ 1024 
t1 = j ∗ 32
t2 = k ∗ 4 
t3 = t1 + t0 
t4 = t3 + t2 
t5 = X[t4]

Which one of the following statements about the source code for the C program is CORRECT?

  1. $\mathbf{X}$ is declared as "int $\mathbf{X[32] [32] [8]}$.
  2. $\mathbf{X}$ is declared as "int $\mathbf{X[4] [1024] [32]}$.
  3. $\mathbf{X}$ is declared as "char $\mathbf{X[4] [32] [8]}$.
  4. $\mathbf{X}$ is declared as "char $\mathbf{X[32] [16] [2]}$.
in Compiler Design
edited by
9.3k views
4
Can it be written like this?

t5 = X[ t4 ]

     = X [ t3 ] [ t2 ]

     = X [ to ] [ t1 ] [ t2 ]

     = X [ i*1024 ][  j *32 ][ k * 4 ]

     = X [ i * ( j * ( k * 4 ) ) ][ j * ( k * 4 )][ k * 4 ]  ( multiplication by 4 is due to 32 bit ( or 4 B) integer )

From here clearly option A) is the answer.
5

$(i\times j\times k+ j\times k+ k)\times 4\ bytes$

$Put\ A)\ values\ "intX[32][32][8]"\ above$

$=(32\times 32\times 8+32\times 8+8)\times 4$

$=33824$


$t5=X[t4]$

$t4=t3+t2$

     $=t0+t1+k\times 4$

     $=i\times 1024+j\times 32+k\times 4$

$Put\ A)\ values\ "intX[32][32][8]"\ in\ 't4'$

$=32\times 1024+ 32\times 32+ 8\times 4$

$=33824$


$Ans: A$

In order to visualize what exactly is happening: Refer here

9 Answers

78 votes
 
Best answer

$k$ is multiplied by $4$, means sizeof(dataype) is int.
$j$ is multiplied by $32$, means the inner most dimension of array is $32/4 = 8$ (we have to divide by the size of the inner dimension- which here is a simple integer)
$i$ is multiplied by $1024$, means the second dimension of array is $1024/32 = 32$ ($32 = 8*4$ is the size of the inner dimension here)

So, (A) is correct. The first dimension is not needed for code generation and that is why in C language while passing an array to a function, we can omit the value of the first dimension but not any others.


We can also do as follows:

$X[i][j][k] = *(*(*(X + i) + j) + k)$

In Integer arithmetic, this equals

$*(*(*(X + i * sizeof(*X) ) + j * sizeof(**X) + k * sizeof(***X) )$

as for every add to a pointer we have to multiply the size of the pointed value (to get a valid address)

So, from the given code we get

$sizeof(***X) = 4, -$ int
$sizeof(**X) = 32 -$ int  array  of size $8$
$sizeof(*X) = 1024 - 2$ $D$ int array of size $[32]$ havinf size of inner $1D$ array $32$.

So, the inner dimensions must be $32$ and $8$ and type must be integer. So, only option A matches.


edited by
0
Any Reference link for this Answer?
0
Can anyone elaborate further did not understand
0
How is r1 calculated ?
2
See now..
0
@Das if u mean dimension one - that cant be calculated.. only assumed from choice..
0
Thank you Sir :)
0
Sir can u explain why we concluded that since k is multiplied by 4 the data type is int ????
0
Difference between option A) and C)?

Why C) cannot be answer?
0
Exactly... why c is wrong? It also has its outer dimensions 32 and 8 only
5

@srestha 

why c is wrong? It also has its outer dimensions 32 and 8 only

This is because 

Inner dimensions must be 32 and 8 and type must be integer

And option C is char type..so wrong.

0
@Arjun Suresh

Why only k is multiplied by 4 (size of each element), If 4 is size of each element of the array, then why multiply k alone, why not all the remaining elements in the 2D and 1D arrays (1024*i+32*j number of elements) we have surpassed to reach the desired element.
0
why the last element is 8. please explain the logic
3

Suppose given dimensions are X[a][b][c] and you have to find element at X[i][j][k] It will be done like

(i * b * c * size) + (j * c * size) + (k *size). Now in the code k is multiplied by 4 so we got size as 4. Now go in reverse way to calculate c (innermost dimension) we have 

t1 = j ∗ 32 ----1

Our second term (j * c * size) ----2

c*size=32 and we know size is 4 so c is 8.

same we get b as 32.

Hope you got it. :)

0

For those asking about why it's an integer array, from the second explanation @Arjun da has given, since $sizeof(***X) = 4$, and $sizeof$ returns the size of a type in bytes, 4 bytes = 32 bits = integer type.

0

@Arjun

@Vikrant Singh

why we are access array like this,

actually 3d array address resolution  should be like,

FORMULA

**Row Major and Column Major for 3-D Array:
**ROW MAJOR OF A[I, J, K]=B+W[(K-Ko)*RC+(I-Io)*C+(J-Jo)] 
COLUMN MAJOR OF A[I, J, K]=B+W[(K-Ko)*RC+(I-Io)+(J-Jo)*R]**

WHERE:
R=ROW
C=Column
K=Weidth
Ko=Lower Bound of Width
Io=Lower Bound of Row
Jo=Lower Bound of Column**

https://stackoverflow.com/questions/33463594/element-address-in-3-dimensional-array

51 votes

X is of type integer and dimensions of X are r1 X r2 X r3.

 value of r2 = 32

r3 = 8

4
what can be said about r1?
0
thanx for this answer.
0
So, if here t2= k*1 instead of k*4 then answer would be for Char array, is it?
38 votes

For a while, assume that this 3-D array is of int type.

If I write int k = X[i][j][k]; Means I am looking for a particular integer value which is stored at the location *(X[i][j]+k) = *(*(X[i]+j)+k) = *(*(*(X+i)+j)+k)

Lets take an example of 1D array

 if there is one 1D array A[10,20,30,40], Suppose, A is stored at 1000 location, intsize=4B 
and If I write int k = A[2], means i am looking for an integer which is stored at *(A+2) location.

K = A[2]; Lets write intermediate code for this.

A[j]=*(Base Address + j*intsize)

A[j] = *(A + j*intsize) = *( 1000 + 2*4) = *(1008) = 30 ( our element)

t1 = j*intsize
t2 = baseAddress + t1
k = *(t2)  it will give 30 to us.

Now, take an example of 2D array.

Int k = B[3][5]; It will also assign k with an integer value. We have to find the location of that integer.

Suppose array B has x rows and y columns, and stored in memory in ROW MAJOR Order.

k = B[i][j] = *(B +([i*no.Of_Cols]+j)*intsize)
k = B[3][5] = *(B + ((3*y) + 5)*4)
Suppose number of rows = 30, number of columns =20
k=B[3][4]= *(Base address + ((3*20)+5)*4) = *(B.A + 3*20*4 + 5*4) = *(1000 + 240+ 20) = *(1260).
To access, B[3][5], i can also write B[260/4] = B[65] = *(B + 65*4) = *(1000 + 260) = *(1260)
Intermediate code for k = B[i][j];

t1 = j*intsize     = 5*4 = 20
t2 = i*#cols*instize  = 3*20*4 = 240
t3 = t1+t2  = 260
k = B[t3]; *(1000 + 260) = *(1260);

PS: Assume Array B is stored at memory location 1000.

Let's take 3-D array now.

int k = C[i][j][k].

It means we have to cross, i 2D arrays, j 1D arrays, and k elements to reach our required element.

= B.A + (i_2D_arrays*no._elements_In_1_2D_Array + j*no._elements_in_1_1D_Array + k)*intsize

=B.A + (i_2D_arrays*no._elements_In_1_2D_Array*instsize + j*no._elements_in_1_1D_Array*intsize + k*intsize)

Now, we can see in question that k is multiplied by 4, hence array X is of int type. options (C) and (D) are eliminated here.

j is multiplied by 32, and this calculation equals to j*no._elements_in_1_1D_Array*intsize=j*32 = j*8*4
it means there are 8 elements in one 1D array.

int X[][][8];  so far so good to eliminate option B.


Let's go further.

i*1024 = i*no._elements_In_1_2D_Array*intsize

number of columns in 2D arrays = 8
number of rows in 2D arrays 256/8 = 32

Hence, there 2D array is of [32][8] size.

i*1024 = i*32*8*4 = i is number of 2D arrays, 32x8 is size of one D array. 

We can't calculate number of 2D arrays by the given code, and that is not even required for our question.

So, the answer is (A). 


edited by
0
@Manu Thanks lot :)
0
How 256/8 while calculating no. Of rows @Manu
2

This is the best answer.

But @Manu Thakur one question ,that is how you  can calculate number of columns in 2d array is 8 from number of elements of 1d array?

0
This should be the selected answer.
0
Thanks for such a wonderful answer.
0
Clearly explained
11 votes

The final expression can be simplified in form ofi, j and k by following the intermediate code steps in reverse order

t5 = X[t4]
   = X[t3 + t2]
   = X[t1 + t0 + t2]
   = X[i*1024 + j*32 + k*4]
   = X + i*1024 + j*32 + k*4 

Since k is multiplied by 4, the array must be an int array. We are left with 2 choices (A and B) among the 4 given choices. X[i][j][k]'th element in one dimensional array is equivalent to X[i*M*L + j*L + k]'th element in one dimensional array (Note that multi-dimensional arrays are stored in row major order in C). So we get following equations

j*L*4 = j*32, we get L = 8 (4 is the sizeof(int))
i*1024 = i*M*L*4, we get M = 1024/32 = 32

Therefore option A is the only correct option as M and L are 32 and 8 respectively only in option A.

0
Great and simple explanation !
0
What are M and L here?
0
It's size of data type mentioned in question.i.e., 32 and 8
0

@Regina Phalange Ma'am why we are multiply j with L  like j*L and for i with M*L

Also how are you evaluating this   X + i*1024 + j*32 + k*4 to X[i*M*L + j*L + k]?

from where did this X[i*M*L + j*L + k] came?

0
This is answer for me. Thanks

If given permission , I would have up voted answer at least 10 times
10 votes

Answer - A

Explanation - 

Element needed - X[i][j][k]

A 3D array is a collection of 2D arrays and a 2D array is a collection of 1D arrays, and a 1D array is a collection of elements.

So, we need to first cross the required no. of 2D arrays(no. of elements in 1 2D array * i), then the required no. of 1D arrays(no. of elements in 1 1D array(no. of rows in 1 2D array) * j) in our reached 2D array, and then the required no. of elements in our reached 1D array(k).

1. We have t0 = i * 1024, which means that there are 1024 elements in 1 2D array.

2. We have t1 = j * 32, which means that we have 32 elements in 1 1D array of our 2D arrays or in other words, the no. of rows of our 2D array is 32, so the no. of columns can easily be found by 1024 / 32 = 32. 

So now we have the dimensions of our 2D arrays = 32*32.

so clearly our answer is A (no other close option).

elaborating further, 

3. We have calculated t3 of our 3-address code = (i * (32*32)) + (j * 32) + k.

4.We now need to multiply the above expression with the size of the datatype. 

Since we have t2 = k * 4, it clearly means that the size of our datatype of each element is 4 bytes, hence an int. 

And the expression t4 of our 3-address code in high level language is - ((i * (32*32)) + (j * 32) + k) * 4

5. t5 gives the specific element. 

Conclusion - our required 3D array is - x[32][32][8] and it is of type integer. 

Note - There is no way of finding out the 3rd dimension of our 3D array, here 8 with the help of our 3-address code, since its not required in the calculation of an element's location.

0
@ ravi_ssj4

Sir, I think u have made a mistake in point 2. j is the number of rows and 32 is the number of elements in each row, although this should not effect final answer.

And I could not understand why they have multiplied k by 4. If it is size of each element of the array, then why multiply k alone, why not all the remaining elements in the 2D and 1D arrays we have surpassed to reach the desired element.
6 votes
$int\ X$ $\underbrace{32}$ $\underbrace{32}$ $\underbrace{8}$
$Assume$ $streets$ $apartments$ $buildings$

According to question we need to find: $loc\ X[i][j][k]$

Size of int$:4B$

$Analogy:$ You want to go and meet your friend who lives in $k^{th}$ building of $j^{th}$ apartment which is on $i^{th}$ street.

1. First you will cross $i$ streets which contains $32$ apartments and in each apartment there are $8$ buildings

$\therefore\ 32\times 8\times 4=1024$

Hence $t_{0}=i\times 1024$ 

2. Now you will cross $j$ apartments which contains $8$ buildings

$\therefore\  8\times 4=32$

Hence $t_{1}=j\times 32$ 

3. Now you will cross $k$ buildings

Hence $t_{2}=k\times 4$ 

Rest of the part everyone knows :)

3
Hmmm.. kiran sir haan! :)
4 votes

Size of an integer = 32 bits = 4 Bytes
Size of a character = 8 bits = 1 Byte
Let array be

            type x[A] [B] [C]
type  may be integer / character

we want  t5=x[t0+t1+t2]=x[i*1024 + j*32 + k*4 ] element,

From t0 = i *1024,
we can conclude that

          B * C * (size of type) = 1024
From t1 = j *32, we can conclude that

         C *(size of type) = 32
From t2 = k *4, we can conclude that   

         (size of type) = 4
therefore  type = int
                    C *4 = 32    => C = 8
                    B *8 * 4 = 1024 => B = 32

Choice (A)

0 votes

Prerequisite: The visualisation of multidimensional arrays.


How do we get to $A[i][j]$ ? (in RMO)

From the base address, we skip $i$ rows and $j$ columns. This is quite well known.

See this or this for example.

 

Actually, a better perspective is to see it as skipping $i$ arrays and $j$ elements.

An even better perspective is to look at it as skipping $i$ $1D$ arrays, and $j$ elements.

 

By extending this, $A[i][j][k]$ is nothing but skipping $i$ $2D$ arrays, $j$ $1D$ arrays and $k$ elements. You can extend this generalised perspective to any number of dimensions.

 

Now,

t0 = i ∗ 1024 
t1 = j ∗ 32
t2 = k ∗ 4 

This is nothing but "skipping". Start from the innermost index. We're skipping $k$ by multiples of $4$. So, single-elements in the array occupy space of $4$ (Bytes). Hence, we're dealing with ints.

 

We're skipping $j$ by multiples of $32$. This means the $1D$ "sub-arrays" are of size $32$ (Bytes).

//Visualisation of multidimensional arrays is needed. If you don't know how to picturise it, I'll draw that in the comments.

 

Size of the $1D$ array = $32$ .

Number of elements = $\frac{32}{4}=8$

So, the last array subscript has a size 8.

 

With this knowledge, Option A is the answer.

But let's continue.

 

We're skipping $i$ by multiples of $1024$. This means the $2D$ "sub-arrays" are of size $1024$ (Bytes).

Number of elements in $2D$ subarrays = $\frac{1024}{32}=32$

Hence, there are $32$ $1D$ subarrays.

So the middle subscript is of size 32.

 

Nothing can be concluded about the first subscript. (Why? Hint: we don't know the total number of 2D subarrays)

 

So, we conclude the array must have been declared like: $int X[?][32][8]$

Answer:

Related questions

32 votes
7 answers
1
3k views
Consider the expression tree shown. Each leaf represents a numerical value, which can either be $0$ or $1$. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.
asked Sep 28, 2014 in Compiler Design jothee 3k views
14 votes
3 answers
2
2.3k views
Consider the grammar defined by the following production rules, with two operators $∗$ and $+$ $S\:\to\:T∗P$ $T\:\to\:U\mid T∗U$ $P\:\to\:Q+P\mid Q$ $Q\:\to Id$ $U\:\to Id$ Which one of the following is TRUE? $ +$ is left associative, while $∗$ is right associative $ +$ is right associative, while $∗$ is left associative Both $+$ and $∗$ are right associative Both $+$ and $∗$ are left associative
asked Sep 28, 2014 in Compiler Design jothee 2.3k views
80 votes
4 answers
3
6.3k views
Suppose $n$ and $p$ are unsigned int variables in a C program. We wish to set p to $^nC_3$. If $n$ is large, which one of the following statements is most likely to set p correctly? $p = n * (n-1) * (n-2) / 6;$ $p = n * (n-1) / 2 * (n-2) / 3;$ $p = n * (n-1) / 3 * (n-2) / 2;$ $p = n * (n-1) * (n-2) / 6.0;$
asked Sep 28, 2014 in Programming jothee 6.3k views
18 votes
3 answers
4
2.7k views
Which one of the following is NOT performed during compilation? Dynamic memory allocation Type checking Symbol table management Inline expansion
asked Sep 28, 2014 in Compiler Design jothee 2.7k views
...