cs606compilerconstruction midterm paper for virtual university students

[Xpert]

cs606 compiler construction midterm paper for virtual university students. These papers are in the form of .Doc format not in the PDF format.

CS410 Visual Programming
Final Term Examination – Spring 2005
Time Allowed: 150 Minutes
Please read the following instructions carefully before
attempting any of the questions:
1. The duration of this examination is 150 Mins.
2. This examination is closed book, closed notes, closed neighbors.
3. Do not ask any questions about the contents of this examination from
anyone.
a. If you think that there is something wrong with any of the
questions, attempt it to the best of your understanding.
b. If you believe that some essential piece of information is
missing, make an appropriate assumption and use it to solve
the problem.
4. Some of the examination consists of multiple-choice questions.
Choose only one choice as your answer.
a. If you believe that two (or more) of the choices are correct for a
particular question, choose the best one.
b. On the other hand, if you believe that all of the choices provided
for a particular question are wrong then select the one that
appears to you as being the least wrong.
**WARNING: Please note that Virtual University takes serious
action against unfair means. Anyone found involved in
cheating will get an `F` grade in this course.
Total Marks: 160 Total Questions: 21
Question No. 1 Marks : 05
When generating a lexical analyzer from a token description, the item sets (states) are
constructed by two types of "moves": character moves and ε-moves. ε-moves do not
consume any input character, but merely expand non-basic items with repetition and
composition operators.
o True
o False
Question No. 2 Marks : 30
Consider the following augmented grammar
(a) Derive the canonical sets of LR( 1) items
(b) Build the LR(1) parse table (Action/Goto)
Question No. 3 Marks : 05
The following two items
{A→ P • P,B → Q • Q}
can coexist in an LR item set.
o True
o False
QuestionNo.4 Marks:05
A recursive descent parser consists of a set of (recursive) routines, each routine
corresponding closely to a rule in the grammar.
- an empty production (N → ε translates to a routine returning true without inspecting any
token.
o True
o False
QuestionNo.5 Marks:05
The dependency graph associated with the attribute evaluation rule of some production
rule (N→ α captures how values flow from one attribute to another, hence, which
attribute depends on which others.
- An inherited attribute can depend on a synthesized attribute.
o True
o False
Question No. 6 Marks : 05
Dotted items (T→ α • β record which part of a token has already been matched. There are
two kinds of basic items: shift items and reduce items.
integer → (•[0 - 9])+
- This is a reduce item.
o True
o False
Question No. 7 Marks : 05
When dealing with attribute grammars it is important to detect cycles in the evaluation
rules to prevent the evaluator to loop endlessly. In the case of dynamic cycle detection,
the AST is traversed multiple times until either all attributes have obtained a value, or a
maximum number of traversals is reached (in which case a cycle can be reported).
- For an AST with N attributes, cycles can be detected dynamically by performing (at
most) N evaluation traversals.
o True
o False
QuestionNo.8 Marks:25
Consider the productions and semantic rules for the expression grammar
a) Write the three-address code that would be generated from the semantic rules
shown for the program fragment (input string)
x:=(a+b)* (c+a)
b) How many temporary variables are used to implement this?
c) The programming language designer has decided to add the pre-increment operator
"++" to the grammar with the production "E →++id". This new operator increments
id, and then returns the value (for example after the code, x=5; y=++x; is
executed then x is 6 and y is 7). Add the semantic rule that will generate code
for this new operator.
Question No. 9 Marks : 05
The regular expressions (a |b) + and a+ |b+ describe the same set of strings
o True
o False
Question No. 10 Marks : 05
In a CFG (Context Free Grammar) the set of terminal and non-terminal symbols may
overlap.
o True
o False
Question No. 11 Marks : 05
The LR(1) parsing technique reduces a handle (the right-hand side of a production N → α
only when the current input token is an element of FOLLOW(N).
o True
o False
Question No. 12 Marks : 15
Consider the following ACTION/GOTO tables:
Show the contents of the stack and input buffer for the shift-reduce parse of input "a",
assuming state 0 is the start state:
QuestionNo.12 Marks:05
Register allocation by graph coloring uses a register interference graph.
- If a node in the graph is connected to N other nodes, then at at least N + 1 registers
(colors) are needed.
o True
o False
QuestionNo.12 Marks:05
Grammars with LL(1) conflicts can be made LL(1) by applying left-factoring,
substitution, and left-recursion removal.
- Left-factoring takes care of FIRST/FIRST conflicts.
o True
o False
QuestionNo.12 Marks:05
Code generation consists of three tasks:
1. instruction selection
2. register allocation
3. instruction ordering
- For generating "optimal" code these three tasks must be considered at once, because
they dependent on each other.
o True
o False
QuestionNo.12 Marks:05
A lexical analyzer generated by lex is essentially a PDA (Push Down Automaton).
o True
o False
Question No. 12 Marks : 05
A lexical analyzer transforms a stream of characters into a stream of tokens.
o True
o False
Question No. 12 Marks : 05
The symbol table is used to pass information only between consecutive stages (lexical
analysis, semantics analysis, etc.) in the compiler pipeline.
o True
o False
Question No. 12 Marks : 05
The stack used in a bottom-up parser contains an alternating sequence of states and
grammar symbols.
o True
o False
Question No. 12 Marks : 05
When generating code at the basic block level, a dependency graph is used instead of an
AST.
- The nodes in the graph represent the basic blocks, and the edges capture the ordering
dependencies that must be obeyed at execution time.
o True
o False
Question No. 12 Marks : 05
A top-down parser creates the nodes in the AST (Abstract Syntax Tree) in preorder.
o True
o False