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 Nullable, 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)
FIRST(Aa) FOLLOW(B)
{ a } FOLLOW(A)
{ c } FOLLOW(B)
FIRST(A) FOLLOW(A)
FOLLOW(B) FOLLOW(A)
Which we solve to
FOLLOW(A) {a, b,c,$}
FOLLOW(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