Java Reference
In-Depth Information
A BNF grammar describes the syntax of programs in a programming language. For
example, Appendix B at the end of this topic uses BNF for describing the syntax of j-- and
Appendix C describes the syntax of Java. BNF is described in the next section. The AST
captures the essential syntax of our program.
Why are we interested in a tree representation for our program? Because it is easier to
analyze and decorate (with type information) a tree than it is to do the same with text.
The abstract syntax tree makes that syntax, which is implicit in the program text, explicit.
This is the purpose of parsing.
Before discussing how we might go about parsing j-- programs, we must first discuss
context-free grammars and the languages they describe.
3.2 Context-Free Grammars and Languages
3.2.1 Backus{Naur Form (BNF) and Its Extensions
The grammars that we use to describe programming languages are inherently recursive and
so are best described by what we call context-free grammars. For example, the context-free
rule
S ::=
if(
E
)
S
(3.1)
says that, if E is an expression and S is a statement,
if(
E
)
S
is also a statement. Or, we can read the rule as, a statement S can be written as an
if
,
followed by a parenthesized expression E and finally a statement S. That is, we can read
the \::=" as \can be written as a". There are abbreviations possible in the notation. For
example, we can write
S ::=
if(
E
)
S
j
if(
E
)
S
else
S
(3.2)
as shorthand for
S ::=
if(
E
)
S
S ::=
if(
E
)
S
else
S
(3.3)
That is, we can read the \j" as \or". So, a statement S can be written either as an
if
followed by a parenthesized expression E, and a statement S; or as an
if
, followed by a
parenthesized expression E, a statement S, an
else
, and another statement S.
This notation for describing programming language is called Backus-Naur Form (BNF)
for John Backus and Peter Naur who used it to describe the syntax for Algol 60 in the Algol
60 Report [Backus et al., 1963].
The rules have all sorts of names: BNF-rules, rewriting rules, production rules, pro-
ductions, or just rules (when the meaning is clear from the context). We use the terms
production rule or simply rule.
There exist many extensions to BNF
1
, made principally for reasons of expression and
1
BNF with these extensions is called extended BNF or EBNF.
Search WWH ::
Custom Search