COSC4307 TEST-2 Summer 2004
NAME____________________________________________________
NOTE:
1. Alpha:
A string of grammar symbols, possibly
empty.
2. Lambda: 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. (72
points)
Answer 18 questions in this PART-A. Mark the BEST one choice in each question you choose and clearly cross out those four others you do not choose.
The first 12 questions are about
the following CFG where each character is a
grammar symbol.
S ->
x R S // Rule-1
S ->
y R // Rule-2
R ->
( ) // Rule-3
R ->
( S ) // Rule-4
R ->
S z // Rule-5
1. The
OPR “<” applies to
a. ( x
b. ( y c. both. d. neither.
2. The
OPR “>” applies to
a. ) )
b. ) z c. both. d. neither.
3. The
SPR “<” applies to
a. R y
b. ( y c. both. d. neither.
4. The
SPR “>” applies to
a. ) x
b. ) y
c. z x
d. all above. e. two above. f. none above.
5. The
SPR “=” applies to
a. ( S
b. S )
c. R S
d. all above. e. two above. f. none above.
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-5
d. all above. e. two above. f. none above.
8. The
FOLLOW set of the nonterminal R includes
a. )
b. z
c. x
d. all above. e. two above. f. none above.
9. The
Initial state (I0) of the SLR(1) parser includes
a. G -> . S (The LR(0) item from The
augmented rule)
b. S -> . x R S
c. R -> . S z
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. x R x R y R
b. y x R x R y R z
c. both. d. neither.
12. Which is a S.F?
a. y y y R z
b. y ( y ( S ) )
c. both. d. neither.
13. The PREDICT set of a
production rule must be the same as its FIRST set if
a. the
grammar is LL(1)
b.
the
production rule cannot derive the Empty-String even when the grammar
has Empty-production-rule(s).
c. Both. d. Neither.
14. FOLLOW sets are used
a. in
calculating PREDICT sets even when the grammar has no
Empty-Production-Rule.
b. as
a basis for reductions in LALR(1) parsers.
c. Both. d. Neither.
15. In general, given a grammar, the LR(1)
parser
a. has more number of states than the SLR(1)
parser does.
b. may
have a conflict where the LALR(1) parser does.
c. Both. d. Neither.
16. The syntax stack of
SLR(1) Parsers
a. contain
alternating grammar symbols and state numbers.
b.
have
exactly twice as many symbols popped off as the length of
the RHS of a production rule by
which a reduction is being made.
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 prefix 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
Shifts.
b. one
Reduction and one Shift in a state that is not inadequate.
c. one
shift and one GOTO.
d. all above. e. two
above. f. none above.
19. Which parse table's
empty (blank) entry represents a syntax error?
a. LL(1)
Parsers.
b. Recursive
Descent Parsers.
c. both. d. neither.
20. Which class represents a broadest class of
deterministic parsers?
a. LR(1)
parsers.
b. SLR(1)
parsers.
c. LL(1)
parsers.
d. none.
21. Which prevents a grammar from being LL(1)?
a. a
left recursive rule, not necessarily direct.
b. a
nonterminal with two disjoint PREDICT sets.
c. a
terminal which is a member in two different FOLLOW sets.
d. all
above. e. two above. F. none above.
22. The contents of a
syntax stack used by Operator Precedence-based parsers are,
in general,
a. a suffix of the R.S.F.
b. a prefix of the R.S.F.
c. a prefix of a leftmost S.F.
d. None above.
PART-B. Other problems (28 points)
Do two
problems in this PART-B.
For
problems in this PART-B, consider the following CFG:
A -> B * A
A ->
A + B
A ->
B
B -> b B
B -> B c A
B -> a
// where each character is a grammar symbol.
A.
Calculate
and clearly show FOLLOW set of each nonterminal 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 the condition of LL(1) grammars.
And, eliminate the (direct) left recursive
rule(s) for the nonterminal ‘A’
and clearly show the resulting new grammar.
(Do not worry about the other
nonterminal)