Java Reference
In-Depth Information
parser construction by the algorithms we discuss in Chapters 5 and 6 proves a
grammar to be unambiguous. However, when such parser construction fails,
the grammar may or may not be ambiguous. Section 6.4.1 on page 199 presents
some approaches for reasoning about a grammar's ambiguity.
Themost potentially serious flawthat a grammarmight have is that it generates
the “wrong” language. That is, the terminal strings derivable by the grammar
do not correspond
exactly
to the strings present in the desired language. This
is a subtle point, because a grammar typically serves as the very definition of
a language's syntax.
The correctness of a grammar is usually tested informally by attempting
to parse a set of inputs, some of which are supposed to be in the language and
some of which are not. One might try to compare for equality the languages
defined by a pair of grammars (considering one a standard), but this is rarely
done. For some grammar classes, such verification is possible; for others, no
comparison algorithm is known. Determining in general whether two CFGs
generate the same language is an
undecidable problem
.
Backus-Naur form
(BNF) extends the grammar notation defined in Section 4.1
with syntax for defining optional and repeated symbols.
•
Optional symbols are enclosed in square brackets. In the production
A
→α
[
X
...X
n
]
β
1
the symbols
X
1
...X
n
are entirely present or absent between the symbols
of
α
and
β
.
•
Repeated symbols are enclosed in braces. In the production
B
→γ{X
1
...X
m
}δ
theentiresequenceofsymbols
X
...X
m
can be repeated zero or more
1
times.
These extensions are useful in representingmany programming language con-
structs. In Java
TM
, declarations can optionally include modifiers such as final,
static,andconst. Eachdeclarationcanincludea
list
of identifiers. A pro-
duction specifying a Java-like declaration could be as follows:
