Computer Science and Information Technology - Compiler Design
Exam Duration: 45 Mins Total Questions : 30
Elimination of left recursion can be done systematically, if the grammar has
- (a)
cycles or \(\varepsilon \) - productions
- (b)
no cycles but \(\varepsilon \) - productions
- (c)
no cycle or no \(\varepsilon \) - productions
- (d)
cycles and no \(\varepsilon \) - productions
Which of the following derivations do a top-down parser use while parsing an input string ? The input is assumed to be scanned in left to right order.
- (a)
Left most derivation
- (b)
Left most derivation traced out in reverse
- (c)
Right most derivation
- (d)
Right most derivation traced out in reverse
Which of the following is correct about syntax directed translation ?
(i) Evaluation of the semantic rules may generates codes save information in a symbol table, issue error messages or perform any other activities.
(ii) The translations of the token stream in the result obtained by evaluating the semantic rules.
- (a)
(i) only
- (b)
(ii) only
- (c)
(i) and (ii)
- (d)
Neither (i) nor (ii)
Which is a permanent database in the general model of compiler ?
- (a)
Literal table
- (b)
Identifier table
- (c)
Terminal table
- (d)
Reductions
The best way to compare the different implementation of symbol table is to compare the time required to
- (a)
add a new name
- (b)
make an inquiry
- (c)
add a new name and make an inquiry
- (d)
All of the above
In which type of loader, the assembler run in one part of memory and place the assembled machine unstructions and data as they are assembled directly into assigned memory location ?
- (a)
Compile and go loader
- (b)
general loader
- (c)
Absolute loader
- (d)
None of these
Heap allocation is required for the languages
- (a)
that support recursion
- (b)
that support dynamic data structure
- (c)
that are dynamic scope rules.
- (d)
None of the above
Left factoring is the process of factoring out of the common.
- (a)
prefixed of alter nates
- (b)
sufixes of alternates
- (c)
predictive parsing
- (d)
None of these
Generation of intermediate code based on a abstract machine model is useful in compiler 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 languages programs
A loader is
- (a)
a program that places programs into memory and orepares them for execution
- (b)
a program that automates the translation of assembly language into machine language
- (c)
a program that accepts a program written in a high level language and produces an object program
- (d)
a program that appears to execute a source program as if it was machine language.
A programming language is to be designed to run on a machine that does not have a big memory. The language should
- (a)
prefer a two-pass compiler to one-pass compiler
- (b)
prefer an interpreter to a compiler
- (c)
not support recursion
- (d)
All of the above
Which table is a permanent data based that has an entry for each terminal symbol ?
- (a)
Terminal table
- (b)
Literal table
- (c)
Identifier table
- (d)
Reductions
Pick the machine independent phase(s) of the compiler.
- (a)
Syntax analysis
- (b)
Lexical analysis
- (c)
Intermediate code generation
- (d)
All of the above
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
A grammar will be meaningless
- (a)
if terminal set and non-terminal set are not disjoint
- (b)
if the left handside of a production has a single terminal
- (c)
if the left handside of a production has no non-terminal
- (d)
All of the above
Which of following is used for grouping of characters into tokens (in a compiler ) ?
- (a)
Parser
- (b)
Code optimizer
- (c)
Code generator
- (d)
Scanner
Context Free Grammer (CFG) can be recognized by
- (a)
finite state automata
- (b)
two-way linear bounded automata
- (c)
push down automata
- (d)
All of the above
Hamming distance is
- (a)
a theoretical way of measuring errors
- (b)
a technique for assigning codes to a set of items known to occur with a given probability
- (c)
a technique for optimizing the intermediate code
- (d)
None of the above
Consider the left recursive grammar
S \(\rightarrow \) Aa \(|\) b
A \(\rightarrow \) Ac \(|\) bd
When the left recursion is removed, the grammar will become equivalent to the grammar
- (a)
S \(\rightarrow \) bA'
A \(\rightarrow \) c \(|\) da - (b)
S \(\rightarrow \) Aa \(|\) b
A \(\rightarrow \) ad \(|\) bd \(|\) cA - (c)
S \(\rightarrow \) Aa \(|\) b
A \(\rightarrow \) Ac \(|\) Aad \(|\) bd - (d)
S \(\rightarrow \) Aa \(|\) b
A \(\rightarrow \) bdA'
A \(\rightarrow \) cA' \(|\) \(\epsilon \)
Recursive descent parsing belongs to the class of
- (a)
predictive parsing
- (b)
top-down parsing
- (c)
bottom-up parsing
- (d)
None of these
Which of the following symbols table implementation is based on the property of locality of reference ?
- (a)
Hash table
- (b)
Search tree
- (c)
Self-organizing list
- (d)
Linear list
The parsing technique that avoids back tracking is
- (a)
top-down parsing
- (b)
recursive descent parsing
- (c)
predictive parsing
- (d)
Both (b) and (c)
Consider the grammar :
S \(\rightarrow \) (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 \(\ge \) n3 \(\ge \) n2
The grammar E \(\rightarrow \) E + E
E \(\rightarrow \) E*E \(|\) a, is
- (a)
ambiguous
- (b)
unambiguous
- (c)
depends on the given sentence
- (d)
None of the above
The number of tokens in the following C statement :
printf ("i = %d, & i = %x", i, & i) ;
- (a)
3
- (b)
26
- (c)
10
- (d)
21
Which one of the following is valid ssumption prior to code ganeration ?
(i) Prior to code genaration, the front end has scanned, parsed and translated the source program into a reasonably detaied intermediate representation.
(ii) The necessary type checking has taken place
(iii) The input is free from errors.
- (a)
(i), (ii) and (iii)
- (b)
(ii) and (iii)
- (c)
(i) and (iii)
- (d)
(i) and (ii)
The process of computing the attribute values at the nodes in parse tree is called ............parse tree.
- (a)
annotating
- (b)
decorating
- (c)
Both (a) and (b)
- (d)
Neither (a) nor (b0
Consider the following grammar for arithmetic expression involving +, -, *, / and \(\uparrow \)
E \(\rightarrow \) E + E \(|\) E - E \(|\) E * E \(|\) E / E \(|\) E \(\uparrow \) E \(|\) (E) \(|\) - E \(|\) id
Then which of the following is correct ?
- (a)
The grammar is ambiguous and we cannot disambiguate it
- (b)
Syntactic variable and syntactic category are two different terminologies related to non- terminals
- (c)
The productions define the ways in which the syntactic categories may be built-up from one another and from the terminals
- (d)
The grammar is ambiguous and we can disambiguous it by specifying the associativity and precedence of arithmetic operators
Consider the following grammar for arithmetic expressions :
E \(\rightarrow \) E + E \(|\) E * E \(|\) (E) \(|\) - E \(|\) id
Then -(id + id) is ....
- (a)
invalid sentence of a grammar
- (b)
valid sentential form of a grammar
- (c)
valid sentence of grammar
- (d)
invalid sentential form of a grammar
Consider the following expression grammar. the semantic rules for expression evaluation are stated next to each grammar production.
E \(\rightarrow \) number E. val = number .val
\(|\) E '+' E E(1). val = E(2). val + E(3). val
\(|\) E 'x' E E(1). val = E(2). val x E(3). val
Assume the conflicts in Q.5 are resolved and an LALR (1) parser is generated for parsing arithmetic expression as per the given grammar. Consider an expression 3 x 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 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 x and both operators are left associative; expression is evaluated to 9.