Category: Compilers Objective Questions

Compilers Multiple Choice Questions & Answers (MCQs) on “Predictive Top-Down Parsing”.

1. Find the TRUE statement?

I.  There exist parsing algorithms for some programming languages which has O(3) complexity.
II.  A programming language which allows recursion can be implemented with static storage allocation.
III. No L-attributed definition can be evaluated in The framework of bottom-up parsing.
IV. Code improving transformations can be performed at both intermediate code level and source Language.

a) I and II
b) I and IV
c) III and IV
d) I III and IV

Answer: b
Clarification: In recursion, space used but recursive call can’t be calculated by the compiler.

2. Which of the following describes a handle (as applicable to LR-parsing) appropriately?
a) Position where next reduce or shift operation will occur
b) The next step has use of Non-terminal for reduction
c) Used for reduction in a coming-up step along with a position in the sentential form where the next shift or reduce operation will occur
d) Used in the next step for reduction along with a position in the sentential form where the right hand side of the production may be found

Answer: d
Clarification: the next step in LR parsing shall have a Reduction.

3. Which one of the following is a top-down parser?
a) Recursive descent parser
b) Operator precedence parser
c) An LR(k) parser
d) An LALR(k) parser

Answer: a
Clarification: Recursive Descent also known as top down parsing also known to be LL(1).
Consider the following two statements:
P: Every regular grammar is LL(1)
Q: Regular is LR(1) grammar.

4. Which of the following is TRUE?
a) Both P and Q are true
b) P is true and Q is false
c) P is false and Q is true
d) Both P and Q are false

Answer: c
Clarification: Ambiguity can be seen in regular grammar
S → aA/a
A → aA/ε
In above grammar, string ‘a’ has two leftmost
derivations.
S → aA
S → a
S->a (using A->ε).

5. Consider the grammar defined by the following production rules:

    S --> T * P 
    T --> U | T * U
    P --> Q + P | Q
    Q --> Id
    U --> Id

Which one of the following is TRUE?
a) + is left associative, while ∗ is right associative
b) + is right associative, while ∗ is left associative
c) Both + and ∗ are right associative
d) Both + and ∗ are left associative

Answer: b
Clarification: It is associative we can see and tell.
Second productions latter part shows left recursion and is left associative.

6. The grammar A → AA | (A) | e is not suitable for predictive-parsing because the grammar is?
a) Ambiguous
b) Left recursive
c) Right recursive
d) An operator grammar

Answer: b
Clarification:
A ::= A a
| b is the left recursive language.

7. 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 + n × n
c) n, n + n and n + n × n
d) n, E + n and E × n

Answer: d
Clarification: E → E + n {Applying E → E + n }
→ E + E * n {Applying E → E * n }
→ E + n * n {Applying E → n }
→ n + n * n {Applying E → n }.

8. Which grammar rules violate the requirements of an operator grammar?

1.  P → Q R                    
2.  P → Q s R
3.  P → ε       
4.  P → Q t R r

a) 1 only
b) 1 and 3 only
c) 2 and 3 only
d) 3 and 4 only

Answer: b
Clarification: Top down parsin: We begin with the start symbol and compare the right side of the different productions against the first piece of input to see which of the productions should be used.

9. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
a) Removing left Recursive alone
b) Factoring the grammar alone
c) Along with removing left recursion we also perform the factoring of the grammar
d) None of the mentioned

Answer: d
Clarification: Removing left recursion and factoring the grammar do not suffice to convert an arbitrary CFG to LL(1) grammar.

10. In a bottom-up evaluation of a syntax directed definition its inherited attributes can do which of the following?
a) Always evaluated
b) Can be evaluated if the definition is L attributed
c) Can be evaluated if the definition has synthesized attributes
d) Never be evaluated

Answer: b
Clarification: A Syntax Directed Definition (SDD) is called S Attributed if it has only synthesized attributes. Also the L-Attributed Definitions contain both synthesized and inherited attributes but do not need to build a dependency graph to evaluate them.

Compilers Multiple Choice Questions & Answers (MCQs) on “Intermediate code-Generation”.

1. The below 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?

 E -> number   Eval           number val 
     E         E .val         E .VAL           E .val 
    E # E      E .val         E .VAL           E .val 
     ;

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

Answer: c
Clarification: Yacc tool is used to create a LALR (1) parser. This parser can detect the conflicts but to resolve the conflicts it actually prefers shift over reduce action.

2. Assume the conflicts 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?

  E -> number        Eval               number val 
   E                 E .val             E .VAL                  E .val 
  E # E              E .val             E .VAL                  E .val 
   ;

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 ‘x’ 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

