ANALYSIS OF COMPILER DESIGN IN GATE PAPER

Years Marks
2015 3
2016 5
2017 6
2018 5
2019 6
2020 4
2021 Set (1) 7
2021 Set (2) 8

COMPILER DESIGN GATE SYLLABUS

 Features of programming language
 Parameter Passing Techniques
 Static Scoping & Dynamic Scoping
 Introduction of compiler
 Phases of Compiler
 Scanning
 Parsing
 LL(1) parser
 SLR Parser
 CLR Parser
 LaLR Parser
 Syntax Directed Translation
 Attributed Grammar (S-attributed, L-attributed, Inherited attributed)
 Annoted Parse tree
 Intermediate Code Generation
 DAG(Directed Acyclic graph)
 Abstract Syntax tree
 Three address code
 Static single assignment
 Control Flow graph
 Runtime Environment

COMPILER DESIGN GATE REFERENCE BOOKS

Introduction to Compiler Design by “ Alfred V. Aho. Ravi Sethi, D. Ulmann”
 Compiler
For Next Five Question
Consider the following C program:
int i, b[5];
void q (int x)
{
i++;
x++;
}
void main()
{
i=1;
b[1]=3;
b[2]=4;
q(b[i]);
printf(“%d \n”, b[i]);
}
Q1. What value will be printed assuming that C uses the following parameter passing
mechanisms is “Pass by value”?
(A) 3 (B) 4 (C) 5 (D)none

Q2. What value will be printed assuming that C uses the following parameter passing
mechanisms is “Pass by reference”?
(A) 3 (B) 4 (C) 5 (D)none

Q3. What value will be printed assuming that C uses the following parameter passing
mechanisms is “Pass by value result”?
(A) 3 (B) 4 (C) 5 (D)none

Q4. What value will be printed assuming that C uses the following parameter passing
mechanisms is “Pass by name”?
(A) 3 (B) 4 (C) 5 (D)none

BASIC Compiler Page 1

Q5. What value will be printed assuming that C uses the following parameter passing
mechanisms is “Pass by need”?
(A) 3 (B) 4
(C) 5 (D) none

Q6. [MSQ]
Consider the following code:
int a[]=
{10,20,30,40}
int i = 0;
foo(int x){
print x;
x = x+1;
i = i+1;
print x;
}
void main(){
foo (a[i])
}
Which of the following statement is/are true?
(A) If parameter passing mechanism is “call by reference”, then the output of the
given code: 10, 11.
(B) If parameter passing mechanism is “call by name”, then the output of the given
code: 10, 11.
(C) If parameter passing mechanism is “call by need”, then the output of the given
code: 10, 11.
(D) If parameter passing mechanism is “call by value”, then the output of the given
code: 10, 11.

BASIC Compiler Page 2

Q7. [MSQ]
Consider the following code
int n = 1;
void display (int x){
print x + n;
}
void increment(){
n = n + 2;
print n ;
}
void main(){
int n =200;
display(7);
n = 50;
increment();
print n;
}
Which of the following statement is/are true?
(A) If the Static Scoping is used then printed output is: 8 52 50
(B) If the Static Scoping is used then printed output is: 8 3 50
(C) If the Dynamic Scoping is used then printed output is: 207 52 50
(D) If the Dynamic Scoping is used then printed output is: 207 52 52
For Next Two Question Consider the following block of C code:
#include <stdio.h>
int a, b;
int p(void)
{
int a, k;
a =0; b=1; k=2;
return k;
}
void print( void)
{
printf(“%d\n %d\n”, a, b);
}
void q(void)
{
int b;
a = 3; b=4;
print();
}
Void main()
{
a=p();
q();
}

BASIC Compiler Page 3

Q8. What values will be printed, when the program is parsed using Lexical (Static) scope?
(A) 3,1 (B) 3,4
(C) 4, 1 (D)none

Q9. What values will be printed, when the program is parsed using Dynamic scope?
(A) 3,1 (B) 3,4
(C) 4, 1 (D)none

