Java Reference
In-Depth Information
1 Start
→
Stmt $
2 Stmt
→
id assign E
3
|
if
lparen E rparen Stmt else Stmt fi
4
|
if
lparen E rparen Stmt fi
5
|
while lparen E rparen do Stmt od
6
|
begin Stmts end
7 Stmts
→
Stmts semi Stmt
8
|
Stmt
9 E
→
EplusT
10
|
T
11 T
→
id
12
|
num
Figure 7.14: Grammar for a simple language.
Figure 7.14 shows a grammar for a language that is relatively simple but con-
tains features found in most programing languages. The language uses only
integer data types, so declarations are unnecessary. We begin by considering
each portion of the grammar in Figure 7.14 with the purpose of designing its
AST structure.
Assignment statements
Type analysis and code generation will require in-
formation about the target of the assignment and the value that will be
stored at that target. The AST structure for an assignment statement
can therefore be close to its concrete syntax. The assignment operator
becomes the parent of the identifier and expression subtree, as shown in
Figure 7.15(a).
if
statements
There are two forms of if statements in the grammar: Rule 3
generates an else clause and Rule 4 does not. We could design separate
AST structures for each, but amore consistent approach views the second
form as an instance of the first, with a
null
node inserted to represent the
else clause.
Figure 7.15(c) show an AST structure suitable for both cases. The con-
crete syntax uses 6-8 symbols for an if statement, but most of those are
punctuation required by the source language's syntax. Those symbols
serve to disambiguate the language and make programs written in the
language easier to read. However, only the essential elements are re-
tained in Figure 7.15(c): the predicate that is tested by the statement and