Java Reference
In-Depth Information
foreach
p
∈
Prods
of the form “ A
→α
[
X
1
...
X
n
]
β
”
do
N
←
N
ew
N
on
T
erm
()
p
←
”
Prods
←
Prods
∪{
“ A
→α
N
β
“
N
→X
1
...
X
n
”
}
}
foreach
p
∈
Prods
of the form “ B
Prods
←
Prods
∪{
“
N
→λ
”
→γ{X
1
...
X
m
}δ
”
do
M
←
N
ew
N
on
T
erm
()
p
←
”
Prods
←
Prods
∪{
“ B
→γ
M
δ
“
M
→X
1
...
X
n
M
”
}
Prods
←
Prods
∪{
“
M
→λ
”
}
Figure 4.4: Algorithm to transform a BNF grammar into standard
form.
Declaration
→
[ final ][static ][const ] Type identifier
{
, identifier
}
This declaration insists that the modifiers be ordered as shown. Exercises 13
and 14 consider how to specify the optional modifiers in any order.
Although BNF can be useful, algorithms for analyzing grammars and
building parsers assume the standard grammar notation as introduced in
Section 4.1. The algorithm in Figure 4.4 transforms extended BNF grammars
into standard form. For the BNF syntax involving braces, the transformation
uses
right
recursion on
M
to allow zero or more occurrences of the symbols
enclosed within braces. This transformation also works using left recursion—
the resulting grammar would have generated the same language.
As discussed in Section 4.1, a particular derivation (e.g., leftmost or right-
most) depends on the structure of the grammar. It turns out that right-recursive
rules are more appropriate for top-down parsers, which produce leftmost
derivations. Similarly, left-recursive rules are more suitable for bottom-up
parsers, which produce rightmost derivations.
Compilers are expected to verify the syntactic validity of their inputs with
respect to a grammar that defines the programming language's syntax. Given
a grammar G and an input string
x
, the compiler must determine if
x
∈
L(G).
An algorithm that performs this test is called a
recognizer
.
For language translation, we must determine not only the string's validity,
but also its structure, or
parse tree
. An algorithm for this task is called a
parser
.
Generally, there are two approaches to parsing:
