Compiler Design Test 1

Result

Compiler Design Test 1

Score
-
out of -
Rank
-
out of -

TIME Taken - -

SHARING IS CARING

If our Website helped you a little, then kindly spread our voice using Social Networks. Spread our word to your readers, friends, teachers, students & all those close ones who deserve to know what you know now.

Weekly Quiz Competition

Question 1
2 / -0.33

Consider the following syntax directed definition:
Production
Semantic Rule
T → FT’
T’.val = F.val
T’ → * FT’₁
T’.val = T’₁.val * F.val

The above SDD is

A
Synthesized

B
Inherited

C
S – attributed

D
L – attributed

Solution

Synthesized attributes:
A Synthesized attribute is an attribute of the non-terminal on the left-hand side of a production. Synthesized attributes represent information that is being passed up the parse tree. The attribute can take value only from its children.
S-attributed SDT
If an SDT uses only synthesized attributes, it is called as S-attributed.
T → FT’ {T’.val = F.val} // it is S-attributed
T’ → * FT’1 {T’.val = T’1.val * F.val} // // it is not S-attributed
Inherited attributes:
An attribute of a nonterminal on the right-hand side of a production is called an inherited attribute. The attribute can take value either from its parent or from its siblings.
L-attributed SDT
If an SDT uses both synthesized attributes and inherited attributes with a restriction that inherited attribute can inherit values from left siblings only, it is called as L-attributed SDT.
T → FT’ {T’.val = F.val} // it is L-attributed
T’ → * FT’1 {T’.val = T’1.val * F.val} // // it is L-attributed
Therefore option 4 is correct
Question 2
2 / -0.33

Consider the following grammar where capital letter is non-terminal and smaller letter are terminal
X → P Q R | y z Q | Q x | Q
P → ax | PQ
Q → b | ϵ
R → c | ϵ
What is the number of terminals in the FIRST of X?
(if epsilon is present include it)

A
5-5

B
54-51

C
57-56

D
59-52

Solution

Non-Terminal
FIRST
X
y, a, b, x, ϵ
P
a
Q
b, ϵ
R
c, ϵ
Question 3
2 / -0.33

What will be the result of following code after constant propagation?
int x =4;
int y = x * 2;
int z = a[y];

A
int x = 4;
int y = 4 * 2;int z = a[y];

B
int y =4 *2;int z = a[y]

C
int y = 8;
int z = a[y];

D
int z = a[8];

Solution

Concept:
If the value of a variable is constant, then replace the variable with the constant and it must be propagated forward from the assignment point.
Explanation:
Given code:
Int x =4;
Int y = x * 2;
Int z = a[y];
Here we use the value of constant x = 4 and replace x by its value.
STEP 1: int y = 4 * 2; int z = a[y];
STEP 2: int y = 8; int z = a[y];
STEP 3: int z = a[8];
Question 4
2 / -0.33

Consider the grammar given below
E → TE’
E' → +TE' | ϵ
T → FT'
T' → *FT' | ϵ
F → (E) | id
Which of the following terminal symbol will be present in FOLLOW(F)?

A
+

B
*

C
)

D
$

Solution

T → FT'
FOLLOW(F) = FIRST(T’)
FIRST(T’) = {*, ϵ}
put ϵ in T → FT'
T → F
Therefore FOLLOW(F) = FOLLOW(T)
FOLLOW(T) = FIRST(E') = { +, ϵ } // E → TE’
put ϵ in E → TE’
E → T
FOLLOW(T) = FOLLOW(E)
Therefore FOLLOW(E) = { ), $ }
NOTE:
E is start symbol
ϵ is not a follow symbol
Question 5
2 / -0.33

Match all items in Group 1 correct option from those given in Group 2.
Group 1
Group 2
P. Intermediate representation
1. Activation records
Q. Top-down parsing
2. Code generation
R. Runtime environments
3. Leftmost derivation
S. Register allocation
4. Graph coloring

A
P – 2, Q – 3, R – 4, S – 1

B
P – 1, Q – 2, R – 3, S – 4

C
P – 4, Q – 2, R – 3, S – 1

D
P – 2, Q – 3, R – 1, S – 4

Solution

Intermediate representation
Intermediate representation is used to generate code. Code generation is the last phase of compiler.
Therefore P → 2.
Top down parsing
Top down parsing uses left most derivation to generate the string of the language.
Therefore Q → 3.
Runtime environment
Activation records of a function are loaded into stack memory at runtime environments, so runtime matches with activation records. Therefore R → 1.
Register allocation
Graph coloring is the predominant approach to solve register allocation.
Therefore S → 4.
Question 6
2 / -0.33

The number of tokens in the following C statement is
int i = 10;
float b = 12.0;
printf("x = %i, y = %f", i++, ++b);

A
21-21

B
214-211

