140
90.5k

90+ Theory of Computation and Compiler Design Solved MCQs

These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) .

Take a Test
51.

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
Answer» C. the lexical analysis of the program
discuss
52.

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
Answer» A. Finite state automata
discuss
53.

Consider the following statements:
(I) The output of a lexical analyzer is groups of characters.
(II) Total number of tokens in printf("i=%d, &i=%x", i, &i); are 11.
(III) Symbol table can be implementation by using array and hash table but not tree.
Which of the following statement(s) is/are correct?
A. Only (I)
B. Only (II) and (III)
C. All (I), (II), and (III)
D. None of these
Answer» D. None of these
discuss
54.

Which one of the following statements is FALSE?

A. Context-free grammar can be used to specify both lexical and syntax rules.
B. Type checking is done before parsing.
C. High-level language programs can be translated to different Intermediate Representations.
D. Arguments to a function can be passed using the program stack.
Answer» B. Type checking is done before parsing.
discuss
55.

A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}. T1: a?(b∣c)*a T2: b?(a∣c)*b T3: c?(b∣a)*c Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix. If the string bbaacabc is processes by the analyzer, which one of the following is the sequence of tokens it outputs?

A. T1T2T3
B. T1T1T3
C. T2T1T3
D. T3T3
Answer» D. T3T3
discuss
56.

Consider the following statements related to compiler construction :
I. Lexical Analysis is specified by context-free grammars and implemented by pushdown automata.
II. Syntax Analysis is specified by regular expressions and implemented by finite-state machine. Which of the above statement(s) is/are correct?
A. Only I
B. Only II
C. Both I and II
D. Neither I nor II
Answer» D. Neither I nor II
discuss
57.

Which of the following statement(s) regarding a linker software is/are true?
I. A function of a linker is to combine several object modules into a single load module.
II. A function of a linker is to replace absolute references in an object module by symbolic references to locations in other modules.
A. Only I
B. Only II
C. Both I and II
D. Neither I nor II
Answer» A. Only I
discuss
58.

From the given data below : a b b a a b b a a b which one of the following is not a word in the dictionary created by LZ-coding (the initial words are a, b)?

A. a b
B. b b
C. b a
D. b a a b
Answer» D. b a a b
discuss
59.

The number of tokens in the following C statement is printf("i=%d, &i=%x", i&i);

A. 13
B. 6
C. 10
D. 9
Answer» D. 9
discuss
60.

In compiler optimization, operator strength reduction uses mathematical identities to replace slow math operations with faster operations. Which of the following code replacements is an illustration of operator strength reduction?

A. Replace P + P by 2 * P or Replace 3 + 4 by 7.
B. Replace P * 32 by P < < 5
C. Replace P * 0 by 0
D. Replace (P < <4) – P by P * 15
Answer» B. Replace P * 32 by P < < 5
discuss
61.

Debugger is a program that

A. allows to examine and modify the contents of registers
B. does not allow execution of a segment of program
C. allows to set breakpoints, execute a segment of program and display contents of register
D. All of the above
Answer» C. allows to set breakpoints, execute a segment of program and display contents of register
discuss
62.

Consider the following two sets of LR(1) items of an LR(1) grammar.
X -> c.X, c/d
X -> .cX, c/d
X -> .d, c/d
X -> c.X, $
X -> .cX, $
X -> .d, $
Which of the following statements related to merging of the two sets in the
corresponding LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.
A. 1 only
B. 2 only
C. 1 and 4 only
D. 1, 2, 3, and 4
Answer» D. 1, 2, 3, and 4
discuss
63.

The grammar S → aSa | bS | c is

A. LL(1) but not LR(1)
B. LR(1)but not LR(1)
C. Both LL(1)and LR(1)
D. Neither LL(1)nor LR(1)
Answer» C. Both LL(1)and LR(1)
discuss
64.

Which of the following statements are TRUE?
I. There exist parsing algorithms for some programming languages whose complexities are less than O(n3).
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 source language and intermediate code level.
A. I and II
B. I and IV
C. III and IV
D. I, III and IV
Answer» B. I and IV
discuss
65.

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

A. It is the position in a sentential form where the next shift or reduce operation will occur
B. It is non-terminal whose production will be used for reduction in the next step
C. It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur
D. It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found
Answer» D. It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found
discuss
66.

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

A. the SLR(1) parser for G has S-R conflicts
B. the LR(1) parser for G has S-R conflicts
C. the LR(0) parser for G has S-R conflicts
D. the LALR(1) parser for G has reduce-reduce conflicts
Answer» B. the LR(1) parser for G has S-R conflicts
discuss
67.

