Compiler-Design
Question 1 |
Consider the following grammar.
S → aSB|d B → b
The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is _______.
A | 7 |

7 reductions total.
Question 2 |
Consider the following statements.
- I. Symbol table is accessed only during lexical analysis and syntax analysis.
II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment.
III. Errors violating the condition ‘any variable must be declared before its use’ are detected during syntax analysis.
Which of the above statements is/are TRUE?
A | II only |
B | I only |
C | I and III only
|
D | None of I, II and III |
II is wrong as compilers which supports recursion require stack memory in run time environment.
III is wrong “any variable must be declared before its use” is a semantic error and not syntax error.
Question 3 |
Consider the productions A⟶PQ and A⟶XY. Each of the five non-terminals A, P, Q, X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.
Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i
Which one of the following is TRUE?
A | Only Rule 2 is L-attributed.
|
B | Neither Rule 1 nor Rule 2 is L-attributed. |
C | Both Rule 1 and Rule 2 are L-attributed. |
D | Only Rule 1 is L-attributed.
|
Question 4 |
A | The LALR (1) parser for a grammar G cannot have reduce-reduce conflict if the LR (1) parser for G does not have reduce-reduce conflict. |
B | Symbol table is accessed only during the lexical analysis phase. |
C | Data flow analysis is necessary for run-time memory management. |
D | LR (1) parsing is sufficient for deterministic context-free languages. |
Symbol table is accessed in all the phases of compiler and not only in lexical analysis phase.
Data flow analysis is done in the control flow graph, in the code optimization phase. If LR(1) parses a grammar then definitely it is DCFL, so LR(1) parsing is sufficient for deterministic context-free languages.
Question 5 |

A | 5 |

Question 6 |

A | 80 |

Question 7 |
The pass number for each of the following activities
- 1. Object code generation
2. Literals added to literal table
3. Listing printed
4. Address resolution of local symbols
That occur in a two pass assembler respectively are
A | 1, 2, 1, 2 |
B | 2, 1, 2, 1 |
C | 2, 1, 1, 2 |
D | 1, 2, 2, 2 |
Pass 1:
1) Assign addresses to all statements in the program.
2) Save the values assigned to all labels for use in pass 2.
3) Perform some processing of assembler directives.
Pass 2:
1) Assemble instructions.
2) Generate data values defined by BYTE, WORD etc.
3) Perform processing of assembler directives not done during pass 1.
4) Write the program and assembling listing.
Question 8 |
Which of the following macros can put a micro assembler into an infinite loop?
(i) .MACRO M1 X .IF EQ, X ;if X=0 then M1 X + 1 .ENDC .IF NE X ;IF X≠0 then .WORD X ;address (X) is stored here .ENDC .ENDM (ii) .MACRO M2 X .IF EQ X M2 X .ENDC .IF NE, X .WORD X+1 .ENDC .ENDM
A | (ii) only |
B | (i) only |
C | both (i) and (ii) |
D | None of the above |
Question 9 |
Given below are the transition diagrams for two finite state machine M1 and M2 recognizing languages L1 and L2 respectively.
(a) Display the transition diagram for a machine that recognizes L1.L2, obtained from transition diagrams for M1 and M2 by adding only ε transitions and no new states.
(b) Modify the transition diagram obtained in part(a) obtain a transition diagram for a machine that recognizes (L1.L2)∗ by adding only ε transitions and no new states. (Final states are enclosed in double circles).

A | Theory Explanation. |
Question 10 |
Consider the syntax-directed translation schema (SDTS) shown below:
E → E + E {print “+”} E → E ∗ E {print “.”} E → id {print id.name} E → (E)
An LR-parser executes the actions associated with the productions immediately after a reduction by the corresponding production. Draw the parse tree and write the translation for the sentence.
(a+b)∗(c+d), using the SDTS given above.
A | Theory Explanation. |
Question 11 |
In the following grammar
X ::= X ⊕ Y/Y Y ::= Z * Y/Z Z ::= id
Which of the following is true?
A | ‘⊕’ is left associative while ‘*’ is right associative |
B | Both ‘⊕’ and ‘*’ is left associative |
C | ‘⊕’ is right associative while ‘*’ is left associative |
D | None of the above |

