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 rightto-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 evaluation, 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 A0 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 A1 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 A1
from the Stack, then forming A1 + 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 A0
from the Stack, forming the sum A0 + 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.