Theory Of Computation And Compiler Design Set 4 MCQs

Q1 | 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 R2. P ? Q s R3. P ? ?4. P ? Q t R r

1 only

1 and 3 only

2 and 3 only

3 and 4 only

Q2 | 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.

200

180

160

40

Q3 | 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:

n1 is necessarily less than n2

n1 is necessarily equal to n2

n1 is necessarily greater than n2

none of these

Q4 | 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

{S' ? e S} and {S' ? e}

{S' ? e S} and {}

{S' ? ?} and {S' ? ?}

{S' ? e S, S'? ?} and {S' ? ?}

Q5 | Consider the translation scheme shown belowS ? T RR ? + T {print ('+');} R | ?T ? num {print (num.val);}Here num is a token that represents an integer and num.val represents thecorresponding integer value. For an input string '9 + 5 + 2', this translation scheme willprint

9 + 5 + 2

9 5 + 2 +

9 5 2 + +

+ + 9 5 2

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

An operator stack

An operand stack

An operand stack and an operator stack

A parse tree

Q7 | The grammar whose productions are ? if id then ? if id then else ? id := idis ambiguous becausea) the sentence if a then if b then c:= d has two parse treesb) the left most and right most derivations of the sentence if a then if b then c:= d give rise to different parse treesc) the sentence if a then if b then c:= d else c:= f has more than two parse treesd) the sentence if a then if b then c:= d else c:= f has two parse trees

a

b

c

d

Q8 | Consider the following grammars(S1) :A --> aBCDB --> bc|cC --> d|?D -> b(S2) :A --> aBCDB --> bc|?C --> d|cD -> b(S3) :A --> aBCDB --> bc|?C --> d|?D -> b(S4) :A --> aBCDB --> bc|cC --> d|cD -> bWhich of the following grammar has same follow set for variable B?

Only (S1), (S2) and (S3), (S4)

Only (S1), (S3) and (S2), (S4)

Only (S2), (S3) and (S1), (S4)

None of the above

Q9 | Which is True about SR and RR-conflict:

If there is no SR-conflict in CLR(1) then definitely there will be no SR-conflict in LALR(1).

RR-conflict might occur if lookahead for final items(reduce-moves) is same.

Known that CLR(1) has no RR-conflict, still RR-conflict might occur in LALR(1).

All of the above.

Q10 | 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.

Only I

Only II

Both I and II

Neither I nor II

Q11 | Shift-Reduce parsers perform the following:

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.

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.

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

Shift step that does not advance in the input stream and Reduce step that applies a completed grammar rule to form a single tree.

Q12 | Incremental-Compiler is a compiler

which is written in a language that is different from the source language

compiles the whole source code to generate object code afresh

compiles only those portion of source code that have been modified.

that runs on one machine but produces object code for another machine

Q13 | Which one of the following is FALSE?

A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.

Available expression analysis can be used for common subexpression elimination.

Live variable analysis can be used for dead code elimination.

x = 4 ? 5 => x = 20 is an example of common subexpression elimination.

Q14 | Consider the following C code segment.for (i = 0, i

The code contains loop invariant computation

There is scope of common sub-expression elimination in this code

There is scope of strength reduction in this code

There is scope of dead code elimination in this code

Q15 | Consider the intermediate code given below:1. i = 12. j = 13. t1 = 5 * i4. t2 = t1 + j5. t3 = 4 * t26. t4 = t37. a[t4] = –18. j = j + 19. if j <= 5 goto(3)10. i = i + 111. if i < 5 goto(2)The number of nodes and edges in the control-flow-graph constructed for the abovecode, respectively, are

5 and 7

6 and 7

5 and 5

7 and 8

Q16 | 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 tostatic single assignment form is Note : This question was asked as Numerical AnswerType.

6

8

9

10

Q17 | 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?

0, 200, 500, 600

0, 200, 1000, 1600

200, 500, 600, 800

200, 700, 1300, 2100

Q18 | 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 compiler using static memory allocation can be written for L

A compiler cannot be written for L, an interpreter must be used

A compiler using dynamic memory allocation can be written for L

None of the above

Q19 | 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

‘op’ is ‘+’ or ‘*’

'op’ is ‘?’ or ‘*’

'op’ is ‘?’ or ‘+’

not possible to evaluate without storing

Q20 | Which of the following macros can put a micro assembler into an infinite loop?(i).MACRO M1 X.IF EQ, X ;if X=0 thenM1 X + 1.ENDC.IF NE X ;IF X?0 then.WORD X ;address (X) is storedhere.ENDC.ENDM(ii).MACRO M2 X.IF EQ XM2 X.ENDC.IF NE, X.WORD X+1.ENDC.ENDM

(ii) only

(i) only

Both (i) and (ii)

None of the above

Q21 | Consider the following expressionu*v+a-b*cWhich one of the following corresponds to a static single assignment from the above expressions

x1 = a - b y1 = p * c x2 = u * v y2 = p + q

x 1 = a - b y1 = x2 * c x3 = u * v y2 = x4 + y3

x1 = a - b y2 = x1 * c x2 = u * v y3 = x2 + y2

p = a - b q = p * c p = u * v q = p + q

Q22 | 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 macroII. The program is recursiveIII.The program is reentrant

I only

II only

Ill only

I, II and III