Page 218 - Introduction to Microcontrollers Architecture, Programming, and Interfacing of The Motorola 68HC12

7,3 From Formulas to Subroutine Calls 195

Figure 7.13. Algorithm to Write a Sequence of Subroutine Calls for (8)
The reader is invited to find these parsing trees for the formulas given in the
problems at the end of the chapter. Note that a parsing tree is really a good way to write
a formula because you can see "what plugs into what" better than if you write the
formula in the normal way. In fact, some people use these trees as a way to write all of
their formulas, even if they are not writing programs as you are, because it is easier to
spot mistakes and to understand the expression. Once the parsing tree is found, we can
write the sequence of subroutine calls in the following way. Draw a string around the
tree, as shown in Figure 7.13. As we follow the string around the tree, a subroutine call
or PUSH is made each time we pass a node for the last time or, equivalently, pass the
node on the right. When a node with an operand is passed, we execute the macro PUSH
for that operand. When a node for an operation is passed, we execute a subroutine call for
that operation. Compilers use parsing trees to generate the subroutine calls to evaluate
expressions in high-level languages. The problems at the end of the chapter give you an
opportunity to learn how you can store parsing trees the way that a compiler might do it,
using techniques from the end of Chapter 6, and how you can use such a tree to write the
sequence of subroutine calls the way a compiler might.
As a second example, we consider a program evaluating the consecutive expressions

delta = delta + c
s = s + (delta * delta)

These can be described by the trees