Theory Of Computation And Compiler Design Set 4

On This Page

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