Parsing - Introduction to Compiler Construction in a Java World - page 62

clarity. Our notation for describing j-- syntax follows that used for describing Java [Gosling
et al., 2005].
In our grammar, the square brackets indicate that a phrase is optional, for example,
(3.2) and (3.3) could have been written as

S ::= if( E ) S [ else S]

(3.4)

which says an S may be written as if( E ) S, optionally followed by else S. Curly braces
denote the Kleene closure, indicating that the phrase may appear zero or more times. For
example,

E ::= T f + Tg

(3.5)

which says that an expression E may be written as a term T, followed by zero or more
occurrences of + followed by a term T:

T
T + T
T + T + T
:::

Finally, one may use the alternation sign j inside right-hand sides, using parentheses for
grouping, for example,

E ::= T f( + j - ) Tg

(3.6)

meaning that the additive operator may be either + or - , allowing for

T + T - T + T

This extended BNF allows us to describe such syntax as that for a j-- compilation unit,

compilationUnit ::= [ package qualiedIdentier ; ]
f import qualiedIdentier ; g
ftypeDeclarationg EOF

(3.7)

which says that a j-- compilation unit may optionally have a package clause at the top,
followed by zero or more imports, followed by zero or more type (for example, class) decla-
rations 2 . The EOF represents the end-of-file.
These extensions do not increase the expressive power of BNF because they can be
expressed in classic BNF. For example, if we allow the empty string on the right-hand
side of a production rule, then the optional

[X Y Z]

can be expressed as T, where T is defined by the rules

T ::= X Y Z
T ::=

2 Yes, syntactically this means that the input file can be empty. We often impose additional rules, enforced
later, saying that there must be at most one public class declared.