COSC4307
Test-1
6/19/2008
NAME
(Please
PRINT)____________________________________________________
NOTE:
1.
Alpha:
A string of grammar symbols, possibly empty.
2.
l:
The empty-string.
3.
A -> Alpha:
A production rule of a CFG.
4.
RHS:
Right-hand side
5.
S.F:
Sentential Form.
6.
R.S.F:
Rightmost sentential form
7.
CFG:
Context-Free Grammar.
8.
OPR:
Operator Precedence Relation
9.
SPR:
Simple Precedence Relation
PART-A.
Multiple Choices.
(84 points)
Answer 28
questions in this PART-A by clearly crossing out those you select not to
ANSWER..
Each question
is 3 points worth.
Mark
your BEST choice by writing down a
big A or B or C or D or E or F in Capital by
each
question number you select to answer.
1. Which is for compiling a source
program?
L
P
S P
a. M --- --
b. N --- --
c. both.
d.
neither
M.M L
N.N N
L
S
2.
M ----
----
M.M
L.N
a. Above may
represent converting a compiler into another.
b.
Above may produce a compiler that can be
run by the same computer being used.
c.
both.
d. neither.
3. Identifier scope rule is for
binding
a. local
names
b. non-local names
and parameters.
c. both.
d. neither.
4. The Static Scope rule is more suitable
than the Dynamic Scope rule when
a. subprograms or
blocks can be nested.
b. only non-local
names need to be bound. c.
both.
d. neither.
5. Which is true about
lex?
a. it is an
automatic parser generator supported by UNIX.
b.
it
produces a C program as functions that the wanted scanner needs are provided as
a part
of inputs.
c. both. d.
neither.
6. Which is true of an ambiguous
grammar?
a. at least one
sentence of the language being defined by the grammar is
ambiguous.
b.
at
least one grammar may define the same language that the grammar defines.
c.
both.
d. neither.
7. The stack used in Program-2 (Scanner
Generator)
a. is to be pushed
onto each time a block starts in the source program being
compiled.
b. is to be popped
off each time a block ends in the source program.
c. both.
d. neither.
8. Which is
true of Automatic Scanner Generators?
a. regular
expressions are used in their inputs.
b. they essentially
convert regular expressions into Finite State Acceptors.
c. both.
d. neither.
9. A parse
tree of a given sentence may show
a. only one leftmost
derivation sequence.
b. two different
derivation sequences, not leftmost nor rightmost.
c. both.
d. neither.
10. Two
different leftmost derivation sequences of a given sentence may
imply
a. two different
parse trees of the same sentence.
b. two different
meanings of the same sentence.
c. both.
d. neither.
11. Which
makes the task of a scanner design easier and simpler?
a. when blanks are totally
ignored.
b. when
keywords are strictly reserved.
c.
both.
d.
neither.
12.
Which parse table's empty (blank) entry represents a syntax
error?
a.
LL(1) Parsers.
b.
Recursive Descent Parsers
c.
both.
d.
neither.
13.
Which prevents a grammar from being LL(1)?
a.
a left recursive rule, not necessarily direct.
b.
a non-terminal with two disjoint PREDICT sets.
c.
a non-terminal whose two
production rules have a Common Prefix.
d.
all above.
e.
two above.
f.
none above.
14.
Which is true about a Viable Prefix?
a.
it
is about rightmost sentential
forms.
b.
it
must be recognized by a state of SLR(1) parsers.
c.
It
may not be recognized by any state of an SLR(1) parser.
d.
All
above.
e.
two above.
f.
none above.
A
= alpha B
// alpha is a string of grammar symbols
15.
If a grammar has above two production rules,
a.
Follow set of A and
Follow set of B are the same.
b.
Both non-terminals
have left recursions.
c.
Both.
d.
neither.
Next
10 questions are about the following CFG where each character is a grammar
symbol.
S -> a
S b
// Rule-1
S -> R
b
// Rule-2
R -> c
S c
// Rule-3
R -> (
)
// Rule-4
R -> S
d R
// Rule-5
R -> l
// Rule-6
16.
The OPR < applies to
a.
a c
b.
a (
c.
both.
d.
neither.
17.
The OPR > applies to
a.
b b
b.
b d
c.
both.
d.
neither.
18.
The OPR = applies to
a.
( )
b.
a b
c.
both.
d.
neither.
19.
The nonterminal S leftmost derives (in one or more
steps)
a.
a
b.
c
c.
R
d. all above.
e. two above.
f.
none
20.
The nonterminal R leftmost derives (in one or more
steps)
a.
a
b.
c
c.
R
d. all above.
e. two above.
f. none
21.
Which is a NEXT pair?
a.
c
a
b.
b
c
c.
a a
d. all above.
e. two above.
f.
none.
22.
Which is a S.
F.?
a.
S d R
b
b.
S d ( ) b
c.
R b d
R b
23.
Which is a R. S.
F.?
a.
S d R
b
b.
S d ( ) b
c.
R b d
R b
24.
Which rule has the same PREDICT set as its FIRST
set?
a.
rule-1
b.
rule-5
c.
rule-6
d.
all above.
e.
two above.
f.
none above.
25.
The FOLLOW set of the nonterminal R includes, among
others,
a.
b
b.
c
c.
a
d.
all above.
e.
two above.
f.
none above.
26. The
PREDICT set of a production rule must be the same as its FIRST set if
a.
the grammar has no Empty-production-rule.
b.
the
production rule cannot derive the Empty-String even when the
grammar
has
an Empty-production-rule.
c.
Both.
d.
Neither.
27.
FOLLOW sets are used
a.
in calculating PREDICT sets when the grammar has an Empty-Production
rule.
b.
as a basis for reductions in SLR(1) parsers as they are kind of
underestimates.
c.
Both.
d.
Neither.
28.
Leftmost derivation sequences are for
a.
LL(1)
parsers and Recursive Descent parsers.
b.
Precedence-based
parsers
c.
Both.
d.
neither
29.
In general (that is, most of the times), the contents of a syntax stack
used by LL(1) parsers
are
a.
a suffix of the leftmost S.F.
b.
a prefix of the S.F., not necessarily leftmost.
c.
both.
d.
neither.
30.
Which computes
R+ nt
a.
R* nn R nt
b.
R+ nn R nt
c.
neither.
31.
Which is for the bottom-up parsers?
a.
the rightmost derivation sequence.
b.
the rightmost derivation sequence in reverse.
c.
Both.
d.
neither.
32.
Which is a compiler design issue beyond the basic issues of source
language and the target
language
requirements?
a.
number of passes.
b.
Bootstrapping and error
processing.
c.
Subprogram
handling.
d.
All
above.
e. two
above.
33.
Which is true of bootstrapping?
a.
it
is a shortcut in compiler design by taking advantage of hardware
architectures.
b.
It
enables us to avoid translating the intended source language at
all.
c.
Both.
d.
neither.
34.
Which can represent a class of tokens?
a.
context-free
grammars
b.
regular expressions
c.
both.
d.
neither.
35.
Which is a sub-task of a scanner?
a.
memory allocation even when the exact
memory size is not known.
b.
symbol table creation and
maintenance.
c.
Both.
d.
neither.
PART-B.
Other problems
(16 points)
Do
two problems in this
PART-B.
For
first three problems in this PART-B, consider the following CFG:
A -> A +
B
A -> B a B
B -> ( D )
B -> D D
D -> D b
D -> a
// where each character is a grammar symbol.
A.
Calculate and clearly
show FOLLOW set of each non-terminal of above grammar.
Do
not forget using the end-marker, $.
B.
Give the description of each function of a Recursive descent parser for
the above grammar.
C.
Calculate and clearly show the NEXT matrix for the grammar. It must be
5-5.
D.
What
is the condition for LL(1) grammars???
E.
Describe
some issues of complier design beyond the basic issues of source and target
languages in no more than 12 lines.