### Theory Of Computation And Compiler Design Set 4

This set of Theory of Computation and Compiler Design Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation And Compiler Design Set 4

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