Theory of Computation and Compiler Design
Section-A
1 .What is compiler? Explain its phases with diagram.
2 .What is lexical analyser? Explain how token is identified?
3 .What is parser? Explain LR parser.
4 .What is intermediate code? What type of intermediate code is used in compiler?
5 .What is symbol table? Explain any two data structure to maintain symbol table.
6 .What is flow control? Explain basic block with a suitable example.
7 .Explain the issues related to code generation.
Section-B
1. Explain three addressing code with a suitable example.
2. The Example which is taken for three addressing mode, make direct acyclic graph (DAG) for the same.
3. What is code optimization and code generation?
Section-C
Question No. 1 Marks - 10
Suppose L={am bn:n=1} then L is
Options
Regular
Context free but not Regular
Context sensitive but not Context free
None of these
Question No. 2 Marks - 10
In a compiler, Parsing is done by
Options
Lexical
syntax
Code generation
Code optimization
Question No. 3 Marks - 10
Contaxt-free grammar is also known as
Options
Type-0
Type-1
Type-2
Type-3
Question No. 4 Marks - 10
A top-down parser generates
Options
Left most derivation
Right most derivation
Left most derivation in reverse
Right most derivation in reverse
Question No. 5 Marks - 10
A Bottom-up parser generates
Options
Left most derivation
Right most derivation
Left most derivation in reverse
Right most derivation in reverse
Question No. 6 Marks - 10
A grammar is said to be Ambiguous if
Options
Two or more productions have the same nonterminal on the left hand side
A derivation tree has more than associated sentence
a sentence with more than one derivation tree
Brackets are not present in the grammar
Question No. 7 Marks – 10
Which of the following is NOT a Context-free-grammar
Options
S-->Aba/B B-->b
S-->AbA/b/A A-->b
S-->aA/b A-->bA/b
S-->aSa/bSb/e
Question No. 8 Marks - 10
Suppose L1 and L2 are two Regular Language, then which one is true?
Options
Union of L1 and L2 is also regular
Concatenation of L1 and L2 is also regular
Complement of L1 or L2 is also Regular
All of these
Question No. 9 Marks - 10
Suppose L1 and L2 are two context-free Language, then which one is False
Options
Union of L1 and L2 is also Cntext-free
Concatenation of L1 and L2 is also Context-free
Complement of L1 is also Context-free
All of these
Question No. 10 Marks - 10
The concept of FSA is much used in this part of the compiler
Options
Lexical Analysis
Parser
Code generation
Code optimization
Question No. 11 Marks - 10
The concept of grammar is much used in this part of the compiler
Options
Lexical Analysis
Parser
Code generation
Code optimization
Question No. 12 Marks - 10
The set of all strings over the alphabet S = {a, b} (excluding e) is denoted by
Options
(a + b)*
(a+b)+
a*b*
(a*+b*)
Question No. 13 Marks - 10
Which of the following denotes Chomskian hiearchy
Options
REG ? CFL ? CSL ? type0
CFL ? REG ? type0? CSL
CSL ? type0 ? REG ? CFL
CSL ? CFL ? REG ? type0
Question No. 14 Marks - 10
Which of the following regular expression identity is true
Options
p*=p(p*)
(p+ q)*=(p*q*)*
(p + q)* = p* + q*
p*q*= p*+q*
Question No. 15 Marks - 10
Which of the following conversion is not possible (algorithmically)?
Options
regular grammar to context-free grammar
nondeterministic FSA to deterministic FSA
nondeterministic PDA to deterministic PDA
nondeterministic TM to deterministic TM
Question No. 16 Marks - 10
Which of the following Parsing Technique is most powerfull
Options
SLR
LALR
Canonical LR
LL(1)
Question No. 17 Marks - 10
Cosider the Grammar (G): S?iEtSA/a A?eS/? E?b
Options
FIRST(S)={i,? }
FIRST(S)={i,a}
FIRST(S)={e,? }
None of these
Question No. 18 Marks - 10
Cosider the Grammar (G): S? iEtSA/a A? eS/? E?b
Options
FOLLOW(S)={e,?}
FOLLOW(S)={e,$}
FOLLOW(S) = {i?}
FOLLOW(S)={i, $}
Question No. 19 Marks - 10
Cosider the Grammar (G): S? iEtSA/a A? eS/? E?b then G is
Options
LL(1)
Not a LL(1)
SLR(1) but not LL(1)
None of these
Question No. 20 Marks - 10
A grammar is called Operetor precedence, if
Options
No production on the Right hand side has?
No two consecutive non-terminals on the Right side of any production
Both (1) and (2)
Only (2)
Question No. 21 Marks - 10
Which of the following grammar is Operator precedence
Options
S?aSa/bSb/ab
S?SAa/SAb/ab A?b
E?E+E/E*E/id/?
All of these
Question No. 22 Marks - 10
Consider the grammar(G): E?E+T/T T?T*F/F F?(E)/id then
Options
LEADING(E)={+,*,),id}
LEADING(E)={+,*,(,id}
LEADING(E)={+,*,id}
LEADING(E)={*,(,id}
Question No. 23 Marks - 10
Consider the grammar(G): E?E+T/T T?T*F/F F?(E)/id then
Options
TRAILING(T)={+,*,),id}
TRAILING(T)={*,),id}
TRAILING(T)={+,*,id}
TRAILING(T)={*,+,id}
Question No. 24 Marks - 10
After removing Left recursion for the production(s): A?Aa1/Aa2/…./Aan/ß1/…./ßm
Options
A?ßiA' A'?aiA'/?
A?ßiA' A'?aiA/a
A?aiA' A'?ßiA'/?
A?aiA' A'?ßiA'/b
Question No. 25 Marks - 10
Which of the following is NOT an Intermediate Code generation method
Options
Quadruples
triples
Indirect Triples
Parse tree
Question No. 26 Marks - 10
Top-Down parser always do the
Options
Left-most Derivation
Right-most derivation
Left-most derivation in reverse
Right-most derivation in reverse
Question No. 27 Marks - 10
Bottom-up parser always do the
Options
Left-most Derivation
Right-most derivation
Left-most derivation in reverse
Right-most derivation in reverse
Question No. 28 Marks - 10
Loading operating system from secondary memory to primary memory is called
Options
Compiling
Booting
Refreshing
Reassembling
Question No. 29 Marks - 10
A compiler for a high level language that runs on one machine and produces code for a different machine is called
Options
Optimizing
One pass compiler
Cross compiler
Multipass Compiler
Question No. 30 Marks - 10
A Tabular implementation of Recursive-descendent parser is also known as
Options
Predictive Parser
Operator precedence
SLR parser
LALR parser
Question No. 31 Marks - 10
In the context of compiler design, "reduction in strength" refers to
Options
Code optimization obtained by the use of cheaper machine instructions
Reduction in accuracy of the output
Reduction in the range of values of input variables
Reduction in the efficiency of the program
Question No. 32 Marks - 10
Symbol table can be used for
Options
Checking type compatibility
Supressing duplication of error message
Storage allocation
All of these
Question No. 33 Marks - 10
Which of the following is NOT a method to implement symbol table
Options
Linear list
Hash table
self-organizing list
parse tree
Question No. 34 Marks - 10
Consider the grammar (G): A?abAbc/abBbc/b/a ; After eliminating left factoring
Options
A?abA'/b/a A'?Abc/Bbc
A?abA'bc/abB'bc/b/a A'?? B'??
A?abbc/abbc/b/a
None of these
Question No. 35 Marks - 10
Cosider the grammar (G): E?E+T/T T?T*F/F F?(E)/id , the canonical collection of LR(0) set {i.e. I0 item is}
Options
E’? E E?.E+T T?.T*F F?.(E)/.id
E'?E E?.E+T/.T T?.T*F/.F F?.(E)/.id
E'?E E?E.+T/.T T?T.*F/.F F?.(E)/.id
All of these
Question No. 36 Marks - 10
Which of the following is related with code optimization
Options
loop optimization
Code motion
Induction variable elimination
All of these
Question No. 37 Marks - 10
Code motion referes to
Options
removing costly operator with cheaper one
Removing loop invarient computation
increasing space complexity
All of these
Question No. 38 Marks - 10
which language is accepted corresponds to grammar(G): S?0S0/1S1/0/1
Options
0*1*
1*0*
plindrome string over ?={0,1}
Even number of 0's and 1's
Question No. 39 Marks - 10
The logic of pumping lemma is a good example of
Options
pigeon-hole principle
recursion
iteration
Divide & conquer technique
Question No. 40 Marks - 10
Intermediate code generation of compiler phase takes input from
Options
Lexical analyzer
code optimizer
Syntax Analyzer
semantic Analyzer
University: AMITY