Compiler-Design
Question 1 |

Which one of the following choices represents the correct combination for the numbered cells in the parsing table (“blank” denotes that the corresponding cell is empty)?
A | ① S ⟶ Rf ② S ⟶ Rf ③ T ⟶ ∊ ④ T ⟶ ∊
|
B | ① blank ② S ⟶ Rf ③ T ⟶ ∊ ④ T ⟶ ∊ |
C | ① S ⟶ Rf ② blank ③ blank ④ T ⟶ ∊ |
D | ① blank ② S ⟶ Rf ③ blank ④ blank |

Question 2 |
P ⟶ D* E*
D ⟶ int ID {record that ID.lexeme is of type int}
D ⟶ bool ID {record that ID.lexeme is of type bool}
E ⟶ E1 + E2 {check that E1.type = E2.type = int; set E.type := int}
E ⟶ !E1 {check that E1.type = bool; set E.type := bool}
E ⟶ ID {set E.type := int}
With respect to the above grammar, which one of the following choices is correct?
A | The actions can be used to type-check syntactically correct integer variable declarations and integer expressions. |
B | The actions will lead to an infinite loop. |
C | The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions. |
D | The actions can be used to correctly type-check any syntactically correct program. |
Question 3 |
S1:Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
S2: For any context-free grammar, there is a parser that takes at most O(n3 )
Which one of the following options is correct?
A | S1is true and S2is true
|
B | S1is true and S2is false |
C | S1is false and S2is true |
D | S1is false and S2is false |
Every unambiguous grammar need not be SLR(1). As we know some unambiguous grammar which is CLR(1) but not SLR(1). So S1 is true.
Any CFG (which is in CNF form) can be parsed by CYK algorithm in O(n3) where n is length of string. Although it is not given that CFG is in CNF form but since we can convert any CFG in CNF form so S2 is true
Question 4 |
a = b + c;
e = a + 1;
d = b + c;
f = d + 1;
g = e + f;
In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes in the DAG is _______
A | 6 |
Question 5 |
Suppose we have a computer with a single register and only three instructions given below:
LOAD addren ; load register ; from addren STORE addren ; store register ; at addren ADD addren ; add register to ; contents of addren ; and place the result ; in the register
Consider the following grammar:
A → id :=E E → E + T|T T → (E)|id
Write a syntax directed translation to generate code using this grammar for the computer described above.
A | Theory Explanation. |
Question 6 |
Match the following items

A | (i) - (d), (ii) - (a), (iii) - (b), (iv) - (c) |
Yacc (Yet Another Compiler- Compiler) is a computer program for the UNIX operating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specially a LALR parser, based on an analytic grammar. Yacc is written in portable C.
Question 7 |
Generation of intermediate code based on an abstract machine model is useful in compilers because
A | it makes implementation of lexical analysis and syntax analysis easier |
B | syntax-directed translations can be written for intermediate code generation |
C | it enhances the portability of the front end of the compiler |
D | it is not possible to generate code for real machines directly from high level language programs |
Question 8 |
Construct the LL(1) table for the following grammar.
1. Expr → _Expr 2. Expr → (Expr) 3. Expr → Var Expr Tail 4. ExprTail → _Expr 5. ExprTail → λ 6. Var → Id Var Tail 7. VarTail → (Expr) 8. VarTail → λ 9. Goal → Expr$
A | Theory Explanation. |
Question 9 |
(a) Translate the arithmetic expression a*-(b+c) into syntax tree.
(b) A grammar is said to have cycles if it is the case that
A ⇒ +A
Show that no grammar that has cycles can be LL(I).
A | Theory Explanation. |
Question 10 |
A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar
S → xxW {print "1"} S → y {print "2"} W → Sz {print "3"}
What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?
A | 23131 |
B | 11233 |
C | 11231 |
D | 33211 |

