Java Reference
In-Depth Information
It is often necessary to analyze a grammar to determine if it is suitable for
parsing and, if so, to construct tables that can drive a parsing algorithm. In
this section, we discuss a number of important analysis algorithms that build
upon the basic concepts of grammars and derivations. These algorithms are
central to the automatic construction of parsers, as discussed in Chapters 5
and 6.
The algorithms presented in this chapter refer to a collection of utilities for
accessing and modifying representations of a CFG. The e
ciency of these
algorithms is a
ff
ected by the data structures upon which these utilities are
built.
In this section, we examine how to represent CFGs e
ciently. We
assume that the implementation programming language o
ff
ers the following
constructs directly or by augmentation:
•
A
set
is an unordered collection of distinct entities.
•
A
list
is an ordered collection of entities. A entity can appear multiple
times in a list.
•
An
iterator
is a construct that enumerates the contents of a set or list.
As discussed in Section 4.1, a grammar formally contains two disjoint sets of
symbols,
and
N
, which contain the grammar's terminal and nonterminal
symbols, respectively. Grammars also contain a designated start symbol and
a set of productions. The following observations are relevant to obtaining an
e
Σ
cient representation for grammars:
•
Symbols are rarely deleted from a grammar.
•
Transformations such as those shown in Figure 4.4 can add symbols and
productions to a grammar.
•
Grammar-based algorithms typically visit all rules for a given nontermi-
nal or visit all occurrences of a given symbol in the productions.
•
Most algorithms process a production's RHS one symbol at a time.
Based on these observations, we represent a production by its LHS symbol and
a list of the symbols on its RHS. The empty string
λ
is not represented explicitly
as a symbol. Instead, a production A
has an empty list of symbols for its
RHS. The collection of grammar utilities is as follows.
→λ
