A simple arithmetic expression, sum, can be defined as
follows.
sum P[+ sum]
The primitive symbols are P and +,
This example can be used to illustrate recursion and the
technique for scanning text with a transition diagram. The
definition above forces a right-to-left order of evaluation.
Because this definition is recursive, a "Stack" is needed to save
intermediate results whenever sum reinvokes itself. Items
are saved onto this Stack by a PUT operation, and are retrieved
by a GET operation, in a last-in-first-out order. The transition
diagram for the definition of sum above is shown below.
Place value of P into A, that is, P A.
A + Result Result.
A Result.
In order to illustrate the effect of a diagram’s structure on
the order of evaulation, this example can be tested on the input
string P+Q+R eol , where Q and R are separate occurrences
of the symbol P, and eol is the string termination
character. The steps below interpret this string using the above
diagram, in the same fashion as the algorithm on the previous
page uses the MUMPS diagrams in Section 2.
The window is initially positioned at the first character of
the string, P.
Path Ea contains the same symbol as in the window (P);
consequently, the path to node a is traversed and the window is
moved to the next character of the input string.
Action 1 is executed. The value of P is placed in
A0. (A0 is the zero-level occurrence of
temporary variable A.)
Path ab contains the same symbol as in the window (+), causing
transversal of the path to node b, and moving the window to the
next character of the input string.
Path bX is a call to sum. PUT Ao on the Stack and start
at node E, now at level 1.
Path Ea contains the same symbol as in the window (Q=P), so
traverse the path to node a, moving the window to the next input
character.
Action 1 is executed, placing the value of Q in A1.
Path ab contains the same symbol as in the window (+), so
traverse the path to node b, and move the window to the next
character.
Path bX is again a call to sum. PUT Al on
the Stack and start at node E, now at level 2.
As before, path Ea is traversed and the value of R is placed
in A2.
The default blank path aX is now traversed because there is an
end-of-line symbol in the window, which is not the same as a
+.
Action 3 is executed, which places the value in A2
(i.e., R) into Result.
The second call to sum is now complete, so effectively
path bX can now be traversed at level 1.
Action 2 is executed, by first performing a GET Al
from the Stack, then forming Al + Result (which is Q +
R), and finally placing the sum into Result.
The first call to sum is now successful, so path bX can
now be traversed at level 0.
As above, action 2 is executed, doing a GET Ao from the Stack,
forming the sum Ao + Result (which is P + Q + R), and placing
this value into Result.
The variable Result now contains the value obtained from
scanning the input string P+Q+R eol. This value can in
turn be used in another diagram which invoked the sum
diagram, much as Result was used in the recursive calls of sum
above.
A.