Consider the following two statements:
P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar
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. P is false and Q is true
discuss
68.

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. (i) and (ii)
B. (ii) and (iii)
C. (i) and (iii)
D. None of the above
Answer» D. None of the above
discuss
69.

A canonical set of items is given below
S --> L. > R
Q --> R.
On input symbol < the set has
A. a shift-reduce conflict and a reduce-reduce conflict.
B. a shift-reduce conflict but not a reduce-reduce conflict.
C. a reduce-reduce conflict but not a shift-reduce conflict.
D. neither a shift-reduce nor a reduce-reduce conflict.
Answer» D. neither a shift-reduce nor a reduce-reduce conflict.
discuss
70.

Consider the grammar defined by the following production rules, with two
operators ∗ and +
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. + is right associative, while ∗ is left associative
discuss
71.

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. {S → FR} and {R → ε }
discuss
72.

Consider the following translation scheme. S → ER R → *E{print("*");}R | ε E→ F + E {print("+");} | F F → (S) | id {print(id.value);} Here id is a token 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» D. 2 3 4+*
discuss
73.

The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is

A. ambiguous
B. left-recursive
C. right-recursive
D. an operator-grammar
Answer» A. ambiguous
discuss
74.

Consider the grammar S → (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 ≥ n3 ≥ n2
Answer» B. n1 = n3 < n2
discuss
75.

Consider the following expression grammar. The seman-tic rules for expression
calculation are stated next to each grammar production.
E → number E.val = number. val
| E '+' E E(1).val = E(2).val + E(3).val
| E '×' E E(1).val = E(2).val × E(3).val
The above 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?
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. It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action
discuss
76.

Which of the following grammar rules violate the requirements of an operator grammar ? P, Q, R are nonterminals, and r, s, t are terminals.
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. 1 and 3 only
discuss
77.

Consider the grammar with the following translation rules and E as the start symbol.
E → E1 # T { E.value = E1.value * T.value } | T{ E.value = T.value }
T → T1 & F { T.value = T1.value + F.value } | F{ T.value = F.value }
F → num { F.value = num.value }
Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.
A. 200
B. 180
C. 160
D. 40
Answer» C. 160
discuss
78.

Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is:

A. n1 is necessarily less than n2
B. n1 is necessarily equal to n2
C. n1 is necessarily greater than n2
D. none of these
Answer» B. n1 is necessarily equal to n2
discuss
79.

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' → e}
B. {S' → e S} and {}
C. {S' → ε} and {S' → ε}
D. {S' → e S, S'→ ε} and {S' → ε}
Answer» D. {S' → e S, S'→ ε} and {S' → ε}
discuss
80.

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
Answer» B. 9 5 + 2 +
discuss
81.

Which of the following is essential for converting an infix expression to the postfix from efficiently?

A. An operator stack
B. An operand stack
C. An operand stack and an operator stack
D. A parse tree
Answer» A. An operator stack
discuss
82.

The grammar whose productions are
<stmt> → if id then <stmt>
<stmt> → if id then <stmt> else <stmt>
<stmt> → id := id
is ambiguous because
a) the sentence if a then if b then c:= d has two parse trees
b) the left most and right most derivations of the sentence if a then if b then c:= d give rise to different parse trees
c) the sentence if a then if b then c:= d else c:= f has more than two parse trees
d) the sentence if a then if b then c:= d else c:= f has two parse trees
A. a
B. b
C. c
D. d
Answer» D. d
discuss
83.

Consider the following grammars
(S1) :
A --> aBCD
B --> bc|c
C --> d|∈
D -> b
(S2) :
A --> aBCD
B --> bc|∈
C --> d|c
D -> b
(S3) :
A --> aBCD
B --> bc|∈
C --> d|∈
D -> b
(S4) :
A --> aBCD
B --> bc|c
C --> d|c
D -> b
Which of the following grammar has same follow set for variable B?
A. Only (S1), (S2) and (S3), (S4)
B. Only (S1), (S3) and (S2), (S4)
C. Only (S2), (S3) and (S1), (S4)
D. None of the above
Answer» B. Only (S1), (S3) and (S2), (S4)
discuss
84.

Which is True about SR and RR-conflict:

A. If there is no SR-conflict in CLR(1) then definitely there will be no SR-conflict in LALR(1).
B. RR-conflict might occur if lookahead for final items(reduce-moves) is same.
C. Known that CLR(1) has no RR-conflict, still RR-conflict might occur in LALR(1).
D. All of the above.
Answer» D. All of the above.
discuss
85.

Which of the following statement(s) regarding a linker software is/are true ? I A function of a linker is to combine several object modules into a single load module. II A function of a linker is to replace absolute references in an object module by symbolic references to locations in other modules.