C
217-216

D
219-212

Solution

Line no.
Tokens
Number of Tokens
Line 1
int | i | = | 10 | ; |
5
Line 2
float | b | = | 12.0 | ; |
5
Line 3
Printf | ( | "x = %i, y = %f" | , | i |++ | , | ++ |b | ) | ; |
11

Total Number of tokens = 5 + 5 + 11 = 21
Notes:
| is used to separate the token
Question 7
2 / -0.33

Find the Left factoring of a grammar
S → iEtS | iEtSeS | a
E → b

A
S → iEtS’ | a
S’ → eS| ∈
E → b

B
S → iEtSS’ | a
S’ → eS | ∈
E → b

C
S → iEtSS’ | a
S’ → eS
E → b

D
S → iEtS’|a
S’ → eS’’|∈
S’’ → a
E → b

Solution

If there is A-production be
A → aB1 | aB2 |……aBn | Y
Where ‘Y represent all alternative that do not begin with ‘a’ then
A → aA’ | Y
A’ → B1 | B2 |………..| Bn
In the given Grammar S → iEtS | iEtSeS | a, E → b.
$a = S$' = iEtS an B1 ∈ and $B2 = eS$
E → aB1 | aB2-----------------------a=S’=iEts and B1= ∈ and B2=eS
A → aA’ | Y……………………………….E → iETSS’
A’→ B1 | B2-------------------------S’->eS|∈
Question 8
2 / -0.33

Consider the following grammar:
S → aS'
S' → aS' | ϵ
Which of the following is/are true for the above grammar?

A
not left recursive

B
ambiguous

C
LL(1)

D
FIRST(S) = {a, ϵ}
Solution
Option 1: TRUE
S → aS' \\ right recursive
S' → aS' | ϵ \\ right recursive
Therefore given grammar is not left recursive
Option 2: FALSE
Two parse trees cannot be generated for any string in the given grammar and hence it is not ambiguous.
Option 3: TRUE and Option 4: FALSE
A grammar G is LL(1) iff. for all non-terminals A, each distinct pair of productions A → β and A → γ satisfy the condition FIRST(β) $\cap$ FIRST(γ) = φ.
A grammar G is LL(1) iff. for each set of productions A→α1 |α2 |···|αn:
FIRST(α1), FIRST(α2), ..., FIRST(αn) are all pairwise disjoint
If αi ⇒ *ε then FIRST(αj) $\cap$ FOLLOW(A) = φ, ∀1 ≤ j ≤ n, i $\neq$ j
Grammar is LL(1):
NON- TERMINAL
FIRST
FOLLOW
S
a
$
S’
a, ϵ
$

