Java Reference
In-Depth Information
CFGs are a notational mechanism for specifying languages. Just as there
are many programs that compute the same result, so also there are many
grammars that generate the same language. Some are better suited for a
particular translation task, as discussed in Chapter 7. Some grammars have
one or more of the following problems that preclude their use:
•
The grammar may include useless symbols.
•
The grammar may allow multiple, distinct derivations (parse trees) for
some input string.
•
The grammar may include strings that do not belong in the language, or
the grammar may exclude strings that are in the language.
In this section, we discuss these problems and their implication for language
processing.
A grammar is
reduced
if each of its nonterminals and productions participates
in the derivation of some string in the grammar's language. Nonterminals
that can be safely removed are called
useless
.
1 S
→
A
2
|
B
3 A
→
a
4 B
→
Bb
5 C
→
c
The above grammar contains two kinds of nonterminals that cannot participate
in any derived string:
•
With S as the start symbol, the nonterminal C cannot appear in any
phrase.
•
Any phrase that mentions B cannot be rewritten using the grammar's
rules to contain only terminals.
When B, C, and their associated productions are removed, the following re-
duced grammar is obtained:
1 S
→
A
2 A
→
a