⊕ is left associative.
* is right associative.
Question 12 |
A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which of the following is true?
A | A compiler using static memory allocation can be written for L |
B | A compiler cannot be written for L; an interpreter must be used |
C | A compiler using dynamic memory allocation can be written for L |
D | None of the above |
Question 13 |
The conditional expansion facility of macro processor is provided to
A | test a condition during the execution of the expanded program |
B | to expand certain model statements depending upon the value of a condition during the execution of the expanded program |
C | to implement recursion |
D | to expand certain model statements depending upon the value of a condition during the process of macro expansion |
Question 14 |
Heap allocation is required for languages
A | that support recursion |
B | that support dynamic data structures |
C | that use dynamic scope rules |
D | None of the above |
Question 15 |
In a resident – OS computer, which of the following systems must reside in the main memory under all situations?
A | Assembler |
B | Linker |
C | Loader |
D | Compiler |
Some OS may allow virtual memory may allow the loader to be located in a region of memory that is in page table.
Question 16 |
Which of the following statements is true?
A | SLR parser is more powerful than LALR |
B | LALR parser is more powerful than Canonical LR parser |
C | Canonical LR parser is more powerful than LALR parser |
D | The parsers SLR, Canonical CR, and LALR have the same power |
Canonical LR parser is more powerful than LALR parser.
Question 17 |
Type checking is normally done during
A | lexical analysis |
B | syntax analysis |
C | syntax directed translation |
D | code optimization |
Question 18 |
Let the attribute ‘val’ give the value of a binary number generated by S in the following grammar:
S → L.L | L L→ LB | B B → 0 | 1
For example, an input 101.101 gives S.val = 5.625
Construct a syntax directed translation scheme using only synthesized attributes, to determine S.val.
A | Theory Explanation. |
Question 19 |
Which of the following is the most powerful parsing method?
A | LL (1) |
B | Canonical LR |
C | SLR |
D | LALR |
LR > LALR > SLR
Question 20 |
The number of tokens in the Fortran statement DO 10 I = 1.25 is
A | 3 |
B | 4 |
C | 5 |
D | None of the above |
10 → 2
I → 3
= → 4
1.25 → 5
Question 21 |
Let synthesized attribute val give the value of the binary number generated by S in the following grammar. For example, on output 101.101, S.val = 5.625.
S → LL|L L → LB|B B → 0|1
Write S-attributed values corresponding to each of the productions to find S.val.
A | Theory Explanation. |
Question 22 |
The number of tokens in the following C statement.
printf("i = %d, &i = %x", i, &i);
is
A | 3 |
B | 26 |
C | 10 |
D | 21 |
(i) Keyword
(ii) Identifier
(iii) Constant
(iv) Variable
(v) String
(vi) Operator
Print = Token 1
( = Token 2
“i=%d%x” = Token 3 [Anything inside ” ” is one Token]
, = Token 4
i = Token 5
, = Token 6
& = Token 7
i = Token 8
) = Token 9
; = Token 10
Here, totally 10 Tokens are present in the equation.
Question 23 |
Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.
A | Leftmost derivation |
B | Leftmost derivation traced out in reverse |
C | Rightmost derivation |
D | Rightmost derivation traced out in reverse |
Bottom-Up parser – Reverse of rightmost derivation
Question 24 |
Given the following expression grammar:
E → E * F | F + E | F F → F - F | id
which of the following is true?
A | * has higher precedence than + |
B | – has higher precedence than * |
C | + and – have same precedence |
D | + has higher precedence than * |
Order of precedence is *, +, -.
Here * and + have equal preference, ‘-‘ can have higher precedence than + and *.
Question 25 |
Consider the syntax directed translation scheme (SDTS) given in the following.
Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction.
E → E1 * T {E.val = E1.val * T.val} E → T {E.val = T.val} T → F – T1{T.val = F.val – T1.val} T → F {T.val = F.val} F → 2 {F.val = 2} F → 4 {F.val = 4}
(a) Using this SDTS, construct a parse tree for the expression
4 – 2 – 4 * 2
and also compute its E.val.
(b) It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the SDTS given, without changing the grammar, to find E.red, the number of reductions performed while reducing an input to E.
A | Theory Explanation is given below. |
Question 26 |
(a) Construct all the parse trees corresponding to i + j * k for the grammar
E → E+E E → E*E E → id
- (b) In this grammar, what is the precedence of the two operators * and +?
(c) If only one parse tree is desired for any string in the same language, what changes are to be made so that the resulting LALR(1) grammar is non-ambiguous?
A | Theory Explanation is given below. |
Question 27 |
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
A | Removing left recursion alone |
B | Factoring the grammar alone |
C | Removing left recursion and factoring the grammar |
D | None of the above |
To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
Question 28 |
Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is:
A | n1 is necessarily less than n2 |
B | n1 is necessarily equal to n2
|
C | n1 is necessarily greater than n2
|
D | None of the above |
Question 29 |
In a bottom-up evaluation of a syntax directed definition, inherited attributes can
A | always be evaluated |
B | be evaluated only if the definition is L-attributed |
C | be evaluated only if the definition has synthesized attributes |
D | never be evaluated |
L-Attributed definitions are a class of syntax directed definitions whose attributes can be evaluated by a single traversal of the parse-tree.
Question 30 |
Which of the following statements is FALSE?
A | In statically typed languages, each variable in a program has a fixed type |
B | In un-typed languages, values do not have any types |
C | In dynamically typed languages, variables have no types |
D | In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program
|
Question 31 |
Consider the grammar shown below
S → i E t S S' | a S' → e S | ε E → b
In the predictive parse table. M, of this grammar, the entries M[S’, e] and M[S’, $] respectively are
A | {S’→e S} and {S’→ε} |
B | {S’→e S} and { } |
C | {S’→ε} and {S’→ε} |
D | {S’→e S, S’→ε} and {S’→ε} |
First(S’) = {e,ε}
First(E) = {b}
Follow(S’) = {e,$}
Only when ‘First’ contains ε, we need to consider FOLLOW for getting the parse table entry.

