**CS606 – Compiler Construction**

In CS606 Compiler Construction we have you covered with Digitized Past Papers From Fall of Mid Term and Final Term.

**NOTE: Tab/Click on Preparation Tab to take the MCQ’s Tests.**

**POSTED DATE:31-01-2019 IDEA SOLUTION**

**We first find the equations for Nullable: **

**Nullable(A) = Nullable(BAa) V Nullable(ɛ) **

**Nullable(B) = Nullable(bBc)**** ****V Nultable(AA) **

**This trivially solves to **

**Nullabk(A) = true **

**Nullable(****B****) ****=**** true **

**Next. we set up the equations for FIRST: **

**FIRST(A) = FIRST(****BAa) ****FIRST****(****ɛ****)**

**FIRST(****B****) = FIRST(****bBc) ****FIRST****(AA)**** **

**Given that both A and B are Nul****lable****,**** ****we can reduce this to **

**FIRST(A) = FIRST(****B) ****FIRST****(A) ****{a}**

**FIRST(****B****) = ****{b}**** ****FIRST(A)**

**which solve to **

**FIRST(A) = ****{****a, b} **

**FIRST(****B****) = ****{****a, b} **

** **

**Finally, we add the production A’ —**** $**** and set up the constraints for FOLLOW: **

** **

**{ $ ****}**** ****FOLLOW(A)**

**F****IRST****(A****a****)**** ****FOLLOW(****B****)**

**{ a ****}**** ****FOLLOW(A)**

**{ c ****}**** ****FOLLOW(****B****)**

**F****IRST****(A)**** ****FOLLOW(****A****)**

**F****OLLOW****(****B****)**** ****FOLLOW(****A****)**

** **

**Which we solve to**

**F****OLLOW****(A)**** ****{****a, b****,c,$****}**

**F****OLLOW****(****B****)**** ****{****a, b****,c****}**

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?

Answer: Page no: 135

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

3)

What is Relocation?

Answer:

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

Page 2 of 20

The third section represents C/C++ functions.

5)

Differentiate attribute grammar and syntax-directed grammar.

Answer: 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.

Page 3 of 20

• 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

What is reducible flow graph?

Answer:

Reducible flow graph

Intuition: Produced by exclusive use of flow of control statements such as if-then-else, while-do,

continue, break etc.

Statistics: Even programs written using goto statements are almost always reducible.

Main property: there are no jumps in the middle of loops from outside; the only entry to a loop is

through its header.

Definition: A flow graph G is reducible if and only if we can partition the edges into two disjoint groups,

often called the forward edges and back edges with properties:- forward edges from an acyclic graph in

which every node can be reached from the initial node of G.- the back edges consist only of edges whose

heads dominate their tails.

20)

: Consider grammar SàaS show that grammar is ambiguous by using two parse tree for the same string.

Answer:

The string given is not correct(incomplete) actually so unable to make parse tree. So to understand the

concept of ambgious grammer we can look at following example:

Finite automata, which are equivalent to regular expressions. Regular expressions are widely used in programming for matching strings and extracting text. They are a simple method of describing a set of valid strings using basic characters, grouping, and repitition. They can do a lot, but they can’t match balanced sets of parentheses. · Push-down automata, equivalent to context-free grammars. Text/input parsers and compilers use these when regular expressions aren’t powerful enough (and one of the things you learn in studying finite automata is what regular expressions can’t do, which is crucial to knowing when to write a regular expression and when to use something more complicated). Context-free grammars can describe “languages” (sets of valid strings) where the validity at a certain point in parsing the string does not depend on what else has been seen. · Turing machines, equivalent to general computation (anything you can do with a computer)

cs606 GDB