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