Hence, option (D) is correct.
Question 32 |
Consider the grammar shown below.
S → C C C → c C | d
The grammar is
A | LL(1) |
B | SLR(1) but not LL(1)
|
C | LALR(1) but not SLR(1) |
D | LR(1) but not LALR(1)
|

Hence, it is LL(1).
Question 33 |
Consider the translation scheme shown below.
S → T R R → + T {print ('+');} R|ε T → num {print(num.val);}
Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string ‘9 + 5 + 2’, this translation scheme will print
A | 9 + 5 + 2 |
B | 9 5 + 2 + |
C | 9 5 2 + + |
D | + + 9 5 2 |

Now traverse the tree and whatever comes first to print, just print it.
Answer will be 9 5 + 2 +.
Question 34 |
Consider the syntax directed definition shown below.
S → id := E {gen (id.place = E.place;);} E → E1 + E2 {t = newtemp ( ); gen(t = E1.place + E2.place;); E.place = t} E → id {E.place = id.place;}
Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that ti’s are the temporary variable names generated by newtemp. For the statement ‘X: = Y + Z’, the 3-address code sequence generated by this definition is
A | X = Y + Z |
B | t1 = Y + Z; X = t1 |
C | t1= Y; t2 = t1 + Z; X = t2 |
D | t1 = Y; t2 = Z; t3 = t1 + t2; X = t3
|

