Java Reference
In-Depth Information
resulting string. The set of terminal strings derivable from S comprises the
context-free language
of grammar G, denoted L(G).
In describing parsers, algorithms, and grammars, consistency is useful in
denoting symbols and strings of symbols. We therefore adopt the following
notation:
Names Beginning With
Represent Symbols In
Examples
Uppercase
A, B, C, Prefix
N
Lowercase and punctuation
Σ
a, b, c, if, then, (, ;
X
,
Y
N
∪Σ
X
i
,
Y
3
)
Other Greek letters
(
N
∪Σ
α
,
γ
Using this notation, we write a production as A
...X
m
, depend-
ing on whether the detail of the production's
right-hand side
(RHS) is of in-
terest. This format emphasizes that a production's
left-hand side
(LHS) must
be a single nonterminal while the RHS is a string of zero or more vocabulary
symbols.
There is often more than one way to rewrite a given nonterminal; in such
cases, multiple productions share the same LHS symbol. Instead of repeating
the LHS symbol, an “or notation” is used.
→α
or A
→X
1
A
→ α
| β
···
| ζ
This is an abbreviation for the following sequence of productions:
A
→ α
A
→ β
···
A
→ ζ
If A
→γ
is a production, then
α
A
β⇒αγβ
denotes one step of a derivation using
⇒
+
(derives in one or more steps) and
⇒
this production. We extend
⇒
to
⇒
β
(derives in zero or more steps). If S
is said to be a
sentential form
of the CFG. SF(G) denotes the set of sentential forms of grammar G.Thus
L(G)
,then
β
∩Σ
. That is, the language of
G is simply those sentential forms of G that are terminal strings.
Throughout a derivation, if more than one nonterminal is present in a
sentential form, then there is a choice as to which nonterminal should be
expanded in the next step. Thus to characterize a derivation sequence, we need
to specify, at each step, which nonterminal is expanded and which production
={
w
∈Σ
|
⇒
+
w
}
S
.Also,L(G)
=
SF(G)