A. Only I
B. Only II
C. Both I and II
D. Neither I nor II
Answer» A. Only I
discuss
86.

Shift-Reduce parsers perform the following:

A. Shift step that advances in the input stream by K(K > 1) symbols and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
B. Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
C. Shift step that advances in the input stream by K(K = 2) symbols and Reduce step that applies a completed grammar rule to form a single tree
D. Shift step that does not advance in the input stream and Reduce step that applies a completed grammar rule to form a single tree.
Answer» B. Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
discuss
87.

Incremental-Compiler is a compiler

A. which is written in a language that is different from the source language
B. compiles the whole source code to generate object code afresh
C. compiles only those portion of source code that have been modified.
D. that runs on one machine but produces object code for another machine
Answer» C. compiles only those portion of source code that have been modified.
discuss
88.

Which one of the following is FALSE?

A. A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.
B. Available expression analysis can be used for common subexpression elimination.
C. Live variable analysis can be used for dead code elimination.
D. x = 4 ∗ 5 => x = 20 is an example of common subexpression elimination.
Answer» D. x = 4 ∗ 5 => x = 20 is an example of common subexpression elimination.
discuss
89.

Consider the following C code segment.
for (i = 0, i<n; i++)
{
for (j=0; j<n; j++)
{
if (i%2)
{
x += (4*j + 5*i);
y += (7 + 4*j);
}
}
}
Which one of the following is false?
A. The code contains loop invariant computation
B. There is scope of common sub-expression elimination in this code
C. There is scope of strength reduction in this code
D. There is scope of dead code elimination in this code
Answer» D. There is scope of dead code elimination in this code
discuss
90.

Consider the intermediate code given below:
1. i = 1
2. j = 1
3. t1 = 5 * i
4. t2 = t1 + j
5. t3 = 4 * t2
6. t4 = t3
7. a[t4] = –1
8. j = j + 1
9. if j <= 5 goto(3)
10. i = i + 1
11. if i < 5 goto(2)
The number of nodes and edges in the control-flow-graph constructed for the above
code, respectively, are
A. 5 and 7
B. 6 and 7
C. 5 and 5
D. 7 and 8
Answer» B. 6 and 7
discuss
91.

Consider the following code segment.
x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;
The minimum number of total variables required to convert the above code segment to
static single assignment form is Note : This question was asked as Numerical Answer
Type.
A. 6
B. 8
C. 9
D. 10
Answer» D. 10
discuss
92.

A linker reads four modules whose lengths are 200, 800, 600 and 500 words respectively. If they are loaded in that order, what are the relocation constants?

A. 0, 200, 500, 600
B. 0, 200, 1000, 1600
C. 200, 500, 600, 800
D. 200, 700, 1300, 2100
Answer» B. 0, 200, 1000, 1600
discuss
93.

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
Answer» C. A compiler using dynamic memory allocation can be written for L
discuss
94.

The expression (a*b)* c op........ where 'op' is one of '+', '*' and '↑' (exponentiation) can be evaluated on a CPU with a single register without storing the value of (a * b) if

A. ‘op’ is ‘+’ or ‘*’
B. 'op’ is ‘↑’ or ‘*’
C. 'op’ is ‘↑’ or ‘+’
D. not possible to evaluate without storing
Answer» A. ‘op’ is ‘+’ or ‘*’
discuss
95.

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
Answer» A. (ii) only
discuss
96.

Consider the following expression
u*v+a-b*c
Which one of the following corresponds to a static single assignment from the above expressions
A. x1 = a - b y1 = p * c x2 = u * v y2 = p + q
B. x 1 = a - b y1 = x2 * c x3 = u * v y2 = x4 + y3
C. x1 = a - b y2 = x1 * c x2 = u * v y3 = x2 + y2
D. p = a - b q = p * c p = u * v q = p + q
Answer» C. x1 = a - b y2 = x1 * c x2 = u * v y3 = x2 + y2
discuss
97.

In multi-programmed systems, it is advantageous if some programs such as editors and compilers can be shared by several users. Which of the following must be true of multi-programmed systems in order that a single copy of a program can be shared by several users?
I. The program is a macro
II. The program is recursive
III.The program is reentrant
A. I only
B. II only
C. Ill only
D. I, II and III
Answer» C. Ill only
discuss

Done Studing? Take A Test.

Great job completing your study session! Now it's time to put your knowledge to the test. Challenge yourself, see how much you've learned, and identify areas for improvement. Don’t worry, this is all part of the journey to mastery. Ready for the next step? Take a quiz to solidify what you've just studied.

Take a Test