Question 35 |
Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?
A | Smaller sizes of executable files |
B | Lesser overall page fault rate in the system |
C | Faster program startup
|
D | Existing programs need not be re-linked to take advantage of newer versions of libraries |
Question 36 |
Which of the following grammar rules violate the requirements of an operator grammar? P,Q,R are nonterminals, and r,s,t are terminals.
- (i) P → Q R
(ii) P → Q s R
(iii) P → ε
(iv) P → Q t R r
A | (i) only |
B | (i) and (iii) only |
C | (ii) and (iii) only |
D | (iii) and (iv) only |
i) On RHS it contains two adjacent non-terminals.
ii) Have nullable values.
Question 37 |
Consider a program P that consists of two source modules M1 and M2 contained in two different files. If M1 contains a reference to a function defined in M2, the reference will be resolved at
A | Edit time |
B | Compile time |
C | Link time |
D | Load time |
Question 38 |
Consider the grammar rule E → E1 – E2 for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If E1 and E2 do not have any common sub expression, in order to get the shortest possible code
A | E1 should be evaluated first
|
B | E2 should be evaluated first |
C | Evaluation of E1 and E2 should necessarily be interleaved |
D | Order to evaluation of E1 and E2 is of no consequence
|
Question 39 |
Consider the grammar with the following translation rules and E as the start symbol.
E → E1 # T {E.value = E1.value * T.value} | T {E.value = T.value} T → T1 & F {T.value = T1.value + F.value} | F {T.value = F.value} F → num {F.value = num.value}
Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.
A | 200 |
B | 180 |
C | 160 |
D | 40 |
2 # 3 & 5 # 6 & 4
→ Here # means multiplication (*)
& means addition (+)
→ & is having more precedence because it is far from starting symbol, here # and & are left associatives.
2 # 3 & 5 # 6 & 4
⇒ (2 * (3+5)) * (6+4)
⇒ (2 * 8) * (10)
⇒ 16 * 10 = 160
Question 40 |
Consider the following grammar G:
S → bS| aA| b A → bA| aB B → bB| aS |a
Let Na(w) and Nb(w) denote the number of a’s and b’s in a string w respectively. The language L(G) ⊆ {a, b}+ generated by G is
A | {w|Na(w) > 3Nb(w)}
|
B | {w|Nb(w) > 3Na(w)} |
C | {w|Na(w) = 3k, k ∈ {0, 1, 2, …}}
|
D | {w|Nb(w) = 3k, k ∈ {0, 1, 2, …}} |
S→baA
S→babA
S→babaB
S→babaa
n(a)=3; n(b)=2
Option A:
Na(w) > 3Nb(w)
3 > 3(2)
3 > 6 (✖️)
Option B:
Nb(w) > 3Nb(w)
2 > 3(2)
2 > 6 (✖️)
Option D:
Nb(w) = 3k
2 = 3k(✖️)
S = aA
S→aA
S→abA
S→abaB
S→abaa
n(a)=3
|n(a)|=3
→ Answer: Option C(✔️)
Question 41 |
The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is:
A | ambiguous |
B | left-recursive |
C | right-recursive |
D | an operator-grammar |
It have A → AA has left recursion.
Question 42 |
Consider the grammar:
E → E + n | E × n | n
For a sentence n + n × n, the handles in the right-sentential form of the reduction are:
A | n, E + n and E + n × n |
B | n, E + n and E + E × n
|
C | n, n + n and n + n × n |
D | n, E + n and E × n |
→ E + E * n {Applying E → E * n}
→ E + n * n {Applying E → n}
→ n + n * n {Applying E → n}
We use n, E+n, E×n reductions to get a sentence n+n*n.
Question 43 |
Consider the grammar:
S → (S) | a
Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good:
A | n1 < n2 < n3 |
B | n1 = n3 < n2 |
C | n1 = n2 = n3 |
D | n1 ≥ n3 ≥ n2 |
→ LR(1) be the states of LR(1) items.
→ LR(0) items never be greater than LR(1) items then SLR(1) = LALR(1) < LR(1)
n1 = (n3) < (n2)
Question 44 |
Consider line number 3 of the following C-program.
int main ( ) { /* Line 1 */ int I, N; /* Line 2 */ fro (I = 0, I < N, I++); /* Line 3 */ }
Identify the compiler's response about this line while creating the object-module:
A | No compilation error
|
B | Only a lexical error |
C | Only syntactic errors |
D | Both lexical and syntactic errors |
Question 45 |
Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production.
E → number E.val = number. val |E '+' E E(1).val = E(2).val + E>sup>(3).val |E '×' E E(1).val = E(2).val × E(3).val
The above grammar and the semantic rules are fed to a yacc tool (which is an LALR(1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?
A | It detects recursion and eliminates recursion
|
B | It detects reduce-reduce conflict, and resolves
|
C | It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action |
D | It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action
|
Question 46 |
Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production.
E → number E.val = number. val |E '+' E E(1).val = E(2).val + E>sup>(3).val |E '×' E E(1).val = E(2).val × E(3).val
Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?
A | Equal precedence and left associativity; expression is evaluated to 7
|
B | Equal precedence and right associativity; expression is evaluated to 9 |
C | Precedence of '×' is higher than that of '+', and both operators are left associative; expression is evaluated to 7 |
D | Precedence of '+' is higher than that of '×', and both operators are left associative; expression is evaluated to 9 |

Hence, the answer is 9 and right associative.
Question 47 |
Consider the following grammar.
S → S * E S → E E → F + E E → F F → id
Consider the following LR(0) items corresponding to the grammar above.
(i) S → S * .E (ii) E → F. + E (iii) E → F + .E
Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?
A | (i) and (ii) |
B | (ii) and (iii) |
C | (i) and (iii) |
D | None of the above |

Question 48 |
Consider these two functions and two statements S1 and S2 about them
int work1(int *a, int i, int j) int work2(int *a, int i, int j) { { int x = a[i+2]; int t1 = i+2; a[j] = x+1; int t2 = a[t1]; return a[i+2] – 3; a[j] = t2+1; } return t2 – 3; }
- S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1
S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1
A | S1 is false and S2 is false
|
B | S1 is false and S2 is true |
C | S1 is true and S2 is false |
D | S1 is true and S2 is true |
So, given statement is wrong.
S1: Let us assume an array = {1,2,3,4,5} and i=0.
Let j = i+2 = 0+2 = 2
For the respective example work1 and work2 results 1 and 0, so S1 statement is False.
Question 49 |
Consider the following grammar:
S → FR R → S | ε F → id
In the predictive parser table, M, of the grammar the entries M[S,id] and M[R,$] respectively.
A | {S → FR} and {R → ε}
|
B | {S → FR} and { } |
C | {S → FR} and {R → *S} |
D | {F → id} and {R → ε} |

The representation M[X,Y] means X represents Variable (rows) and Y represents terminals (columns).
The productions are filled in parsing table by the below mentioned rules:
For every production P → α, we have:
Rule 1: If P → α is a production then add this production for each terminal “t” which is in FIRST of [α] i.e., ADD P → α to M[P, a]
Rule 2: If “ϵ” belongs to FIRST of [P] then add P → α to M[P, b] where “b” represents terminals FOLLOW[P].
By the above rules, we can see that production S → FR will go M[S, a] where “a” is FIRST [FR] which is equal to FIRST[F] = id, So S → FR will go in M[S,id].
Since in the production R→ϵ , FIRST[ϵ] = ϵ, hence the production will go in M[R, b] where “b” represents terminals FOLLOW[R] and FOLLOW[R] = $, so production R→ϵ will go in M[R,$]
Question 50 |
Consider the following translation scheme.
S → ER R → *E{print("*");}R|ε E → F + E {print("+");}|F F → (S)|id {print(id.value);}
Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints
A | 2 * 3 + 4 |
B | 2 * +3 4
|
C | 2 3 * 4 + |
D | 2 3 4+* |

Now perform post order evaluation, you will get output as,
2 3 4 + *