Java Reference
In-Depth Information
1 Start
→
Value $
2 Value
→
num
3
|
lparen Expr rparen
4 Expr
→
plus Value Value
5
|
prod Values
6 Values
→
Value Values
7
| λ
Figure 7.9: Grammar for Lisp-like expressions.
For a review of this style of writing top-down parsers, see Sec-
tion 2.5 on page 39 and Section 5.3 on page 149. The relevant
grammar analyses and parser constructions are given as Exercise 2
on page 173.
Rule 1 generates an outermost expression whose value should be printed as
the result of the syntax-directed translation. For example, the input
( plus 31 ( prod 10 2 20 ) ) $
should print 431.
A Value is defined by Rule 2, which allows a simple numeric value via
num, and Rule 3, which treats the result of a parenthesized expression as a
value. Rules 4 and 5 generate the sum of two values and a product of zero
or more values, respectively. The grammar lacks many features that would
be expected in an expression-oriented language. A more complete expression
grammar is considered in Exercises 4 and 5. The recursive rule for Values is
right recursive to accommodate top-down parsing (Section 5.5 on page 154).
A recursive-descent parser for the grammar in Figure 7.9 is shown in
Figure 7.10. As discussed in Chapter 5, the parser contains a procedure for
each nonterminal in the grammar. To conserve space, the error checks normally
present at the end of each
switch
statement are absent in Figure 7.10.
The parser in Figure 7.10 is also equipped with semantic actions that
compute and print expression values. It is common in recursive descent
parsing for semantic actions to make use of inherited and synthesized values.
Inherited values aremanifest as parameters passed into a method; synthesized
values are returned bymethods after deriving their parse subtrees. These ideas
are combined in the parser of Figure 7.10 as follows:
•
AtMarker
5
, the semantic value synthesized froma Value parse subtree
is printed.