Q10. [MSQ]
Consider the following code
int a = 2;
void foo(int b) {
b = b * a;
a = a - b;
}
void main(){
{
int a = 10;
foo(a);
print a;
}
Which of the following statement is / are true?
(A) The output of the above code under call-by-value and lexical scope is 10.
(B) The output of the above code under call-by-value and dynamic scope is -90.
(C) The output of the above code under call-by-reference and dynamic scope is 0.
(D) The output of the above code under call-by-reference and lexical scope is 20.

Q11. How many Tokens are there in the following statement? ________
a[index] = 4 + 2;

Q12. The number of tokens in the following C statement is ____________

int i = 10, j = 0;
printf ("i = %d, &i = %x", i, &i);
Q13. The number of tokens in the following C statement is _______
printf("Hello friends ,welcome to gate at Zeal!\n");

BASIC Compiler Page 4

Q14. The number of tokens in the following C statement is:__________
int main()
{
int a, b = 2, c = 3;
if (b != c)
a = b + c;
return 0;
}
Q15. The number of tokens in the following C statement is: ____________
int main()
{
int a = 10, b = 20, i;
printf("sum is: %d", a+b);
for (i = 1; i<a; i++) b++;
return 0;
}
Q16. [MSQ]
Which of the following error represents semantic error?
(A) Type mismatch (B) missing semi-colon
(C) illegal character (D) division by zero

Q17. Which phase of compiler will generate the error (if exists) in the following code?
void main ()
{
int a, b, c;
i=0; /* initialization //
j=;
=k;
}
(A) Lexical phase (B) Syntax analysis phase
(C) Semantic phase (D) No error in above code

BASIC Compiler Page 5

Q18. Which phase of compiler will generate the error (if exists) in the following code?
void main ()
{
int _, __, ___;
_ = 0; // Assign 0 to __ ;
__= 20;
___ = ___ + 10;
printf("_= %d, __ = %d,___ = %d", __,___,____);
}
(A) Lexical phase (B) Syntax analysis phase
(C) Semantic phase (D) No error in above code
Q19. Consider the following C code
void main()
{
int a, b, c;
a == b + c;
e +=- e;
}
Which phase of compiler will generate the error in above code?
(A) Lexical phase (B) Syntax analysis phase
(C) Semantic phase (D) No error in above code
Q20. Consider the following C program
void main()
{
int a = 089;
a=a+10;
printf("%d", a);
}
Which phase of compiler will generate the error in above code?
(A) Lexical phase (B) Syntax analysis phase
(C) Semantic phase (D) No error in above cod

BASIC Compiler Page 6

Q21. Consider the following C program
int fun(int a, int b)
{
int sum = a + b;
// return statement is missing
}
int main()
{
printf("%d\n", fun(5, 7));
return 0;
}
Which phase of compiler will generate the error (if exists) in above code?
(A) Lexical phase (b) Syntax analysis phase
(C) Semantic phase (d) No error in above code

Q22. In any C program, if a function is called with the incorrect number of arguments, then
which phase of compiler generates error (if exists)?
(A) Lexical phase (B) Syntax analysis phase
(C) Semantic phase (D) No error

Q23. In any C program, if underscore characters ( _ ) appear in the middle of identifiers,

but not at the beginning or end, then which phase of compiler generates error (if
exists)?
(A) Lexical phase (B) Syntax analysis phase
(C) Semantic phase (D) No error

Q24. Compiler ensures that “Every variable must be declared before it is used in the
program” in
(A) Lexical phase (B) Syntax analysis phase
(C) Semantic phase (D) code optimization phase

BASIC Compiler Page 7

Q25. Assignment statements must end with a semicolon
(A) Lexical phase (B) Syntax analysis phase
(C) Semantic phase (D) No error

Q26. Type checking is normally done during

(A) lexical analysis (B) syntax analysis
(C) syntax directed translation (D) code optimization

Q27. While using an array in C++, if index value exceeds the upper bound, then
(A) Compiler detects it as lexical error
(B) Compiler detects it as syntax error
(C) Compiler detects it as run time error
(D) Compiler does not detect it as error

Q28. Which phase of the compiler will generate the error in following C language
statement
iff (x == 0) y + = z + r; }

(A)Syntax Analysis
(B) Semantic Analysis
(C) Lexical Analysis
(D)No error.

Q29. Which phase of the compiler will generate the error in following C language
statement?
int x = "Hello, world!";

(A)Syntax Analysis
(B) Semantic Analysis
(C)Lexical Analysis
(D)No error.

BASIC Compiler Page 8

Q30. Which phase of the compiler will generate the error in following C language
statement?
int x = 2;
… … …
double y = 3.14159 / (x - 2);

(A)Syntax Analysis
(B) Semantic Analysis
(C)Lexical Analysis
(D)Runtime error.

Q31. Fill the appropriate word in the following statements:

S1: A____ ____ is a sequence of characters in the source program that matches the
pattern for a token and is identified by the lexical analyzer as an instance of that
token.
S2: A ________ is a pair consisting of a token name and an optional attribute value.
S3: A ________ is a description of the form that the lexemes of a token may take.
(A) P: Lexeme, Q: token, R: pattern
(B) P: Token, Q: lexeme, R: pattern
(C) P: Lexeme, Q: pattern, R: token
(D) P: pattern, Q: lexeme, R: Token
For the next fifteen questions identify the type of error exists in the given statements:
(1) A lexical error, detected by the scanner
(2) A syntax error, detected by the parser
(3) A static semantic error, detected by semantic analysis
(4) A dynamic semantic error, detected by code generated by the compiler
(5) No error
Q32. ‘@’ sign outside of a string or comment_________

Q33. Mismatched parentheses in an arithmetic expression__________

BASIC Compiler Page 9

Q34. Use of an identifier that was never declared_____________

Q35. Attempt to access an element beyond the bounds of an array___________

Q36. Modification of the index of a for loop by a subroutine called from within the
loop____________

Q37. '0a', 0 cannot be at the beginning of a variable declaration. ____________

Q38. Missing ';' at the end of a statement__________

Q39. int i;
i++; // the variable i is not initialized__________

Q40. int a = "hello"; // the types String and int are not compatible_______

Q41. Char *s = "...";

int a = 5 - s; // the - operator does not support arguments of type String_______

Q42. while (1) {

printf(“hello”);
} // this loop does not terminate ________

Q43. int sum(int a, int b) {

return a - b ;
}
// this method returns the wrong value wrt the specification that requires
// to sum two integer_________

Q44. x = ( 3 + 5; // missing closing parenthesis ')'______

BASIC Compiler Page 10

Q45. y = 3 + * 5; // missing argument between '+' and '_____

Q46. int a, b, x;
a = 10;
scanf (“%d”, &b);
x = a / b; //ERROR if b = 0______
Q47. [MSQ]
Consider the following lexical rules:
() {print(“0”)} // blank space
\n { printf("1") }// New line
All { printf("2") }
[a-f]+ { printf("3") }
eal { printf("4") }
[b-z]+ { printf("5") }
Est { printf("6") }
[A-Z]+ {printf ("7") }
Consider the input:
GateAtZeal
All the best
Assume there is nothing to the right of the last visible character on each line except a
newline character. Which of the following output is/are correct when given input is
scanned all at once?
(A) 73574120505 (B) 73575741205036
(C) 7357574120505 (D) 7357574020505
For next two questions, consider the following grammar over the alphabet {c, d, e}:
S → ABA
A → Bc | dA | 
B → eA | Af
Q48. Which of the following set represents First (A)?
(A) {e, d, } (B) {c, d}
(C) {d, } (D) {e, d, f, }

BASIC Compiler Page 11

Q49. Which of the following set represents Follow (A)?
(A) {c, d, $, f} (B) {c, d}
(C) {e, c, d} (D) {e, $, c, d, f}
For the next two questions: Let G be the following grammar:
E  EAE | (E) | -E | id
A + | - | * | /
Q50. The first of E contains:
(A){$,(,-,id} (B) {(,-,id}
(C) {(,-} (D) {(,-,id,ε}
Q51. The follow of E contains:
(A){$,+,*,/,(,),-,id} (B) {$,+,-,*,/,)}
(C) {$,+,-,*,/,),id} (D) {+,*,/,(,-,id }
Q52. [MSQ]
Consider the following grammar:
S  AB | BAB, A  SA | ba, B  a | 
Which of the following statement is/are true?
(A) First (S) = First (A)
(B) First (B)  Follow (S)
(C) Follow (S) = Follow (A) = Follow (B)
(D) First (B)  Follow (B) = .
Q53. [MSQ]
Consider the following grammar:
S  ACB | CbB | Ba
A  da | BC
Bg|
Ch|
(A) First (S) = {d, g, , h, a, b} and Follow (S) ={b, $, h, g}
(B) First (A) = {d, g, h, } and Follow (A) = {g, h, $}
(C) First (B) = {g, } and Follow (B) = {a, $, h, g}
(D) First (C) = {h, } and Follow (C) ={b, $, h, g}

BASIC Compiler Page 12

For the next two questions: Consider the following grammar:
S  A!
A  - A B | id C
B-B|
C   | id
Q54. The FIRST set contains:
(A)First(S)={-,id} First(A)={-,id} First(B)={-,} First(C)={,id}
(B) First(S)={-,id,!} First(A)={-,id} First(B)={-,,id} First(C)={,id}
(C) First(S)={-,id} First(A)={-,id} First(B)={-,,id} First(C)={,id}
(D) First(S)={-,id,} First(A)={-,id.} First(B)={-,} First(C)={,id}

Q55. The FOLLOW set contains:

(A) Follow(S) = {$} Follow(A)={-,!} Follow(B)={-, } Follow(C)={-,! }
(B) Follow(S) = {$,!} Follow(A)={ -,! } Follow(B)={-, id} Follow(C)={ id}
(C) Follow(S) ={$} Follow(A)={ -,! } Follow(B)={ -,! } Follow(C)={ -,! }
(D) Follow(S) ={$, } Follow(A)={-,id, } Follow(B)={-, } Follow(C)={id}

Q56. Consider the following grammar G:

SABC |aSCAa
ABC | BaA
BbC | cSa | λ
CCb| Cc| λ
How many of the following statement is/are true for G? ____________
1. First (S) is {a, b, c, λ}.
2. First (cdS) is {c}.
3. First (ba) is {b}.
4. Follow (S) is {b, c, $}.
5. Follow (A) is {a, b, c, $}.

BASIC Compiler Page 13

Q57. Consider the following grammar G:
SZaSb|XYc
XcSd|λ
YdSXZe|λ
ZeSf
Consider the following two columns and match the columns:
Column I Column II
i. First (S) 1. {$, b, c, d, e, f}
ii. Follow (S) 2. {c}
iii. First (X) 3. {c, d, e}
iv. Follow (Y) 4. {a, e}
v. Follow (Z) 5. {c, d, e,λ}
vi. First (Y) Follow (X) 6. {c, λ}
vii. First (Z) 7. {e}
(A)i - 3 , ii - 1, iii - 2, iv - 2, v - 4, vi – 5, vii - 7
(B) i - 3 , ii - 1, iii - 6, iv - 2, v - 4, vi – 4, vii - 7
(C)i - 3 , ii - 6, iii - 1, iv - 2, v - 4, vi – 5, vii - 7
(D) i - 3 , ii - 1, iii - 6, iv - 2, v - 4, vi – 5, vii – 7

Q58. Consider the following grammar

A → xA | yA | yC Cc
If we do left factoring to the above grammar resulting grammar will be
(A) A → xA | yB B→A|C Cc
(B) A → xA | yB B→A|y Cc
(C) A → xA | yB B → Ay | C C  c
(D) A → xA | yB B → Ay | y C  c

BASIC Compiler Page 14

Q59. Consider the following grammar G:
S → Sa | bL
L → ScL | Sd | a
A  Aaa | aa
After removing left recursion from G, the resulting grammar will be:
(A) S → bLS’ S’ → aS’ | ε L → ScL | Sd | a AaaA’ A’aaA’ | 
(B) S’ → bLS’ S → aS’ | ε L → ScL | Sd | a AaaA’ | 
(C) S’ → bLS S’ → aS’ | ε L → ScL | Sd | a A aaA’ A’aaA’ | 
(D) S → bLS’ S’ → aS | ε L → ScL | Sd | a A aaA’ A’aaA’ | 
Q60. [MSQ]
Which of the following grammar(s) has/have left-recursive rules?
(A) S  Sa | Sbb | cS | d
(B) S aS | Aa A Bc | d BbB | Ac
(C) S Aab | aBc A aA | Bc B Bb | c
(D) S aS | Aa A Bc | d BbB | c
Q61. [MSQ]
Which of the following grammar is/are not left-factored grammar?
(A) S aA | bB A Bc | d BbB | cB | c
(B) S  AB | BC A bA | c B bB
(C) S aS | a
(D) S aS | bS | 
Q62. [MSQ]
Consider the following grammar G:
A Aa | Aab | a | ab
Let the language generated by G is L(G). A grammar G’ is said to be LRE grammar if
it doesn’t have left-recursive rules and L(G’) = L(G).
Which of the following grammar is/are not LRE?
(A) A abA’ A’ aA’ | abA’ | λ
(B) A aA’ A’ aA’ | abA’ | λ
(C) A aA |abA’ A’ aA’ | abA’ | λ
(D) A aA’ |abA’ A’ aA’ | abA’ | λ

BASIC Compiler Page 15

Q63. [MSQ]
Consider the grammar G:S  0S | 0S0 | 1S | 1 | 0
Which of the following grammar is/are equivalent to G and left factored?
(A) S  0X | 1X X  0X | 1X | 
(B) S 0X | 1Y X  SZ |  Z0| Y S | 
(C) S  0Y | 11 Y 1X | SS0S XS|λ
(D) S  0S1 | 

Q64. [MSQ]
Consider the left-recursive grammar:
S  Sa | Sb | cc | dd | λ
Which of the following grammar is/are equivalent to G and doesn’t have left-
recursion?
(A) S aS’ | c S’  cc S’ | dd S’ | λ
(B)S aS’ | cc | dd S’  cc S’ | dd S’ | λ
(C) S ccS’ |ddS’ | S’ S’ aS’ | bS’ | λ
(D) S ccS’ |ddS’ | S’ S’ aS’ | bS’ | a | b | abS’ |λ

Q65. [MSQ]
Consider the following grammar G over the alphabet {a, b, c, d, e}:
S abA | bB | cCd
A Bc | d A | λ
B Ae | c | cC
C cC | λ
The above grammar G is not LL(1) because
(A) It is ambiguous .
(B) There exists left recursion.
(C)There exists a production rule which is not left factored. So, left-factoring is
required.
(D) First(S)  Follow(S) 

BASIC Compiler Page 16

Q66. [MSQ]
Consider the following grammar G:
S  A!
A  - A B | id C
B  - B | 
C   | id

Which of the following statement is/are False?

(A) G is not LL(1) because there doesn’t exists left factored production rules.
(B) G is not LL(1) because there exists left recursion in the grammar.
(C) G is not LL(1) because it is ambiguous.
(D) G is not LL(1).

Q67. [MSQ]
Consider the following grammar:
S → aS | Ab | b
A → XYZ | ε
X → cS | bS | ε
Y → dS | ε
Z → eS

Which of the following statement is/are true?

(A) The above grammar is not LL(1) because G has left recursive rules.
(B) The above grammar is not LL(1) because G is ambiguous.
(C) The above grammar is not LL(1) because First(A)  Follow(A) ≠ ∅
(D)The above grammar is LL(1)

Q68. Consider the grammar: S → a | aS | bS | b. Which smallest class of grammar does

this grammar belong to?
(A) LL(1) (B) LL(2)
(C) LL(3) (D) LL(0)

BASIC Compiler Page 17

Q69. [MSQ]
Which of the grammar is/are LL(1)?
(A) S aAbC A bBaC B bB | λ C cC | c
(B) S bB | cC A aB | bC B cC | aA C cC | λ
(C) S cAaB A  AB | BC | a B bB | λ C aC | c
(D) S  aAbc A  bA | c | cd

Q70. [MSQ]
Which of the grammar is/are LL(1)?
(A) S aAB | Bb A aA | b | λ B aaB | b | λ
(B) S SAS | (S) | -S | id A + | - | * | /
(C)SbA | aB Aa | aS | bAA Bb | bS | aBB
(D) S  bS | aaS | c

Q71. Let G be the following grammar:

G1: S ABC A bAa |aB | λ B aBb| λ C cCc| λ
G2: S(S)|SS| λ
G3: SaSb|ab| λ
G4: SaS|Sb| λ
G5: S aSbS | bSaS | λ
How many of the above grammar is/are LL(1)? __________

Q72. [MSQ]
Which of the following statement is/are true?
(A) The grammar G: S  S + S | S – S | S * S | S / S | 0 has look-ahead 2.
(B) Every LL(k – 1) is LL(k) but not vice-versa.
(C) In any grammar, for every non-terminal V, if (First (V)  Follow (V))  and
λ First (V), then grammar is not LL(1).
(D) If a grammar G is unambiguous, G has no left-recursion and G is left-factored,
then G is always LL(1).

BASIC Compiler Page 18

Q73. A recursive-descent parser with one-token look ahead is possible for which of the
following grammars?
(A) An ambiguous grammar.
(B) A grammar containing left recursion.
(C) A grammar with overlapping FIRST sets.
(D)An LL(1) grammar

Q74. For the grammar below, a partial LL(1) parsing table is also presented along with the
grammar. Entries that are need to be filled are indicated as E1, E2, and E3.
A Bb | a
B cA | 
a b c $
A A  a E1 E3
B E2 B  cA
The appropriate entries for E1, E2, and E3 are
(A) E1: ABb E2: B E3: BcA
(B) E1: ABb E2: error E3: ABb
(C) E1: ABb E2: B E3: ABb
(D) E1: ABb E2: error E3: BcA

Q75. Consider the following grammar: S AB A  aAb | B  c |  The LL(1) parse
table for the grammar is:
a b c $
S S  AB S  AB S  AB
A A  aAb A A A

B Bc B
Using the above LL(1) parse table to parse the input “abc” the maximum number of
the symbols in the stack at a time will be (stack initially contains $)___________

BASIC Compiler Page 19

Q76. Which of the following describes all languages that can be parsed using an LL(k)
parser?
(A) all LL(k) and LR(k) languages (B) all languages
(C) all LL(j) languages such that j ≤ k (D)all LL(0) languages

Q77. Which of the following strings over {a, b} is not accepted by the LL(1) parsing
algorithm with the following parse table? The start symbol is S.

(A)  (B) ab (C) acbc (D) c

Q78. Which one of the following statements about LL (1) grammars is true?
(A) Every unambiguous grammar is LL (1).
(B) Every grammar in Chomsky normal form is LL (1).
(C) Every regular grammar is LL (1).
(D) In the worst case, the LL (1) parsing algorithm may require space proportional to
the length of the input string.

Q79. Which one of the following grammars is LL(1)?

(A) S  TU, T   | aT, U   | bS
(B) S  Ta | Tb, T   | c
(C) S   | ST, T  a | b
(D) S   | TU, T   | a, U|b
Q80. Which of the following grammars is unsuitable as the basis for a recursive descent
parser? (In each case A is the start symbol for the grammar.)
(A) A  aA | bA | 
(B) A  Bc | a B  Ab | 
(C) A  aAc | bAc | 
(D) A  Bc | a B  bA | 

BASIC Compiler Page 20

Data for next two questions: Consider the following context-free grammar G:
S aAB | CbB | AcC A aABC | λ B bBcC | λ C cCd | λ
We construct a predictive parsing table for given grammar as shown below:
a b c d $
S E1
A E2 E6
B E3
C E4 E7 E5
Q81. [MSQ]
Which of the following is/ are true?
(A) Cell (A, a) contains AaABC.
(B) Cell (S, b) and Cell (S, c) contain one common production rules.
(C) Cell (B, c) contains B  bBcC | λ.
(D) Cell (C, d) contains C  cCd.

Q82. MSQ]
Which of the following statement is/are True?
(A) G is not LL(1) because Cell (C, b) contains multiple entries.
(B) G is not LL(1) because Cell (C, c) contains multiple entries.
(C) G is not LL(1) because Cell (B, b) contains multiple entries.
(D) G is LL(1).

Q83. Consider the following grammar:

0: S  X
1: X  a X c
2: X  X X
3: X  b
What is Closure(X  X . X)?
(A) X  X . X (B) X  X . X (C) X  X . X (D) X  X . X
X.aXc X.aXc X  a X. c X  a X. c
X  . XX X.b X.b X.XX
X.b X.b

BASIC Compiler Page 21

Q84. Consider the following grammar S  Sa | b. How many state are there in SLR(1)
parsing table for this grammar_______?

Q85. Consider the following augmented grammar:

S→E
E → EE+
E → EE!
E→a
How many states are there in SLR parser table of the above grammar? __________

Q86. Which type of conflict occurs in the SLR table of the following grammar?
S aB
S bA
B b
B bS
A a
A aB
(A) Shift-Reduce Conflict
(B) Reduce-Reduce Conflict
(C) Both (A) and (B)
(D) Neither (a) nor (b)

Q87. Consider the following augmented grammar:

S' → S
S → aSb
S→c
How many states are there in LR(1) parser table of the above grammar?_______

BASIC Compiler Page 22

For next four questions consider the following augmented grammar:
S→B
B → BE+ | −E
E → e | Ee | 
Following is incomplete DFA of LR(1) parsing state

Q88. What are the missing entries of state 0?

(A) S ∙ B, $ B ∙ BE+, $ B ∙ − E, $
(B) S ∙ B, $ B ∙ BE+, $+ B ∙ − E, $+
(C) S ∙ B, $ B ∙ BE+, $e B ∙ − E, $e
(D) S ∙ B, $ B ∙ BE+, $+e B ∙ − E, $+e

Q89. What are the missing entries of state 3?

(A) S B ∙ , $ B B ∙ E+, $ E ∙ e, + E ∙ Ee, +E  ∙, +
(B) S B ∙ , $ B B ∙ E+, $+ E ∙ e, + E ∙ Ee, +E  ∙, +
(C) S B ∙ , $ B B ∙ E+, $+ E ∙ e, $+ E ∙ Ee, $+ E  ∙, $+
(d) S B ∙ , $ B B ∙ E+, $+e E ∙ e, +e E ∙ Ee, +e E  ∙, +e

Q90. What are the symbols present in missing look ahead of the item B → BE+ in state 5?
(A) $ (B) $/e
(C) +/e (D) $/e/+

BASIC Compiler Page 23

Q91. What are the symbols present in missing look ahead of the item B → BE+ in state 8?
(A) $ (B) $/e
(C) +/e (D) $/e/+
Data for next two questions: Consider the following grammar G:
S aSBc | ac
B Bc | ba
Q92. [MSQ]
Construct SLR parsing table for G and identify which of the following statement
is/are true?
(A) There are nine items in the SLR table of the given grammar.
(B) There are six reduce entries in the SLR table of the given grammar.
(C) There are two GOTO entries in the SLR table of the given grammar
(D) There exists shift-reduce conflict in SLR parsing table.

Q93. Construct the CLR parsing table for grammar G and identify which of the following
statement is/are true?
1. There are total 17 CLR items in the table
2. There is a Reduce-Reduce conflict in the CLR table of the given grammar
3. The production B ba, is extended two times with different look-ahead.
(A) 1 only (B) 1 &2 only
(C) 3 only (D) None

Q94. Consider the following grammar:

X → YaYb | ZbZa, Y → ε, Z→ε
The above grammar is
(A) LL(1) and LR(0) but not SLR and CLR
(B) LL(1) but not LR(0), SLR and CLR
(C) LL(1) and CLR but not LR(0) and SLR
(D) not LL(1), LR(0), SLR and CLR

BASIC Compiler Page 24

Q95. Which of the following set of production rules form item I0 while running CLR
parsing algorithm for the given grammar?
1. SaS
2. SaA
3.SBa
4. Aa
5. BAbC
6. Cbb
7. S  bS
(A) (B)

S’  .S $ S’  .S $

S  .aS $ S  .aS $

S  .bS $ S  .bS $

S  .Ba $ S  .Ba $

B  .Abc a B  .Abc a

A  .a a A  .a b

C  .bb b C  .bb $

(C)S’  .S $ (D)S’  .S $

S  .aS $ S  .aS $

S  .bS $ S  .bS $

S  .Ba $ S  .Ba $

S  .aA $ B  .Abc b

B  .Abc a A  .a a

A  .a b

BASIC Compiler Page 25

Q96. What is the maximum number of conflicting entries, which can be found in a single
cell, in the SLR parsing table of the following grammar? ________
SSAB | AB | SBC
AAB | a
B BAB | b
Cb | c
Q97. Consider the following states in a LR(1) parser for a grammar G.

Which of the following statement is true?

(A) The grammar G is LALR(1) grammar
(B) The grammar G is Not a LALR (1) because no two states can be merged.
(C) Not a LALR(1) because during merging there exists reduce-reduce conflict
(D) Not a LALR (1) because corresponding LR(1) parser contains shift reduce
conflict.

Q98. Consider the following sets of LR(1) items in the states of a LR(1) parser:

Which of the following states would be merged in a LALR(1) parser?

(A) State 0 and 2
(B) State 0 and 1
(C) State 1 and 2
(D) None of the above states can be merged

BASIC Compiler Page 26

Q99. Consider the grammar
S  AaAb
S  BbBa
A  
B  
Which of the following is TRUE:
(A)The grammar is SLR(1)
(B) The grammar is not LALR(1)
(C) The grammar is not LR(1)
(D) The grammar generates atleast 5 strings.
Q100. Consider the grammar
SAS|b
ASA|a
(A)The grammar is SLR(1)
(B) The grammar is LALR(1)
(C) The grammar is LR(1)
(D)the grammar is ambiguous

Q101. [MSQ]
Which of the following statements is/are true?
(A) An unambiguous grammar has same leftmost and rightmost derivation
(B) An LL(1) parser is a top-down parser.
(C) LALR is more powerful than SLR
(D) An ambiguous grammar can never be LR(k) for any k.
Q102. Which one of the following statement is false for the SLR (1) and LALR (1) parsing
tables for a context free grammar?
(A)The reduce entries in both the tables may be different
(B)The error entries in both the tables may be different
(C)The go to part of both tables may be different
(D)The shift entries in both the tables may be identical.

BASIC Compiler Page 27

Q103. We have a grammar with not epsilon and unit production (i.e. of type Aε and

A  a) to parse a string, with 50 tokens. What the maximum number of reduces

moves that can be taken by a bottom-up parser for this grammar? ___________

Q104. Consider the following CFG:

S aAbB | bAaB A aA | λ B bbB | b | λ
How many of the following is/are not a left sentential form for this language?
_______
1. aaaAbbB 2. baaAaB 3. aaaabbB
4. bAabbbB 5. babbbb 6. bbbbbbba
Q105. [MSQ]
Which of the following statement is/are true?
(A) If G is unambiguous then every right-sentential form has a unique handle.
(B) Any prefix of right sentential form which appears on the stack of bottom up
parser is viable prefix.
(C) Not all prefix of right sentential form are viable-prefix.
(D) Every handle is viable prefix.

Q106. Consider the following grammar G:

S aSbAc | a | b A cAb | aA | λ
If string “abbcaabc” is generated by G and bottom up parser is used to parse this
string, then how many different handles will be there? _________

Q107. Consider the following grammar G:

S aSbAc | a | b A cAb | aA | λ
If string “abbcaabc” is generated by G and bottom up parser is used to parse this
string, then how many of the following is/are viable prefix? ______________
1. aSbA
2. aSbaA
3. aSbc
4. aSbcA
5. abb

BASIC Compiler Page 28

Q108. [MSQ]
Consider the following grammar
S  0S1 | 01
Which of the following string is/are the viable prefix of the grammar?
(A) 01
(B) 001
(C) 00011
(D) 00S1

Q109. [MSQ]
Which of the following features cannot be captured by CFG?
(A) Syntax of if-then-else statement
(B) Syntax of recursive procedures
(C) Whether a variable is declared before its use
(D) Matching nested parenthesis

Q110. Which of the following describes a handle (as applicable to LR-parsing)

appropriately?
(A) It is the position in a sentential form where the next shift or reduce operation will
occur
(B) It is non-terminal whose production will be used for reduction in the next step
(C) It is a production that may be used for reduction in a future step along with a
position in the sentential form where the next shift or reduce operation will occur
(D) It is the production p that will be used for reduction in the next step along with a
position in the sentential form where the right hand side of the production may be
found.

BASIC Compiler Page 29

For next two questions consider the following grammar and the corresponding action and
go to tables.

Q111. What next step taken by the parser if stack contains and input string is: (Assume top
of the stack contains 2)

(A) S8 (B) r2
(C) s7 (D) not a valid state
Q112. What next step taken by the parser if stack contains and input string is: (Assume top
of the stack contains 5)

(A) S8 (B) r2
(C) r0 (D) not a valid state
For the next five questions: Consider the following grammar:
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → digit | ( expr )
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Q113. Which operator has highest precedence?
(A)+ (B)-
(C)* (D)()

BASIC Compiler Page 30

Q114. The operator + is __________ associative.
(A)Left (B)Right .
(C)not associative (D)can’t say

Q115. The operator - is __________ associative.

(A)Left (B)Right
(C)not associative (D)can’t say

Q116. The operator * is __________ associative.

(A)Left (B)Right
(C)not associative (D)can’t say

Q117. The operator / is __________ associative.

(A)Left (B)Right
(C)not associative (D)can’t say

Q118. What output will be printed by the following SDD when the input is “ababb”?
S → aS {print "x"}
S → bS {print "y"}
S → a {print "w"}
S → b {print "z"}
(A) xxyyz (B) zyxxy
(C) zyyxx (D) zyxyx
Q119. What does it compute?
E→TR
R → + T { print(“+”) } R1
R→
T → id { print(id.name) }
(A) A simple translation scheme that converts infix expressions to corresponding
postfix expressions.
(B) A simple translation scheme that converts infix expressions to corresponding
prefix expressions.
(C) A simple translation scheme that converts postfix expressions to corresponding
prefix expressions.
(D) A simple translation scheme that converts postfix expressions to corresponding
infix expressions.

BASIC Compiler Page 31

Q120. Consider the grammar with the following translation rules and E as the start symbol

E  E1  T {E.value = E1.value * T.value}

ET {E.value = T.value}
T  T1 & F {T.value = T1.value + F.value}
TF {T.value = F.value}
F  num {F.value = num.value}
What is the E.value for the root of the parse tree for the expression: 3# 4 & 5 # 6 & 3?
(A) 216 (B) 231
(C) 243 (D) 102
Q121. Given the Syntax-Directed Definition below with the synthesized attribute val, by
drawing annotated parse tree for the expression (3+4) * (5+6) compute the value of
input expressions
L → E L.val = E.val
E → T E.val = T.val
E → E1 + T E.val = E1.val + T.val
T → F T.val = F.val
T → T1 * F T.val = T1.val * F.val
F→(E) F.val = E.val
F → digit F.val = digit.lexval
(A) 29 (B) 77
(C) 88 (D) 18
Q122. Consider the following SDT
EE1 + T {E.val = E1.val + T.val}
ET {E.val = T.val}
T id {T.val = id}
The above SDD is
(A) S-attributed (B) L-attributed
(C) Both a and b (D) Inherited attributed

BASIC Compiler Page 32

Q123. Consider the following SDT

B0 {val(B) = 0}
B1 {val(B) = 1}
LB {val(L) = val(B); len(L) = 1}
L  L1 {val(L) = 2*val(L1 ) + val(B); len(L) = len(L1 ) + 1}
NL {val(N) = val(L); len(N) = len(L)}
The above SDD is
(A) S-attributed (B) L-attributed
(C) Both a and b (D) Inherited attributed.
Q124. [MSQ]
Which of the following is/are true of attribute grammars?
(A) Every S-attributed grammar is also L-attributed.
(B) A symbol in an attribute grammar can have synthesized attributes or inherited
attributes, but not both.
(C) L-attributed grammars can naturally be evaluated during a bottom-up (LR)
parse.
(D) Every attributed grammar also has a natural expression as a context-free
grammar with action routines.
Q125. Consider the following Syntax-Directed Definition
A BC {A.i = B.i; C.i = B.s}
C BAC {C.s = A.s}
The above definition is
(A) S-attributed (B) L-attributed
(C) Inherited-attributed (D) Both a & b
Q126. Consider the following Syntax-Directed Definition
E (* E1E2 ) {E.z = E1.z -E2.z}
E( +E1 E2 ) {E.z = E1.z ^ E2.z}
E( –E1 ) {E.z = E1.z}
Enum{E.z = num.z}
The above definition is
(A) S-attributed (B) L-attributed
(C) Inherited-attributed (D) Both a & b

BASIC Compiler Page 33

Q127. Consider the following attributed grammar.
E→E%T {E0.v = 2 + E1.v + T.v}
E→E#T {E0.v = 3 * E1.v – T.v}
E→T {E.v = 5 + T.v}
T→a {T.v = 3}
T→b {T.v = 2}
T→c {T.v = 1}
What is the value for E.v for the root of the parse tree for the expression
"a # c" ?___________

Q128. Consider the following Syntax-Directed Definition

S  #AB { A.val = S. val*B.val }

A  @B {B.val = - A.val }
B  id {id.val = B.val}
The above definition is
(A) S-attributed
(B) L-attributed
(C) Inherited-attributed
(D) Both a & c

Q129. Consider the following grammar and associated semantic actions.

S  ABCD { x = 11 * x + 1; }
Dd { x = 7 * x + 1; }
C  cc { x = 5 * x + 1; }
B -> Bb { x = 3 * x + 1; }
B -> b { x = x + 1; }
A -> gBa { x = 2 * x + 1; }
The variable x is global—i.e., all semantic actions update the same x. Assume x is
initialized before parsing to 0. What is the final value of x in a bottom-up parse of
the following input string: “gbbabbccd”? ___________

BASIC Compiler Page 34

Q130. What from the following statements concerning the intermediate representations (IR)
is incorrect?
(A) IR simplify retargeting to a new host.
(B) IR simplify writing of a compiler for another language to the same host.
(C) Properly fixed IR simplify semantic aspects of the source language.
(D) IR break the compiler into manageable pieces

Q131. Which of the following is not a typical intermediate representation?

(A) Three address code
(B) Directed acyclic graphs
(C)Abstract syntax trees
(D)Annotated parse trees
Q132. Consider the following code segment.
x = a + b;
y = x * c;
p = y + y;
p = p + d;
p = p – d;
p = p + e;

The minimum number of total variables required to convert the above code segment
to static single assignment form is___________

Q133. Consider the following code segment.

a:= b + c
b:= c + d
d:= b + c
a:= a + c
e:= a + b
The minimum number of total variables required to convert the above code segment
to static single assignment form is __________.

Q134. The least number of temporary variables required to create a three-address code in
static single assignment form for the expression a = b *d – c + b *e – c is_________

BASIC Compiler Page 35

Q135. Consider the following code
a = 10;
b =20;
if (a > b) {
c = 30;
e = c - b;
} else {
d = b;
e = a + d;
Determine the minimum number of registers needed to execute above code without
spilling? _________.

Q136. What is the minimal number of registers necessary for the generation of code
corresponding with the following expression if one operand can be a memory
location. (a * b) + (c - (d + e))

Q137. What is the minimal number of registers necessary for the generation of code
corresponding with the following expression if all operands in cpu register?
(a * b) + (c - (d + e))
(A)2 (B)3 (C)4 (D)5

Q138. Consider the following code

a = 1 ;
b = 10;
c = 20;
d = a + b;
e = c + d;
f = c + e;
b = c + e;
e = b + f;
d = 5 + e;
return d+f;
What is the fewest number of registers that is needed for this program, without
spilling? _____

BASIC Compiler Page 36

For next three questions consider the following three address code:
1: a = b * 2;
L1: 2: if (a >= c) goto L4;
3: d = 3*a + 4;
4: if (d <= c) goto L2;
5: x = 2 * c;
6: y = 7;
7: goto L3;
L2: 8: y = 3 * c;
L3: 9: a = a + 2;
10: goto L1;
L4: 11:
Q139. How many basics blocks are there in this code? ______
(Don’t count entry and exit block)

Q140. What are the loop-invariant instructions in this code? [MSQ]

(A) Instructions 5 (B) Instruction 6
(C) Instruction 7 (D) Instruction 8

Which instructions could be moved out of the loops?

Q141.
(A) Instructions 5 (B) Instruction 6
(C) Instruction 7 (D) Instruction 8

Q142. Consider this code:

<S1> a := b
<S2> L1: b := c
<S3> if (...) goto L2
<S4> c := d
<S5> if (...) goto L1
<S6> L2: d := a
How many basic blocks are there?
(A) 3 (B) 4
(C) 5 (D) 6

BASIC Compiler Page 37

Q143. Which of the following is/are valid basic blocks?
(i) x = 0 (ii) body: (iii) true: (iv) label1: (v) entry:
y=x+1 x=x+1 t = 10 c=x+1 z=5
jump l1 cjump (x < 10) test jump join cjump (c == 0) a = z - 4
false: label3 jump exit
x = 20
jump label5

(A) i, ii & v only

(B) ii & v only
(C) i, iii & iv only
(D) v only

Q144. Consider the following program fragment.

1: j = n
2: i = 16 * n
3: j= j - 1
4: y = 4 * j
5: z = M[y]
6: i = i + z
7: if j > 0 goto 3
How many of the statements are correct:__________
(A) There is scope for applying strength reduction.
(B) There is scope for applying copy propagation.
(C) There is scope for applying induction variable elimination.
(D) There is scope for applying dead code elimination.

BASIC Compiler Page 38

Q145. [MSQ]
Consider the following code
While (i < 10)
{
j = 3 * i + 1;
a[j] = a[j] – 2;
i = i + 2;
}
Its equivalent optimized version is
s = 3 * i + 1;
while (i < 10)
{
j = s;
a[j] = a[j] – 2;
i = i + 2;
s = s + 6;
}
Which of the following techniques of code optimization is/are applied here?
(A) Strength reduction
(B) Copy propagation
(C) Induction variable elimination
(D) Constant Folding
For next three questions consider the following C code with line numbers
1. int f() {
2. int p = 10;
3. int a[3];
4. a[0] = 6;
5. a[1] = p * 32;
6. a[2] = 28;
7. if (a[0] * a[2] < -1)
8. p=p+10;
9. return a[0]+a[1] +a[2]+ p;
10. }
Write the line number on which following code optimization techniques can be applied.
Q146. Strength reduction : _________
(A) Line 5 (B) Line 7
(C) Line 8 (D) None of these

BASIC Compiler Page 39

Q147. Constant folding: __________
(A) Line 5 (B) Line 7
(C) Line 8 (D) None of these

Q148. Dead code elimination ____________

(A) Line 5 (B) Line 7
(C) Line 8 (D) None of these

Q149. [MSQ]
Consider the following code fragment
r0=10
r1= 20
r2 = r0 + r1
r3 = r2
r4 = r2+ r3
// only r4 accessed below this lines
The code given above is transformed in to the code given below after applying some
optimization technique
r0=10
r1= 20
r2 = r0 + r1
r4 = r2 + r2
Which optimization technique(s) is/are applied here?
(A) Strength reduction
(B) Copy propagation
(C) Dead code elimination
(D) Constant Foldin

BASIC Compiler Page 40

For next two questions: Consider the following CFG

Q150. [MSQ]
Which of the following is/are correct gen and kill sets of basic blocks for Available
expression analysis?
(A) For basic block B1, Gen = {a*b, c + d}, Kill = {}
(B) For basic block B2, Gen = {c + d}, Kill = {a*b}
(C) For basic block B3, Gen = {a*b}, Kill = {}
(D) For basic block B4,Gen = {a*b}, Kill = {c + d}

Q151. [MSQ]
Which of the following is/are correct IN and OUT sets of basic blocks for Available
expression analysis?
(A) For basic block B1, IN = {}, OUT = {a*b, c + d}
(B) For basic block B2, IN = {a*b}, OUT = { a*b, c + d }
(C) For basic block B3, IN = {c + d}, OUT = {a*b, c + d}
(D) For basic block B4, IN = {c + d}, OUT = {a*b, c + d}

BASIC Compiler Page 41

For next two questions: Consider the following CFG

Q152. [MSQ]
If Gen (B) and Kill (B) represent the Gen set and Kill set of basic block B, respectively.
Which of the following options is/ are correct about gen and kill sets of basics blocks
for reaching definition analysis?
(A) Gen (B2) = Kill (B2)  Kill (B3)  Kill (B4)

(B) Gen (B1) – (Kill (B2)  Kill (B3)  Kill (B4)) = 

(C) Kill (B2)  Kill (B1) = Gen (B4) – Kill (B4)
(D) Kill (B1) = Gen (B2)  Gen (B3)  Gen (B4)

Q153. [MSQ]
If IN (B) and OUT (B) represent the IN set and OUT set of basic block B, respectively.
Which of the following options is/ are correct about IN and OUT sets of basics
blocks for reaching definition analysis after 3rd Pass?
(A) |OUT (B2)  OUT (B3)| = |OUT (B4) - OUT (B1)|
(B) IN (B3) = IN (B4)
(C) OUT (B3) = IN (B4)
(D) IN (B2)  IN (B1) = {d1, d2, d3, d5, d6, d7}

BASIC Compiler Page 42

For next Eight questions: Consider the following CFG

Q154. Which of the following is correct use and define sets of basics block B1 for live
variable analysis?
(A) Use = { m, n}, Def = {i, j, a } (B) Use = { m, n, u1}, Def = {i, j }
(C) Use = {m, n }, Def = {i, j } (D) Use = { m, n, u1 }, Def = { i, j, a}

Q155. Which of the following is correct use and define sets of basics block B2 for live
variable analysis?
(A) Use = {i,j }, Def = {i,j } (B) Use = { i,j}, Def = {i }
(C) Use = {i,j }, Def = { } (D) Use = {i,j }, Def = {j }

Q156. Which of the following is correct use and define sets of basics block B3 for live
variable analysis?
(A) Use = {u2 }, Def = {a } (B) Use = {u2 }, Def = {u2,a }
(C) Use = { a,u2}, Def = {a } (D) Use = {a }, Def = { u2}

BASIC Compiler Page 43

Q157. Which of the following is correct use and define sets of basics block B4 for live
variable analysis?
(A) Use = {a, j, i }, Def = {i } (B) Use = { a, j}, Def = {i }
(C) Use = {a, j, i }, Def = {a, j, i } (D) Use = {a, j, i }, Def = { i, j}
Q158. Which of the following is correct in and out sets of basics block B1 for live variable
analysis?
(A) In = {m,n,u1}, Out = {i,j,u2,a} (B) In = {m,n}, Out = {i,j,u2,a}
(C) In = {m,n,u1}, Out = {i,j,u2} (D) In = {m,n}, Out = {i,j,u2}
Q159. Which of the following is correct in and out sets of basics block B2 for live variable
analysis?
(A) In = {i,j,a}, Out = {a,j,u2} (B) In = {i,j,a,u2}, Out = {a,j,u2}
(C) In = {i,j,a}, Out = {a,j,u1} (D) In = {i,j,a,u1}, Out = {a,j,u2}
Q160. Which of the following is correct in and out sets of basics block B3 for live variable
analysis?
(A) In = {j,u2}, Out = {a,j,u2} (B) In = {i,u2}, Out = {a,j,u2}
(C) In = {i,j,u2}, Out = {a,j,u2} (D) In = {i,j}, Out = {a,j,u2}

Q161. Which of the following is correct in and out sets of basics block B4 for live variable
analysis?
(A) In = {a,j,u2}, Out = {a,j,u2} (B) In = {a,j,u2}, Out = {a,i,j,u2}
(C) In = {a,j,u2}, Out = {a,i,u2} (D) In = {a,i,u2}, Out = {a,i,j,u2}
For next two questions: Consider the following basic block for live variables:

Q162. What is USE for the basic block?

(A) {a} (B) {b,c}
(C) {e, d} (D) { a, c }

BASIC Compiler Page 44

Q163. What is DEF for the basic block?
(A) {a,b,d} (B) {c, d, b}
(C) { a, b, d, e } (D) {a, c}
Consider the following control flow graph for next three questions

Assume you are given IN/OUT for B1, B2, B4, B5, and GEN/KILL for B3.
Q164. What is the forward data-flow problem for available expression for basic block B3?

(A) IN(B3) = OUT(B1)  OUT(B2) , OUT(B3) = GEN(B3)  (IN(B3) – KILL(B3))

(B) IN(B3) = OUT(B1)  OUT(B2), OUT(B3) = GEN(B3) U (IN(B3) – KILL(B3))
(C) IN(B3) = OUT(B1)  OUT(B2), OUT(B3) = GEN(B3) U (IN(B3) – KILL(B3))
(D) IN(B3) = OUT(B1)  OUT(B2) ,OUT(B3) = GEN(B3)  (IN(B3) – KILL(B3))

Q165. What is the forward data-flow problems for reaching definition for basic block B3 ?
(A) IN(B3) = OUT(B1)  OUT(B2) , OUT(B3) = GEN(B3)  (IN(B3) – KILL(B3))
(B) IN(B3) = OUT(B1)  OUT(B2), OUT(B3) = GEN(B3) U (IN(B3) – KILL(B3))
(C) IN(B3) = OUT(B1)  OUT(B2), OUT(B3) = GEN(B3) U (IN(B3) – KILL(B3))
(D) IN(B3) = OUT(B1)  OUT(B2) ,OUT(B3) = GEN(B3)  (IN(B3) – KILL(B3))

Q166. What is the backwards data-flow problems for B3 ?

(A) OUT(B3) = IN(B4) IN(B5) , IN(B3) = USE(B3) U (OUT(B3) – DEF(B3))

(B) OUT(B3) = IN(B4) IN(B5), IN(B3) = USE (B3)  (OUT(B3) – DEF (B3))
(C) OUT(B3) = IN(B4) IN(B5) , IN(B3) = USE (B3)  (OUT(B3) – DEF (B3))
(D) OUT(B3) = IN(B4) IN(B5) ,IN(B3) = USE (B3) U (OUT(B3) – DEF (B3))

BASIC Compiler Page 45

 Consider the following control flow graph for available expressions

Q167. Calculate GEN/KILL for each basic block. Which of the following option is true?

For next two questions consider the control-flow graph with numbers for each statement:

Q168. What are the sets of live variables at the beginning of each statement?
[Note: Write ∅ for the empty set, if necessary]
(A) 1 –  , 2 – {x}, 3 – {x}, 4 – {x}, 5 – {x, y}, 6 – {x, y}, 7 – {x, y}
(B) 1 –  , 2 – {x}, 3 – , 4 – {x}, 5 – {x, y}, 6 – {x, y}, 7 – {x, y}
(C) 1 –  , 2 – , 3 – , 4 – {x}, 5 – {x, y}, 6 – {x, y}, 7 – {x, y}
(D) 1 –  , 2 – {x}, 3 – , 4 – {x}, 5 – {y}, 6 – {x, y}, 7 – {x, y}

BASIC Compiler Page 46

Q169. What are the sets of reaching definitions at the end of each statement?
[Note: Write ∅ for the empty set, if necessary]

Q170. What is the live range for each variable (x, y, z, w & v) in the following program?
0: ….
1: x = y + 1
2: z = x + y
3: w = load(x)
4: v = f(z, w) // v is used later
5: ….
(A) x: 0-3, y: 0-2, z: 0-4, w: 0-4, v: 0-4
(B) x: 1-3, y: 1-2, z: 2-4, w: 3-4, v: 4-4
(C) x: 1-3, y: 0-2, z: 2-4, w: 3-4, v: 4-5
(D) None of the above

BASIC Compiler Page 47

Q171. [MSQ]
For the following code, find the loop invariant instruction(s) which can be moved to
the pre-header by a loop-invariant code motion pass?

(A) S2 : y = 5
(B) S3 : q = 7
(C) S6: x = 1
(D) None of these

BASIC Compiler Page 48

 Compiler Test -1

Q1. Consider the following context-free grammar:

G = ({S, A,B}, {a, b, c, d}, {S  Ad A  cA | BAa |b B b|}, S)
Which of the following set is First (A)?
(a) {b,c} (b) {a, b}
(c) {a, b, } (d) {a, b, c, }

Q2. Consider the following two grammars:

G1 G2
S → cA | b S → AaS | B
A → cBC | bSA | a A → cS | 
B → cc | Cb B→b
C → aS | ba
Which of the above grammars are LL(1)?
(a) Neither of the two grammars is LL(1) (b) Only G1 is LL(1)
(c) Only G2 is LL(1) (d) Both grammars are LL(1)

For next two questions consider the following code

int A=6, B=7;
void p1(){
int I, J, K;
for (I= 1;I<=10 ;I++)
B = B + I;
K = I + J;
}
void p2(){
int I, J, K;
J = A + B;
p1();
K = J + I;
I = K + J;
}
void main(){
A = 10;
B = -5;
p2();
writeln(A+B);
}

Q3. What is the output of the code if static scoping is used? ____________

BASIC Compiler Page 49

Q4. What is the output of the code if dynamic scoping is used? ________________
Consider program for next two questions:
int x,y;
void regain (int a, int b )
{
a:=b+x;
b:=a+x;
print a,b;
}
void main()
{
x := 1
y:=2;
regain (x,y);
print x,y;
}
Q5. What is the final value of a and b respectively if all parameters are passed by using Call –by
value.
(A) 3 ,4 (B) 1 ,2
(C) 3,2 (D) Error
Q6. What is the final value of x and y respectively if all parameters are passed by using the Call
–by-reference.
(A)3,2 (B) 1,2
(C) 3,6 (D) Error

Q7. Consider the following code

int g;
void foo(int j,int k)
{ print(j,k);
g = g+1;

BASIC Compiler Page 50

 print(j,k);
}
void main(){
g=1
foo(2*g, g);
}
What is the output if parameters are passed by name?
(A) 2 1 , 4 1 (B) 2 1 , 4 2
(C) error (D) none
For next two questions consider the following code
int g;
void foo(int j,int k)
{ g=2;
print(j,k);
g = g+1;
}
void main(){
g=1
foo(2*g, g);
print(g);
}
Q8. What is the output sequence if parameters are passed by need?
(A) 4 2 1 (B) 4 1 2 (C) 4 2 3 (D) 3 1 2

Q9. What is the output sequence if parameters are passed by value result?
(A) 2 1 3 (B) 3 2 1 (C) 2 1 1 (D) 2 1 2

Q10. Consider the following grammar

E→A|B
A→a|c
B→b|c
The above grammar is:

BASIC Compiler Page 51

 (A) LL(1) (B) SLR(1) but not LL(1)
(C) LALR(1) but not SLR(1) (D) Not LR(1)

For next two questions consider the following three grammars, where A is starting symbol,
G1 G2 G3
ABC ABC ABC
BAx | x BAx | x |  BAx | x | 
CyC | y CyC | y CyC | y | 

Q11. In which of the following grammar Follow (A) = {$ , x}?

(A)G1 (B) G1 and G2 (C) G1, G2 and G3 (D) G2 and G3

Q12. In which of the following grammar Follow (B) = {$ , x, y}?

(A)G1 and G3 (B) G1 and G2 (C) G3 (D) G2 and G3

Q13. Consider the following left recursive grammar

S → 2|3|S0|S1
After removing left recursion with the help of new non-terminal T the resulting grammar will
be?
(A) S → 2T|3T T → 0T|1|
(B) S → 2T|3T T → 0T|1T|
(C) S → 2T|3T|1T T → 0T|1T|
(D) S → 2T|3T T → 0|1T|
Q14. Consider the following left factored grammar
S → BCA S → B
After removing left factoring with the help of new nonterminal T the resulting grammar will
be?
(A)S → BT T → CA
(B) S → BT T → CA|
(C) S → BT| T → CA|
(D) none of these

BASIC Compiler Page 52

Q15. Consider the following lexical specifications,
Specification Action
(aba)+ print 1
(a(b*)a) print 2
(a+b) print 3);
What output is generated by lexer for the string abaabbaba? __________
Q16. How many of the following grammar is/are LL(1)? _______
i) A  AxB | Cy B  zAy C  xA | 
ii) A  Cz | xB B  xC C  yA | 
iii) A  xA |By B zC | C zAx
Q17. Consider the following grammar
S→Z Z → aMa | bMb | aRb | bRa M→c R→c
One of the state of LR(1) parser is given below
Z → a·Ma $
Z → a·Rb $
M → ·c x
R → ·c y
What should be the value for x & y respectively?
(a) b, a (b) a, b (c) a,c (d) b,c

Q18. Consider the following grammar

S→A A → Aa | ε
How many states are there in LR(1) parsing table for these grammar? _________
For next two questions consider the following grammar which is both LL(1) and LR(1):
S→A (1)
A → aBE (2)
B → bCD (3)
C→c (4)
D→d (5)
E → eFG (6)
F→f (7)
G→g (8)

BASIC Compiler Page 53

Q19. In which order the production rules are applied by LL(1) parser when parsing the string
abcdefg ?
(a)1,2,3,4,5,6,7,8 (b)1,2,4,5,3,6,7,8
(c)1,2,3,6,5,4,8,7 (d)1,2,3,8,7,6,5,4
Q20. In which order the production rules are applied by LR(1) parser when parsing the string
abcdefg ?
(a) 4, 5, 3, 7, 8, 6, 2, 1 (b) 4, 3, 5, 7, 8, 6, 2, 1
(c) 8 ,7, 6,5 , 4, 3, 2,1 (d) 5, 4, 6, 7, 8, 1, 2, 3
Q21. Consider the following grammar
S →X X → Yb | aa Y → a | bYa
Here is the SLR(1) automata for the grammar

The above grammar is not SLR(1) because

(a)There exists shift-reduce conflict in state 1
(b)There exists shift-reduce conflict in state 3
(c)There exists shift-reduce conflict in state 7
(d)There is no conflict above grammar is SLR(1)
Q22. How many of the following is/are correct statements:_______
1. Tokens can be described using regular grammars (RGs) but not context free grammars
(CFGs)
2. LR(k) can process both left-recursive and right-recursive grammars.
3. For LR-parsing, a handle always appears on the top of the syntax stack
4. Given a sentence to parse, top-down parsing strategies such as LL(k) find its left-most
derivation starting from the start symbol

BASIC Compiler Page 54