CS606 Final Term Subjective 2013

Final Term Papers 2013

1)

What is live variable?

Answer: Page no: 128

A variable is live at a given point in time if it has a next use. Liveness tells us whether we

care about the value held by a variable. Here is the algorithm for computing live status of

variables in a basic block”.

2)

What are the common sub-expressions?

Page no: 135

A node in the DAG with more than one parent is common sub-expression

3)

What is Relocation?

Compilers and assemblers generate the object code for each input module with a starting address of zero. Relocation is the process of assigning load addresses to different parts of the program by merging all sections of the same type into one section. The code and data section also are adjusted so they point to the correct runtime addresses.

4)

Third section of YACC represents what kind of information? 3 Marks

Answer: Page no : 88

Solved by: · Sahar (well wisher) · Class · BSCS 6th Semester · Subject

CS606 (COMPILER CONSTRUCTION)

Solution

Type:

Final Term Solved Subjective including Papers of Year : 2013,2012,2011,2010,2009…2006

Institute:

Virtual University of Pakistan

The third section represents C/C++ functions.

5)

Differentiate attribute grammar and syntax-directed grammar.

Page no: 100

Attribute grammar:

A CFG is augmented with a set of rules. Each symbol in the derivation has a set of values or attributes. Rules specify how to compute a value for each attribute

Syntax-directed grammar:

A syntax directed definition is a generalization of a context free grammar in which each grammar symbol has an associated set of attributes, partitioned into two subsets called the synthesized and inherited attributes of that grammar symbol.

6)

Brief note on Reducible Flow Graphs?

7)

What kind of data structure is used to represent Basic Blocks?

Answer: A basic block is a sequence of consecutive statements with single entry/single exit. Flow of control only enters at the beginning and only leaves at the end. The can be variants of basic blocks with single entry/multiple exit, multiple entry/single exit.

8)

Discuss the issue of Target programs in Code Generation phase?

Answer: Memory management: mapping names to data objects in the run-time system.

• Instruction selection: the assembly language instructions to choose to encode intermediate code statements
• Instruction scheduling: instruction chosen must utilize the CPU resources effectively. Hardware stalls must be avoided.
• Register allocation: operands are placed in registers before executing machine operation such as ADD, MULTIPLY etc. Most processors have a limited set of registers available. The code generator has to make efficient use of this limited resource

Page no : 121

9)

How register descriptor are used in code generation? 5 Marks

Answer: The code generator uses two data structures for keeping track of register usage one is Register descriptor has register status (empty, in use) and contents (one or more "values")

Page no : 129

10)

Diff. Between Hop croft’s Algorithm and Subset Construction Algorithm?

Hop croft’s Algorithm:

The Hop croft’s algorithm can be used to minimize DFA states. The behind the algorithm is to find groups of equivalent states. All transitions from states in one group G1 go to states in the same group G2. We construct the minimized DFA such that there is one state for each group of states from the initial DFA.

Subset Construction Algorithm:

The algorithm is called subset construction. In the transition table of an NFA, each entry is a set of states. In DFA, each entry is a single state. The general idea behind NFA-to-DFA construction is that each DFA state corresponds to a set of NFA states. The DFA uses its state to keep track of all possible states the NFA can be in after reading each input symbol.