Java Reference
In-Depth Information
assignment to an identifier. In the second rule, Stmt is rewritten by symbols
that print an identifier's value.
Productions reference two kinds of symbols:
terminals
and
nonterminals
.
A
terminal
is a grammar symbol that cannot be rewritten. For example, the id,
assign,and$ symbols have no productions in Figure 2.1 that specify how they
can be rewritten. On the other hand, Figure 2.1 does contain productions for
the
nonterminal
symbols Val and Expr. To ease readability in the grammar,
we adopt the convention that nonterminals begin with an uppercase letter and
terminals are all lowercase letters.
Consider a CFG for some programming language of interest. The CFG
serves as a formal and relatively compact definition of
all
syntactically correct
programs for that programming language. To generate such a program, we
begin with a special nonterminal known as the CFG's
start symbol
,whichis
usually the symbol on the
left-hand side
(LHS) of the grammar's first rule.
For example, the start symbol in Figure 2.1 is Prog. From the start symbol, we
proceed by replacing it with the
right-hand side
(RHS) of some production for
that symbol.
We continue by choosing some nonterminal symbol in our derived string
of symbols, finding a production for that nonterminal, and replacing it with
the string of symbols on the production's RHS. As a special case, the symbol
λ
denotes the
empty
or
null string
string, which indicates that there are
no
symbols on a production's RHS. The special symbol $ represents the end of
the input stream or file.
We continue applying productions, rewriting nonterminals until none re-
main. Any string of terminals that can be produced in this manner is consid-
ered syntactically valid. Any other string has a
syntax error
and would not be
alegalprogram.
To show how the grammar in Figure 2.1 defines legal ac programs, the
derivation of one such program is given in Figure 2.2, beginning with the start
symbol Prog. Each line represents one step in the derivation. In each line, the
leftmost nonterminal (surrounded by angle brackets) is replaced by the boxed
text shown on the next line. The right column shows the production number
by which the derivation step is accomplished. For example, the production
Stmt
id assign Val Expr is applied at step 8 to reach step 9.
Notice that some productions in a grammar serve to generate an un-
bounded list of symbols from a nonterminal using recursive rules. For exam-
ple, Stmts
→
Stmt Stmts (Rule 6) allows an arbitrary number of Stmt symbols
to be produced. Each use of the recursive rule—at steps 7, 11, and 17—
generates another Stmt in Figure 2.2. The recursion is terminated by applying
Stmts
→
(Rule 7) at step 19, thereby causing the remaining Stmts symbol to
be erased. Rules 2 and 3 function similarly to generate an arbitrary number of
Dcl symbols.
→λ