Although FIRST(S') has ϵ, FIRST(S') and FOLLOW(S') doesn't contain any common element. Therefore a cell in parsing table will contain at most one entry in it and hence it is LL(1)
Question 9
2 / -0.33

Consider the following code segment:
p = q – r
s = r + t
p = s + p
s = a + s
What it the minimum number of total variables required to convert the above code segment to static single assignment?

A
8-8

B
84-81

C
87-86

D
89-82

Solution

In compiler design, static single assignment form (SSA) is a property of an intermediate representation, which requires that each variable is assigned exactly once, and every variable is defined before it is used.
t1 = q – r
t2 = r + t
t3 = t2 + t1
t4 = a + t2
Variables are: t1, q, r, t2, t, t3, t4, a
Therefore, 8 variables are present in static single assignment form.
Question 10
2 / -0.33

Look at the below given code in C – program.
int main()
{
int i = 10;
whlie(i--)
printf(“TESTBOOK\n”);
}
Identity the compiler’s response about the above given code while creating the object- module

A
Prints TESTBOOK 10 times

B
Prints TESTBOOK 9 times

C
Lexical Error

D
Syntactic Error

Solution

while is a keyword in C programming language but code has incorrect spelling of while, that is, whlie
Now, it will be an error
Lexical analyzer will treat whlie as a valid identifier
But syntax analyzer will catch this error. Hence it is a syntactic error.
Question 11
2 / -0.33

Consider the below given grammar
S → L | M
L → c | b
M → b | a
where S is the start symbol also S, L, and M are non-terminal while x, y, z is terminal symbol.
Consider the predictive parsing table find the production for R1 and R2 respectively

a
b
c
$
S
S → M
R1
S → L

L

L → b
R2

M
M → a
B → b

A
R1 = {S → L} and R2 = {L → c}

B
R1 = {S → M} and R2 = {L → c}

C
R1 = {S → L and S → M} and R2 = {L → c}

D
R1 = {S → L and S → M} and R2 = {M → c}

Solution

First and Follow
Non-terminal
First
Follow
S
a, b, c
$
L
b, c
$
M
a, b
$

Predictive (LL(1)) parsing table

a
b
c
$
S
S → M
S → L
S → M
S → L

L

L → b
L → c

M
M → a
B → b

Important Points:
The give grammar ambiguous, it not LL(1) that is why one cell contains two entry.
Question 12
2 / -0.33

Which of the following statement about peephole optimization is/are correct?

A
It is done by examining a sliding window of target instructions and replacing sequences within the peephole by shorter sequence possible.

B
Code in the peephole must be contiguous

C
It helps in strength reduction.

D
It eliminates the unreachable code.
Solution
Concept:
Peephole optimization is a technique for locally improving the target code which is done by examining a sliding window of target instructions and replacing the instruction sequences within the peephole by shorter or faster sequences wherever possible.
Explanation:
The code in the peephole need not be contiguous although some implementations do require this. Some characteristics of peephole optimization are:
- Redundant instruction elimination
- Elimination of unreachable code
- Reduction in strength
- Algebraic simplifications
- Use of machine idioms
Question 13
2 / -0.33

Consider the following grammar:
S → pAS | r
A → q
Find the number of reduction steps taken by a bottom-up parser while accepting the string "pqpqpqpqr"?

A
9-9

B
94-91

C
97-96

D
99-92

Solution

Concept:
The class of bottom-up parser follow rightmost derivation in the reverse order.
Explanation:
S → pAS (S → pAS)
S → pApAS (S → pAS)
S → pApApAS (S → pAS)
S → pApApApAS (S → pAS)
S → pApApApAr (S → r)
S → pApApApqr (A → q)
S → pApApqpqr (A → q)
S → pApqpqpqr (A → q)
S → pqpqpqpqr (A → q)
Therefore, the number of reduction steps taken by a bottom-up parser while accepting the string "pqpqpqpqr" is 9.
Question 14
2 / -0.33

Consider the following statements, which of the following is/are TRUE?

A
During a program execution, stack is used for dynamic memory allocation and heap is used for static memory allocation.

B
During a program execution, heap is stored in main memory and stack is present in secondary memory.

C
During a program execution, access to heap memory variable is slower as compared to accessing variables allocated on stack.

D
During a program execution, in multithreaded situation, each thread has its own stack and share a common heap memory.

Solution

Option 1) FALSE

Both stack and heap is used for dynamic memory allocation. Hence given statement is False

Option 2) FALSE

During a program execution, both heap and stack is present in main memory.

Option 3) TRUE

Access to heap memory variable is slower as compared to accessing variables allocated on stack.

Because to access a heap memory variable we need access pointer variable first. Hence given statement is True

Option 4) TRUE

In a multithreaded situation, each thread has its own stack and share a common heap memory.
Question 15
2 / -0.33

Consider the following statements in the C language –
for( i = 7 ; i ≤ 923 ; i++ )
{
      x = a + b × c;
}
Here, 3 address code for the above code is given.
1000: i=7
1001: if i ≤ 923 goto   P
1002: goto Q
1003: t₁ = b × c
1004: t₂ = a + t₁
1005: x = t₂
1006: i = i + 1
1007: goto   R
1008: end
Find the value of P, Q and R in the given 3 address code.

A
P = 1003 and Q = 1008

B
Q = 1000 and R = 1001

C
R = 1003 and Q = 1008

D
Q = 1008 and R = 1001

Solution

1000: i = 7
1001: if i ≤ 923 goto   P
When if condition of for loop is true, then the execution of inner content of the for loop will be done, i.e,
x = a + b × c; statement will execute. Hence the flow of execution will go to 1003
So, P = 1003
1002: goto Q
When if condition of for loop is false, then execution will not go inside the for loop. It will end the program.
Hence, Q = 1008
1003: t₁ = b × c
1004: t₂ = a + t₁
1005: x = t₂
1006: i = i + 1
1007: goto   R
When all the 3 address codes until 1006 executed, it means 1 iteration of the for loop is completed. So, we need to go for the second iteration. So, R = 1001.
Overall, P = 1003, Q = 1008 and R = 1001
Question 16
2 / -0.33

Consider the following grammar and the semantic actions to support the L-attributed declaration attributes. Let A₁, A₂, A₃, A₄, A₅be the placeholders for the non- terminals S, X, Y or Z in the following table:
Production rule
Semantic action
S → X Y
A₁.val = A₂.val
X.val → +
Y.val = +
X.val → -
Y.val = -
Y → Z,id
A₃.val = A₄.val
Z → id
addType(id.entry, A₅.val)

Which one of the following is the appropriate choices for A₁, A₂, A₃, A_4,and A₅?

A
A4 = Y, A2 = Y, A3 = Z, A1 = X

B
A1 = X, A2 = Y, A3 = Y, A4 = Z

C
A1 = Y, A2 = X, A3 = Z, A4 = Y

