Java Reference
In-Depth Information
13. Section 4.3 describes extended BNF notation for optional and repeated
symbol sequences. Suppose the
n
grammar symbols
X
...X
n
represent
1
asetof
n
options. What is the e
ect of the following grammar with
regard to how the options can appear?
ff
Options
→
Options Option
| λ
Option
→X
1
|X
2
···
|X
n
14. Consider
n
optional symbols
...X
n
as described in Exercise 13.
(a) Devise a CFG that generates any subset of these options. That is,
the symbols can occur in any order, any symbol can be missing, and
no symbol is repeated.
(b) Howdoes
n
(the number of options) a
X
1
ff
ect the size of your grammar?
(c) How is your solution a
ff
ected if symbols
X
i
and
X
j
are present only
if
i
<
j
?
15. Referring to Section 4.1.4, show that regular grammars and finite au-
tomata (Chapter 3) have equivalent power by developing
(a) an algorithm that translates regular grammars into finite automata
and
(b) an algorithm that translates finite automata into regular grammars.
16. Referring to Section 4.2.1, devise an algorithm to detect nonterminals
that cannot be reached from a CFG's goal symbol.
17. Referring to Section 4.2.1, devise an algorithm to detect nonterminals
that cannot derive any terminal string in a CFG.
18. A CFG is reduced by removing useless terminals and productions. Con-
sider the following two tasks.
(a) Nonterminals not reachable from the grammar's goal symbol are
removed (Exercise 16).
(b) Nonterminals that derive no terminal string are removed (Exer-
cise 17).
Does the order of the above tasks matter? If so, which order is preferred?
