MCA VI Sem.
Theory of Computation and Compiler Design
Section-A
1 . What is compiler? Explain its phases with diagram.
2 . What is lexical analyzer? 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
________________________________________
Cross-compiler is a compiler
Options
Which is written in a language that is different from the source language.
That generates object code for its host machine.
Which is written in a language that is same as the source language.
That runs on one machine but produces object code for another machine.
Question No. 2 Marks - 10
________________________________________
For which of the following reasons, an interpreter is preferred to a compiler?
Options
It takes less time to execute.
It is much helpful in the initial stages of program development
Debugging can be faster and easier.
It needs less computer resources.
Question No. 3 Marks - 10
________________________________________
The cost of developing a compiler
Options
is proportional to the complexity of the source language.
is proportional to the complexity of the architecture of the target machine.
is proportional to the complexity of the available instruction set
none of the above.
Question No. 4 Marks - 10
________________________________________
An optimizing compiler
Options
is optimized to occupy less space.
is optimized to less time for execution.
Optimizes the code.
None of the above.
Question No. 5 Marks - 10
________________________________________
In a compiler grouping of characters into tokens is done by
Options
Scanner.
Parser.
Code generator.
Code optimizer.
Question No. 6 Marks - 10
________________________________________
Whether a given pattern constitutes a token or not
Options
Depends on the source language.
Depends on the target language.
Depends on the compiler.
None of the above comments are true.
Question No. 7 Marks - 10
________________________________________
Which of the following grammars or not phase-structured?
Options
Regular.
Context-free.
Context- sensitive.
None of the above.
Question No. 8 Marks - 10
________________________________________
Which of the following is the most general phase-structured grammar?
Options
Regular.
Context-free.
Context- sensitive.
None of the above.
Question No. 9 Marks - 10
________________________________________
In a context-free grammar,
Options
? can not be the right hand side of any production.
Terminal symbol can’t be present in the left hand side of any production
The number of grammar symbols in the left hand side is not greater than the number of grammar symbols in the right hand side.
All of the above.
Question No. 10 Marks - 10
________________________________________
If w is a string of terminals and A, B are two non terminals, then which of the following are right-liner grammar?
Options
A ? Bw.
A ? Bw/w
A ? wB ? w
None of the above.
Question No. 11 Marks - 10
________________________________________
Representing the syntax by a grammar is advantageous because
Options
It is concise.
It is accurate.
Automation becomes easy.
Intermediate code can be generated easily and efficiently.
Question No. 12 Marks - 10
________________________________________
CFG can be recognized by a
Options
push-down automata.
2-way linear bounded automata.
Finite state automata.
None of the above.
Question No. 13 Marks - 10
________________________________________
CSG can be recognized by a
Options
push-down automata.
2-way linear bounded automata
Finite state automata.
None of the above.
Question No. 14 Marks - 10
________________________________________
A top-down parser generates.
Options
left-most derivation.
right-most derivation.
right-most derivation in reverse.
left-most derivation in reverse.
Question No. 15 Marks - 10
________________________________________
A bottom-up parser generates.
Options
left-most derivation.
right-most derivation.
right-most derivation in reverse.
left-most derivation in reverse.
Question No. 16 Marks - 10
________________________________________
Choose the correct statement.
Options
language corresponding to a grammar, is the set of all strings that can be generated by the given grammar.
A given language is ambiguous if no unambiguous grammar exists for it.
Two different grammars may generate the same language.
None of the above.
Question No. 17 Marks - 10
________________________________________
Synthesized attribute can be easily simulated by a
Options
LL grammar
Ambiguous grammar.
LR grammar
None of the above
Question No. 18 Marks - 10
________________________________________
Syntax directed transaction scheme is desirable because
Options
it is based on the syntax
its description is independent of any implementation
it is easy to modify.
Only a. and c. are correct.
Question No. 19 Marks - 10
________________________________________
Three address code can be implemented by
Options
Indirect triples.
Direct triples.
Quadruples.
None of the above.
Question No. 20 Marks - 10
________________________________________
Symbol table can be used for
Options
Checking type compatibility.
Suppressing duplication of error messages.
Storage allocation.
None of the above.
Question No. 21 Marks - 10
________________________________________
Which of the following symbol table implementation is based on the property of locality of reference?
Options
Linear list.
Search tree.
Hash Table.
Self-organization list.
Question No. 22 Marks - 10
________________________________________
Access time of the symbol table will be logarithmic, if it is implemented by
Options
Linear list.
Search tree.
Hash Table.
Self-organization list.
Question No. 23 Marks - 10
________________________________________
An ideal compiler should
Options
Detect error.
Detect and repair error.
Detect, repair and correct errors.
None of the above.
Question No. 24 Marks - 10
________________________________________
Hamming distance is
Options
A theoretical way of measuring errors.
A technique for assigning codes to a set of items known to occur with a given probability.
A technique for optimizing the intermediate code
None of the above.
Question No. 25 Marks - 10
________________________________________
A parser with the valid prefix property is advantageous because
Options
It detects error as soon as possible.
It detects errors as and when they occur.
It limits the amount of erroneous output passed to the next phase.
All of the above.
Question No. 26 Marks - 10
________________________________________
The advantage of panic mode of error recovery is that
Options
It is simple to implement.
It is very effective.
It never gets into infinite loop.
None of the above.
Question No. 27 Marks - 10
________________________________________
The technique of replacing run time computation by compile time computation is called
Options
Constant folding.
Code hoisting.
Peephole optimization.
Invariant computation.
Question No. 28 Marks - 10
________________________________________
A basic block can be analyzed by
Options
a DAG
a graph which may involve cycles.
Flow-graph
None of the above.
Question No. 29 Marks - 10
________________________________________
Which of the following concepts can be used to identify loops
Options
Dominators.
Reducible graphs.
Depth first ordering.
None of the above
Question No. 30 Marks - 10
________________________________________
Which of the followings are not loop optimization techniques?
Options
jamming
unrolling
induction variable elimination
None of the above
Question No. 31 Marks - 10
________________________________________
Running time of a program depends on
Options
The way the registers are used.
The order in which computations are performed.
The way the addressing modes are used.
The uses of machine idioms.
Question No. 32 Marks - 10
________________________________________
du-chaining
Options
stands for use definition chaining
is useful for copy propagation removal.
Is useful for induction variable removal.
None of the above.
Question No. 33 Marks - 10
________________________________________
Shift reduce parsers are
Options
top-down parsers
bottom-up parsers
may be top-down or bottom-up.
None of the above.
Question No. 34 Marks - 10
________________________________________
LR stands for
Options
left to right.
Left to right reduction.
Right to left
Left to right and right-most derivation in reverse.
Question No. 35 Marks - 10
________________________________________
Which of the following are the most powerful parsers?
Options
SLR
LALR
Canonical LR
Operator-precedence
Question No. 36 Marks - 10
________________________________________
YACC builds up
Options
SLR parsing table
Canonical LR parsing table.
LALR parsing table.
None of the above.
Question No. 37 Marks - 10
________________________________________
LR (k) grammar
Options
can only examine a maximum of k input symbols.
can b used to identify handles.
can be used identify the production associated with a handle.
Covers the LL (k) class
Question No. 38 Marks - 10
________________________________________
Back –patching is useful for handling
Options
conditional jumps
unconditional jumps
backward references
forward references
Question No. 39 Marks - 10
________________________________________
1. Choose the correct answer
FORTRAN is a
Options
regular language
context-free language
context-sensitive language
Turing language
Question No. 40 Marks - 10
________________________________________
Which of the following features can not be captured by CFG?
Options
Syntax of if-then-else statements.
Syntax of recursive procedures.
Whether a variable is declared before its use.
Matching nested parenthesis.