D
A1 = S, A2 = Y, A3 = Z, A4 = Y

Solution

Concepts:
Synthesized attributes:
A Synthesized attribute is an attribute of the non-terminal on the left-hand side of a production. Synthesized attributes represent information that is being passed up the parse tree. The attribute can take value only from its children.
S-attributed SDT
If an SDT uses only synthesized attributes, it is called as S-attributed SDT.
Inherited attributes:
An attribute of a nonterminal on the right-hand side of a production is called an inherited attribute. The attribute can take value either from its parent or from its siblings.
L-attributed SDT
If an SDT uses both synthesized attributes and inherited attributes with a restriction that inherited attribute can inherit values from left siblings only, it is called as L-attributed SDT.
In SDT:
S → X Y {A₁.val = A₂.val}
Y.val = X.val (L-attributed SDT also inherited attribute)
∴ A₁ = Y and A₂ = X
In SDT:
Y → Z,id {A₃.val = A₄.val}
Z.val = Y.val (L-attributed SDT and also inherited attribute)
∴ A₃ = Z and A₄ = Y
Hence option 3 is correct.

User

Question Analysis

Correct -
Wrong -
Skipped -

My Perfomance

Score
-
out of -
Rank
-
out of -

Re-Attempt Weekly Quiz Competition

Production	Semantic Rule
T → FT’	T’.val = F.val
T’ → * FT’₁	T’.val = T’₁.val * F.val

Group 1	Group 2
P. Intermediate representation	1. Activation records
Q. Top-down parsing	2. Code generation
R. Runtime environments	3. Leftmost derivation
S. Register allocation	4. Graph coloring

Line no.	Tokens	Number of Tokens
Line 1	int \| i \| = \| 10 \| ; \|	5
Line 2	float \| b \| = \| 12.0 \| ; \|	5
Line 3	Printf \| ( \| "x = %i, y = %f" \| , \| i \|++ \| , \| ++ \|b \| ) \| ; \|	11

	a	b	c	$
S	S → M	S → L S → M	S → L
L		L → b	L → c
M	M → a	B → b

Production rule	Semantic action
S → X Y	A₁.val = A₂.val
X.val → +	Y.val = +
X.val → -	Y.val = -
Y → Z,id	A₃.val = A₄.val
Z → id	addType(id.entry, A₅.val)

Non-Terminal	FIRST
X	y, a, b, x, ϵ
P	a
Q	b, ϵ
R	c, ϵ

NON- TERMINAL	FIRST	FOLLOW
S	a	$
S’	a, ϵ	$

Non-terminal	First	Follow
S	a, b, c	$
L	b, c	$
M	a, b	$

Compiler Design Test 1

Result

Compiler Design Test 1

Score

-

Rank

-

SHARING IS CARING

Question 1

Synthesized

Inherited

S – attributed

L – attributed

Solution

Question 2

5-5

54-51

57-56

59-52

Solution

Question 3

int x = 4;int y = 4 * 2;int z = a[y];

int y =4 *2;int z = a[y]

int y = 8;int z = a[y];

int z = a[8];

Solution

Question 4

+

*

)

$

Solution

Question 5

P – 2, Q – 3, R – 4, S – 1

P – 1, Q – 2, R – 3, S – 4

P – 4, Q – 2, R – 3, S – 1

P – 2, Q – 3, R – 1, S – 4

Solution

Question 6

21-21

214-211

217-216

219-212

Solution

Question 7

S → iEtS’ | aS’ → eS| ∈E → b

S → iEtSS’ | aS’ → eS | ∈E → b

S → iEtSS’ | aS’ → eSE → b

S → iEtS’|aS’ → eS’’|∈S’’ → aE → b

Solution

Question 8

not left recursive

ambiguous

LL(1)

FIRST(S) = {a, ϵ}

Solution

Question 9

8-8

84-81

87-86

89-82

Solution

Question 10

Prints TESTBOOK 10 times

Prints TESTBOOK 9 times

Lexical Error

Syntactic Error

Solution

Question 11

R1 = {S → L} and R2 = {L → c}

R1 = {S → M} and R2 = {L → c}

R1 = {S → L and S → M} and R2 = {L → c}

R1 = {S → L and S → M} and R2 = {M → c}

Solution

Question 12

It is done by examining a sliding window of target instructions and replacing sequences within the peephole by shorter sequence possible.

Code in the peephole must be contiguous

It helps in strength reduction.

It eliminates the unreachable code.

Solution

int x = 4;
int y = 4 * 2;int z = a[y];

int y = 8;
int z = a[y];

S → iEtS’ | a
S’ → eS| ∈
E → b

S → iEtSS’ | a
S’ → eS | ∈
E → b

S → iEtSS’ | a
S’ → eS
E → b

S → iEtS’|a
S’ → eS’’|∈
S’’ → a
E → b