Compilers Questions and Answers for Entrance exams on “Intermediate Code – Generation”.
1. Consider the following two statements:
P: Every regular grammar is LL(1)
Q: Every regular set has 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: a
Clarification: LL(1) parsers can recognize the regular grammars also LL(1) is subset of LR(1) or CLR grammar so it also recognizes regular sets. So both accept regular grammar.
2. In a simplified computer the instructions are:
OP R j, Ri − Performs Rj OP Ri and stores the result in register Ri OP m, Ri − Performs val OP Ri abd stores the result in Ri. value denotes the content of memory location m. MCVm, Ri −Moves the content off memory loction m to register Ri. MCVm, Ri, m −Moves the content of register Ri to memory location m.
The computer has only two registers, and OP is either ADD or SUB. Consider the following basic block:
t1 = a + b t2 = c + d t3 = e − t2 t4 = t 1 − t2
Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?
a) 2
b) 3
c) 5
d) 6
Answer: b
Clarification: The operation sequence would be
MOV a, R1
ADD b , R1 {R 1 = t1
MOV c , R2
ADD d, R2 {R 2 = t2
SUB e , R2 {t 3 = e − R 2 = R2
SUB R 1, R2 {R 2 = t4
MOV R 2, t4 {finally in memory
Totally no. of move operation is 3.
3. Which of the following strings is generated by the grammar?
S->bA S->aB A->a B->b A->aS B->bS A->bAA B->aBB
a) aaaabb
b) aabbbb
c) aabbab
d) abbbba
Answer: c
Clarification: aabbab S ” aB ” aaBB ” aabSB ” aabbAB ” aabbab
4. How many derivation trees are there?
S->bA S->aB A->a B->b A->aS B->bS A->bAA B->aBB
a) 1
b) 2
c) 3
d) 4
Answer: b
Clarification: For the derivation two trees are possible So due to ambiguity 2 trees are possible.
5. 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 a 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
Clarification: Handles are the part of sentential form, & they are identified as the right side of any given production which will be used for reduction in the next step.
6. Some code optimizations are carried out on the intermediate code because _______________
a) They enhance the portability of the complier to other target processors
b) Program analysis is name accurate on intermediate code than on machine code
c) The information from data flow analysis cannot otherwise be used for optimization
d) The information from the front end cannot otherwise be used for optimization
Answer: b
Clarification: Code optimizations are carried out on the intermediate code because program analysis is more accurate on intermediate code than on machine code.
7. Which of the following are true?
(i) A programming language option does not permit global variables of any king and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation
(ii) Multi-level access link (or display) arrangement is needed to arrange activation records-only if the programming language being implemented has nesting of procedures/function
(iii) Recursion in programming languages cannot be implemented with dynamic storage allocation
(iv) Nesting of procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records
(v) Languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records.
a) (ii) and (v) only
b) (i), (iii) and (iv) only
c) (i), (ii) and (v)
d) (ii), (iii) and (v) only
Answer: a
Clarification: I. Statement is false since global variables are required for recursions with static storage. This is due to unavailability of stack in static storage. II. This is true III. In dynamic allocation heap structure is used, so it is false. IV. False since recursion can be implemented. V. Statement is completely true. So only II & V are true.
8. An LALR(1) parser for a grammar 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
Clarification: LALR parser is reduced form of CLR or LR(1) parser, LALR parser uses the LR(1) items of CLR parser & of any shift reduce conflicts are there then it is due to LR(1) parser.
9. Which of the following statements are TRUE?
I There exist parsing algorithms for some programming languages hose complex are less than θ(n 3)
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
Clarification: I. Statement is true since there are some parsers which take 0 (n log2n) times for parsing. II. Completely false, since there is no use of stack which is required for recursion. III. False IV. True since both types of optimizations are applied.
10. What data structure in a complier is used for managing information about variables and their attributes?
a) Abstract syntax tree
b) Symbol table
c) Semantic stack
d) Parse table
Answer: b
Clarification: Symbol table is used for storing the information about variables and their attributes by compiler.