COSC4307
TEST-2
11/27/2007
Keys
Used
1-5:
BACDC
6-10:
CDDDD
11-15:
ABCCA
16-20:
ABCCA
21-25:
EDAEB
NAME____________________________________________________
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.
(75 points)
Answer all 25
questions in this PART-A. 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.
The
first 12 questions are about the following CFG where each character is a grammar
symbol.
S
-> a S
a
// Rule-1
S
-> R b R
// Rule-2
R
-> c S
c
// Rule-3
R
-> ( S
)
// Rule-4
R
-> b R
// Rule-5
R
-> d
// Rule-6
1.
The OPR “<” applies to
a.
b a
b.
b (
c.
both.
d.
neither.
2.
The OPR “>” applies to
a.
) b
b.
R
b
c.
both.
d.
neither.
3.
The SPR “<” applies to
a.
b c
b.
( c
c.
both.
d.
neither.
4.
The SPR “>” applies to
a.
)
a
b.
)
b
c.
c a
d.
all above.
e.
two above.
f.
none above.
5.
The SPR “=” applies to
a.
R
S
b.
(
)
c.
c
S
d.
all above.
e.
two above.
f.
none above.
****End-of-production-rule
replacement supposition****
6.
The grammar is
a.
LL(1)
b.
an Operator grammar.
c.
both.
d.
neither.
7.
Which rule has the same PREDICT set as its FIRST
set?
a.
rule-1
b.
rule-2
c.
rule-3
d.
all above.
e.
two above.
f.
none above.
8.
The FOLLOW set of the nonterminal S includes, among
others,
a.
)
b.
c
c.
a
d.
all above.
e.
two above.
f.
none above.
9.
The Initial state (I0) of the SLR(1)
parser includes
a.
R -> . ( S )
b.
S -> . a S a
c.
R -> . b R
d.
all above.
e.
two above.
f.
none above.
10.
How many next states does the Initial state of the SLR(1) parser have?
a.
2
b.
3
c.
4
d.
none.
11.
Which is a R.S.F?
a.
a a R b ( S ) a
a
b.
( S ) b b b R
c.
both.
d.
neither.
12.
Which is a S.F?
a.
a ( S ) R a
b.
( S
) b b b d
c.
both.
d.
neither.
13. 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.
14.
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.
c.
Both.
d.
Neither.
15. In
general, given a grammar, the LR(1) parser
a.
has more number of states than the LALR(1) parser
does.
b.
may have a conflict where the LALR(1) parser does not.
c.
Both.
d.
Neither.
16.
Leftmost derivation sequences are for
a.
Top-down
parsers
b.
Precedence-based
parsers
c.
Both.
d.
neither
17.
The syntax stack contents of LL(1) parsers
are
a.
the entire leftmost S.F. at any time.
b.
a proper suffix of a Leftmost S.F most of the time.
c.
Both.
d.
Neither.
18.
A conflict in SLR(1) parsers can occur
between
a.
two Reductions.
b.
one Reduction and one Shift only in a state that
is inadequate.
c.
both.
d.
neither.
19.
Which parse table's empty (blank) entry represents a syntax
error?
a.
LL(1) Parsers.
b.
SLR(1) Parsers
c.
both.
d.
neither.
20.
Which class represents the broadest class of deterministic
parsers?
a.
LR(1) parsers.
b.
SLR(1) parsers.
c.
LL(1) parsers.
21.
Which prevents a grammar from being LL(1)?
a.
a left recursive rule, not necessarily direct.
b.
a non-terminal with two non-disjoint PREDICT sets.
c.
a terminal which is a member in two or more different FOLLOW sets.
d.
all above.
e.
two above.
f.
none above.
22.
In general (that is, most of the times), the
contents of a syntax stack used by Operator Precedence-based
parsers
are
a.
a suffix of the R.S.F.
b.
a prefix of the S.F., not necessarily rightmost.
c.
both.
d.
neither.
23.
Which is true about LALR(1)
parsers?
a.
they
are compromise between SLR(1) parsers and LR(1) parsers.
b.
they
use LR(1) items as a basis for reductions just as SLR(1)
parsers.
c.
They
have the same number of states as LR(1) parsers.
d.
All
above.
e.
two above.
f.
none above.
24. Which
is true about
“Inadequate” states?
a.
they
are the only possible states where a conflict can occur.
b.
they
may contain no “Included” item.
c.
they
may contain no “Completed” item.
d.
All
above.
e.
two above.
f.
none above.
25.
Which is true about “Viable” Prefix?
a.
it
is about any sentential form, not necessarily rightmost
ones.
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.
PART-B.
Other problems
(25 points)
Do
three problems in this PART-B.
For
first four problems in this PART-B, consider the following CFG:
A -> A + B
A -> B A B
A ->
a
B
B ->
(
A ) A
B ->
b
// 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.
Give all pairs of two grammar symbols to each of which the SPR “>”
applies.
D.
Eliminate the (direct) left recursive rule(s) of the non-terminal ‘A’
and
clearly
show the resulting new grammar.
E.
Give the condition(s) for LL(1)
grammars?
And, give a reason of why they are desirable.