⇒ 23131
Note SR is bottom up parser.
Question 11 |
A linker is given object modules for a set of programs that were compiled separately. What information need to be included in an object module?
A | Object code |
B | Relocation bits |
C | Names and locations of all external symbols defined in the object module
|
D | Absolute addresses of internal symbols |
To link to external symbols it must know the location of external symbols.
Question 12 |
Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e initially stored in memory. The binary operators used in this expression tree can be evaluate by the machine only when the operands are in registers. The instructions produce results only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

A | 2 |
B | 9 |
C | 5 |
D | 3 |
Load R2, b ; R2 ← M[b]
Sub R1, R2 ; R1 ← R1 – R2
Load R2, c ; R2 ← M[c]
Load R3, d ; R3 ← M[d]
Add R2, R3 ; R2 ← R2 + R3
Load R3, e ; R3 ← M[e]
Sub R3, 3 ; R3 ← R3 – R2
Add R1, R3 ; R1 ← R1 + R3
Total 3 Registers are required minimum.
Question 13 |
Consider two binary operators ‘↑’ and ‘↓’ with the precedence of operator ↓ being lower than that of the operator ↑. Operator ↑ is right associative while operator ↓, is left associative. Which one of the following represents the parse tree for expression (7↓3↑4↑3↓2)?
A | ![]() |
B | ![]() |
C | ![]() |
D | ![]() |
⇒ 7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2
⇒ 7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative
Question 14 |
In a compiler, keywords of a language are recognized during
A | parsing of the program |
B | the code generation |
C | the lexical analysis of the program |
D | dataflow analysis |
Question 15 |
The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
A | Finite state automata |
B | Deterministic pushdown automata |
C | Non-Deterministic pushdown automata |
D | Turing machine |
Question 16 |
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 17 |
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 18 |
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 19 |
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 20 |
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 21 |
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 22 |
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 23 |
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 24 |
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 25 |
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 26 |
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 27 |
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 28 |
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 29 |
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 30 |
Type checking is normally done during
A | lexical analysis |
B | syntax analysis |
C | syntax directed translation |
D | code optimization |
Question 31 |
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 32 |
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 33 |
Which of the following is the most powerful parsing method?
A | LL (1) |
B | Canonical LR |
C | SLR |
D | LALR |
LR > LALR > SLR
Question 34 |
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 35 |
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 36 |
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 37 |
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 38 |
(a) Remove left-recursion from the following grammar:
S → Sa| Sb | a | b
(b) Consider the following grammar:
S → aSbS| bSaS |ε
Construct all possible parse trees for the string abab. Is the grammar ambiguous?
A | Theory Explanation is given below. |
Question 39 |
Consider the following grammar with terminal alphabet ∑{a,(,),+,*} and start symbol E. The production rules of the grammar are:
E → aA E → (E) A → +E A → *E A → ε
(a) Compute the FIRST and FOLLOW sets for E and A.
(b) Complete the LL(1) parse table for the grammar.
A | Theory Explanation is given below. |
Question 40 |
The syntax of the repeat-until statement is given by the gollowing grammar
S → repeat S1 until E
Where E stands for expressions, S and S1 stand for statement. The non-terminals S and S1 have an attribute code that represents generated code. The nonterminal E has two attributes. The attribute code represents generated code to evaluate the expression and store its truth value in a distinct variable, and the attribute varName contains the name of the variable in which the truth value is stored? The truth-value stored in the variable is 1 if E is true, 0 if E is false.
Give a syntax-directed definition to generate three-address code for the repeatuntil statement. Assume that you can call a function newlabel( ) that returns a distinct label for a statement. Use the operator ‘\\’ to concatenate two strings and the function gen(s) to generate a line containing the string s.
A | Theory Explanation is given below. |
Question 41 |
The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called
A | Assembly |
B | Parsing |
C | Relocation |
D | Symbol resolution |
Question 42 |
Which of the following statements is false?
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 |
Option C: LALR is more powerful than SLR.
Option D: An ambiguous grammar can never be LR (k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.
Question 43 |
(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 44 |
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 45 |
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 46 |
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 47 |
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 48 |
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 49 |
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 50 |
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.