COMPILER DESIGN VIVA Questions and Answers :-
COMPILER DESIGN VIVA Questions and Answers :-
23. Write the transition graph for an NFA that recognizes the language (a|b)*abb ?
31. Mention the issues to be considered while applying the techniques for code optimization.
- The semantic equivalence of the source program must not be changed.
- The improvement over the program efficiency must be achieved without changing the algorithm of the program.
- The machine dependent optimization is based on the characteristics of the target machine for the instruction set used and addressing modes used for the instructions to produce the efficient target code.
- The machine independent optimization is based on the characteristics of the programming languages for appropriate programming structure and usage of efficient arithmetic properties in order to reduce the execution time.
- Available expressions
- Reaching definitions
- Live variables
- Busy variables
32. What are the basic goals of code movement?
- To reduce the size of the code i.e. to obtain the space complexity.
- To reduce the frequency of execution of code i.e. to obtain the time complexity.
33. What do you mean by machine dependent and machine independent optimization?
34. What are the different data flow properties?
35. List the different storage allocation strategies.
The strategies are:
- Static allocation
- Stack allocation
- Heap allocation
36. What are the contents of activation record?
The activation record is a block of memory used for managing the information needed by a single execution of a procedure. Various fields f activation record are:
- Temporary variables
- Local variables
- Saved machine registers
- Control link
- Access link
- Actual parameters
- Return values
37. What is dynamic scoping?
In dynamic scoping a use of non-local variable refers to the non-local data declared in most recently called and still active procedure. Therefore each time new findings are set up for local names called procedure. In dynamic scoping symbol tables can be required at run time.
38. Define symbol table.
Symbol table is a data structure used by the compiler to keep track of semantics of the variables. It stores information about scope and binding information about names.
39. What is code motion?
Code motion is an optimization technique in which amount of code in a loop is decreased. This transformation is applicable to the expression that yields the same result independent of the number of times the loop is executed. Such an expression is placed before the loop.
40. What are the properties of optimizing compiler?
The source code should be such that it should produce minimum amount of target code.
There should not be any unreachable code.
Dead code should be completely removed from source language.
The optimizing compilers should apply following code improving transformations on source language.
i) common subexpression elimination
ii) dead code elimination
iii) code movement
iv) strength reduction
41. What are the various ways to pass a parameter in a function?
- Call by value
- Call by reference
- Call by name
42. Suggest a suitable approach for computing hash function.
- Using hash function we should obtain exact locations of name in symbol table.
- The hash function should result in uniform distribution of names in symbol table.
- The hash function should be such that there will be minimum number of collisions. Collision is such a situation where hash function results in same location for storing the names.
43. Mention the properties that a code generator should possess.
- The code generator should produce the correct and high quality code. In other words, the code generated should be such that it should make effective use of the resources of the target machine.
- Code generator should run efficiently.
- Define and use – the three address statement a:=b+c is said to define a and to use b and c.
- Live and dead – the name in the basic block is said to be live at a given point if its value is used after that point in the program. And the name in the basic block is said to be dead at a given point if its value is never used after that point in the program.
44. List the terminologies used in basic blocks.
45. What is a flow graph?
A flow graph is a directed graph in which the flow control information is added to the basic blocks.
- The nodes to the flow graph are represented by basic blocks
- The block whose leader is the first statement is called initial block.
- There is a directed edge from block B1 to block B2 if B2 immediately follows B1 in the given sequence. We can say that B1 is a predecessor of B2.
46. What is a DAG? Mention its applications.
Directed acyclic graph(DAG) is a useful data structure for implementing transformations on basic blocks.
DAG is used in
- Determining the common sub-expressions.
- Determining which names are used inside the block and computed outside the block.
- Determining which statements of the block could have their computed value outside the block.
- Simplifying the list of quadruples by eliminating the common su-expressions and not performing the assignment of the form x := y unless and until it is a must.
47. Define peephole optimization.
Peephole optimization is a simple and effective technique for locally improving target code. This technique is applied to improve the performance of the target program by examining the short sequence of target instructions and replacing these instructions by shorter or faster sequence.
48. List the characteristics of peephole optimization.
- Redundant instruction elimination
- Flow of control optimization
- Algebraic simplification
- Use of machine idioms
49. How do you calculate the cost of an instruction?
The cost of an instruction can be computed as one plus cost associated with the source and destination addressing modes given by added cost.
MOV R0,R1 1
MOV R1,M 2
SUB 5(R0),*10(R1) 3
50. What is a basic block?
A basic block is a sequence of consecutive statements in which flow of control enters at the beginning and leaves at the end without halt or possibility of branching.