Game Development Reference
In-Depth Information
much easier to compute since they work so well with a stack. Ultimately, all ASTs
(whether mathematical expressions or otherwise) will be traversed in a post-order
manner after syntax analysis.
But in order to traverse the AST, we first must generate one. The first step toward
generating an AST is to define the grammar of the language. A classic way to
define grammars for computer languages is to use
Backus-Naur Form
, which is
often abbreviated as BNF. BNF is designed to be relatively succinct; the grammar
for a calculator that can do integral addition and subtraction might be defined as
follows:
<integer> ::== [0-9]+
<expression> ::== <expression> "+" <expression>
| <expression> "-" <expression>
| <integer>
The
::==
operator means “is defined as,” the
|
operator means “or,” and
<>
are
used to denote grammar rule names. So the preceding BNF grammar says that an
expression can be either an expression plus another expression, or an expression
minus another expression, or an integer. Thus,
5 + 6
would be valid because 5
and 6 are both integers, which means they can both be expressions, which in turn
means they can be added together.
As with tokenization, there are tools you can use to help with syntax analysis. One
such tool is bison, which allows for C/C++ actions to be executed whenever a
grammar rule is matched. The general usage of the action is to have it create the
appropriate node that goes into the AST. For instance, if an addition expression
werematched,anadditionnodecouldbegeneratedthathastwochildren:oneeach
for the left and right operands.
This means it's best to have a class corresponding to each possible node type. So
the addition/subtraction grammar would need to have four different classes: an ab-
stract base expression class, an integer node, an addition node, and a subtraction
node. This hierarchy is shown in
Figure 11.4
.