Answer: b
Clarification: The grammar has equal precedence and it is also ambiguous. Since LALR (1) parser prefer shift over reduce so + operation will be executed here before). 2 + 1 = 3 & 3 # 3 = 9 also the operators are right associative.

3. 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) (ii)
b) (i) and (iii)
c) (iii)
d) None of the mentioned

Answer: c
Clarification: If S -> S): E is in LR (0) then E -> F +: E will also be there because both of them has ‘: ‘ before E.

4. 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 ” ε}

Answer: a
Clarification: The predictive parser table is given as. Non Terminal) id $ S S “FR F F “id R R “) S R “! R “! So at M [ S, id] = { S ” FR} M [ R,$] = {R “!}.

5. Consider the following translation scheme.

S -> ER 
R -> * E{print{’ * ’);
R | f 
E -> F + E{print(’ + ’); | F 
F -> (S) | id{print(id.value);}

Here id is a taken 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 + *

Answer: b
Clarification: Input string 2 ) 3 + 4 S ” ER FR idR {print(2)} id)ER {print())} id) F+ER {print(+)}id) id + ER {print(3)} id) id ) id +id So 2 )+ 3 4 are printed.

6. Consider the following C code segment.

for for if i # i } } }

Which one to the following false?
a) The code contains loop-in variant computation
b) There is scope of common sub-expression elimination in this code
c) There is scope strength reduction in this code
d) There is scope of dead code elimination in this code

Answer: d
Clarification: All the statements are true except option (There is scope of dead code elimination in this code ) since there is no dead code to get eliminated.

7. Which one of the following grammars generates the language L = (a i b i | i ! j}?
a)

b)

S -> aS | Sb | a | b 
C -> aCb | a | b 
A -> aA | ε 
B -> Bb | ε

c)

d)

S -> AC | CB 
C -> aCb |!
C -> aCb |! 
A -> aA |! 
A -> aA | a 
B -> Bb |! 
B -> bB | b

View Answer

Answer: d
Clarification: The grammar S -> AC CB
C ->aCb !
A ->aA a
B->” bB b
Consider string aaabb S -> AC AaCb AaaCbb Aaabb aaabb But string aabb S ” AC And ->his string is not derivable.

8. In the correct grammar above, what is the length of the derivation (number of steps starting from S to generate the string a l b m with l ! m?
a) max (l, m) + 2
b) l+m+2
c) l + m + 3
d) max (l, m) + 3

Answer: a
Clarification: It is very clear from the previous solution that the no. of steps required depend upon the no. of a’ s & b ‘ s which ever is higher & exceeds by 2 due to S ” AC CB & C “! So max(l , m) + 2.

9. Which one of the following is a top-down parser?
a) Recursive descent parser
b) Operator precedence parser
c) An LR(k) parser
d) An LALR(k) parser

Answer: a
Clarification: Clearly LR & LALR are not top down they are bottom up passers. Also not operator precedence parser. ut yes recursive descent parser is top down parser. Starts from start symbol & derives the terminal string.

10. Consider the grammar with non-terminals.

N = {S , C , S}, terminals T = {a, b , i , t, e}, with S as the start symbol, and the following of rules 
S -> iCtSS1 | a 
S1 -> eS | ε 
C -> b

The grammar is NOTLL(1) because ________
a) It is left recursive
b) It is right recursive
c) It is ambiguous
d) It is not context-free

Answer: a
Clarification: The grammar has production S ” iCtSS1 here the right hand side of grammar has the same symbol as left side. So the grammar is left recursive. The grammar is not ambiguous.

Compilers Multiple Choice Questions & Answers (MCQs) on “Storage Allocation”.

1. The idea of cache memory is based __________
a) On the property of locality of reference
b) On the heuristic 90-10 rule
c) On the fact that references generally tend to cluster
d) All of the mentioned

Answer: a
Clarification: Cache memory is based on the locality of references.

2. Which of the following is not a weighted code?
a) Decimal Number system
b) Excess 3-cod
c) Binary number System
d) None of the mentioned

Answer: b
Clarification: Excess 3 is not a weighted code.

3. The average time required to reach a storage location in memory and obtain its contents is called the _____
a) Seek time
b) Turnaround time
c) Access time
d) Transfer time

Answer: c
Clarification: Times used to access the contents.

4. (2FAOC) 16 is equivalent to __________
a) (195 084)10
b) (001011111010 0000 1100)2
c) (195 084)10 & (001011111010 0000 1100)2
d) None of the mentioned

Answer: b
Clarification: It is equivalent to (001011111010 0000 1100)2.

5. The circuit used to store one bit of data is known as_______
a) Register
b) Encoder
c) Decoder
d) Flip Flop

Answer: d
Clarification: 1 bit circuit is known as Flip Flop.

6. Computers use addressing mode techniques for ____________
a) Giving programming versatility to the user by providing facilities as pointers to memory counters for loop control
b) To reduce number of bits in the field of instruction
c) Specifying rules for modifying or interpreting address field of the instruction
d) All of the mentioned

Answer: d
Clarification: All of these are addressing mode techniques.

7. What characteristic of RAM memory makes it not suitable for permanent storage?
a) Too slow
b) Unreliable
c) It is volatile
d) Too bulky

Answer: c
Clarification: Ram is volatile.

8. The amount of time required to read a block of data from a disk into memory is composed of seek time, rotational latency, and transfer time. Rotational latency refers to ______
a) The time it takes for the platter to make a full rotation
b) The time it takes for the read-write head to move into position over the appropriate track
c) The time it takes for the platter to rotate the correct sector under the head
d) None of the mentioned

Answer: a
Clarification: Rotational latency is the time taken to make full rotation.

Compilers Multiple Choice Questions & Answers (MCQs) on “Lexical Analysis”.

1. What is the output of lexical analyzer?
a) A set of RE
b) Syntax Tree
c) Set of Tokens
d) String Character

Answer: c
Clarification: A lexical analyzer coverts character sequences to set of tokens.

2. Which symbol table implementation is based on the property of locality of reference?
a) Linear list
b) Search tree
c) Hash Table
d) Self Organisation

Answer: c
Clarification: Hash table is used as a reference for symbol table because it is efficient.

3. Which of the following is true for operator precedence parsing?
a) For all pair of non-terminal
b) For all pair of non-terminals
c) To delimit the handle
d) None of the mentioned

Answer: a
Clarification: There are two important properties for these operator precedence parsers is that it does not appear on the right side of any production and no production has two adjacent non-terminals. Implying that no production right side is empty or has two adjacent non-terminals. So accordingly to property option (A) is correct.

4. What is an Object program?
a) Program written in machine language
b) Program to be translated into machine language
c) Translation of high-level language into machine language
d) None of the mentioned

Answer: c
Clarification: Since the input is the source language and the output that we get after the analysis is the machine language.

5. Which concept of FSA is used in the compiler?
a) Lexical analysis
b) Parser
c) Code generation
d) Code optimization

Answer: a
Clarification: Because the lexer performs its analysis by going from one stage to another.

6. Which concept of grammar is used in the compiler?
a) Lexical analysis
b) Parser
c) Code generation
d) Code optimization

Answer: b
Clarification: As the lexical analysis of a grammar takes place in phases hence it is synonymous to parser.

7. Which of the following are Lexemes?
a) Identifiers
b) Constants
c) Keywords
d) All of the mentioned

Answer: d
Clarification: Different Lexical Classes or Tokens or Lexemes Identifiers, Constants, Keywords, Operators.

Compilers Multiple Choice Questions on “Minimization of DFA”.

1. Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2* U L1*?
a) €
b) a*
c) All of the mentioned
d) None of the mentioned

Answer: a
Clarification: L1* = * which is { }.

2. Given the language L = {ab, aa, baa}, which of the following strings are in L*?

1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

a) 1, 2, 3
b) 2, 3, 4
c) 1, 2, 4
d) 1, 3, 4

Answer: c
Clarification: The given alphabet ∑ contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’.

3. Which one of the following languages over the alphabet {0,1} is described by the regular expression?

(0+1)*0(0+1)*0(0+1)*

a) String with substring 00
b) String with at most two 0’s
c) String containg at least two 0’s
d) None of the mentioned

Answer: c
Clarification: The regular expression has two 0′s surrounded by (0+1)* which means accepted strings must have at least 2 0′s.

4. Which one of the following is FALSE?
a) Every NFA can be converted to DFA
b) Every subset of a recursively enumerable set is recursive
c) All of the mentioned
d) None of the mentioned

Answer: b
Clarification: Every subset of a recursively enumerable set is recursive.

5. Which of the following are regular sets?

I. { an b2m | n>=0, m>=0}
II. {an bm |n=2m}
III. {an bm | n!= m}
IV {xcy |x,y€{a,b)*}

a) I and IV
b) I and III
c) I and only
d) IV

Answer: a
Clarification: We can write DFA for both I and IV.