Parsing Numerical and Address
Expressions in ANS Forth

The finite state machine for numerical evaluation manipulates four list instances for each level of nested brackets. They describe the state of an expression at a given level, including a list for numbers and three lists for binary operators with three precedences.

All four lists are double-ended, so their tails can be appended to, and they can be traversed starting at their heads. That is, they act as queues.

The three operator lists are single-linked, because there is no need to delete individual nodes. The operator nodes contain the execution token of the binary operation and a pointer to the node in the number list containing the leftmost number of the pair on which it operates.

The number list is double-linked, because the algorithm described below deletes the left-number node once an operation is performed.

The code also uses a single-ended, single-linked list of maps, one for each level of expression nesting, which acts as a LIFO stack. The top of the stack, i.e., the list head, is used for the currently active subexpression.

Nodes in the map list include head and tail pointers for the four expression list instances described above, plus the execution array index for the numerical function to be applied to the expression when its level is completed. If the level was started by an actual or implicit, simple left bracket, the function is a no-op. But levels are also started by numerical functions, whose arguments are numerical expressions.

A subexpression can be evaluated in principle when it is well-formed, i.e., when its number and three binary operator lists contain one more number than the total number of operators. It can be evaluated legally only when its level has been properly terminated.

To evaluate a well-formed subexpression, visit the nodes of the first precedence list in order until it is exhausted. At each node, perform the operation on the two numbers it sits between in the expression, the left one at the number node to which the operation node points, and the right one at the number node's successor in the number list. Delete the left-number node and replace the number in its successor by the result of the operation.

Repeat for the remaining operator lists in order of their precedence. At this point the single node remaining in the number list contains the evaluation.

The finite state machine for recognition and evaluation of numerical expressions is simple in that all exclusive inputs have a unique action and state transition. Instead of representing the machine by a 2x2 maxtrix, with rows labeled by the state and columns by inputs and transitions, we represent it as a one-dimensional array of states, each of which has a one-dimensional array of actions that combine input recognition, manipulation of expression and map lists, and state transition.

The initial input string is assumed to contain nothing beyond the expression. When the input to an action is recognized at the beginning of the input string, it is parsed away from the next input. The treatment of whitespace is not described here.

Numerical machine skeleton:

	0.	map-opened:	termop >2	num >1	[func]lbrak >0
	1.	num-added:	op >2	eostring >exit	rbrak >1
	2.	op-added:	num >1	[func]lbrak >0

The machine works like this:

• It starts at the map-opened state with a single map in the map list, with empty expression lists and a no-op function.

• New maps with empty expression lists are pushed onto the map list by the [func]lbrak action. The function in the map is a no-op if the input is a simple left bracket, or a numerical function if the input is a legal function name followed by a left bracket.

• The rbrak action evaluates the expression in the top map, appends the value to the number list in the second map, and pops the top map. It can be satisfied only if there are at least two maps and a well-formed expression.

• The num action stores the input number in a node appended to the number list.

• The termop action appends a node containing zero to the empty number list and then does the op action.

• The op action appends a node to the operator list of appropriate precedence, with the operator execution token and the pointer to the last node in the number list.

• The eostring action evaluates the completed expresssion. It can be satisfied only if the input string is empty and there is exactly one map left.

• If none of the actions following a state is satisfied, the machine exits with the original input string and a false flag, after clearing the expression and map lists.

An external global may appear in an address expression only once, and the expression must resolve to the unscaled global plus a numerical offset.

The translator evaluates an address expression by computing its block signature, i.e., that it closes on a block or numerical offset, or resolves to an external global plus a numerical offset. It does not reduce numerical subexpressions to actual numbers.

Addresses themselves appear only in a linear fashion in address expressions. They are not allowed to be individually scaled by numerical factors, but combinations of simple sums and differences that resolve to a numerical offset may be scaled. To facilitate parsing in this situation, we require brackets when such combinations are to be scaled; and we require that brackets be used only for simple combinations that must resolve to a numerical offset, with no nesting. We also require that numbers appear only as simple numbers or names of numerical expressions defined by the .SET pseudo-op (recognized by the num-name terminal below). Since names for address expressions defined by the .EQU pseudo-op may also occur (recognized by the addr-ref terminal below), the absence of nested brackets is not a semantic restriction.

	addr-expr	::=	[termop] (addr-monom | addr) {termop (addr-monom | addr)}
	addr-monom	::=	[num {factorop num} '*'] addr-bracket {factorop num}
	addr-bracket	::=	'[' simple-addr-expr ']'
	simple-addr-expr	::=	[termop] addr {termop addr}
	addr	::=	addr-ref | temp-ref | num | '.'
	num	::=	dec# | hex# | num-name | asc# | oct# | bin#

The '.' literal in the addr production is the assembler label for the current location. It occurs last because AAma allows leading dots in several types of names recognized by addr-ref and num-name.

Evaluation of an address expression obeying this grammar imposes the further condition that addr-bracket must resolve to a numerical offset, and hence so does addr-monom. Our implementation of evaluation requires an initialization each time the start production addr-expr is called, which we mention because failure to do so was for us a hard bug to find.

Normal syntax elements have the stack pattern:

  ( s -- after.s true | s false )

That's opposed to a separation pattern

  ( s -- after.s hit.s true | s false )

Any participation of a syntax element in the semantics of evaluation is assumed here to occur only as a side effect, and only in the true case. Any hit.s from an intermediate separation pattern is consumed.

We emphasize that the false case is supposed to have no net semantic side effect. The arrangement to accomplish this is called backtracking. In the case of combinations, it entails unwinding any semantic side effects accumulated by elements that were satisfied before the combination failed.

The upto syntax elements associated with a normal syntax element b are {b}, [b], and {n: b}. The normal recognition pattern is not appropriate for them, since failure to recognize b satisfies the upto condition. We could live with an always true recognition pattern:

  ( s -- s' true )

  ( s -- after.s | s )

The or sequence is the simplest combination, in that it requires no backtracking beyond that implicit in the normal stack pattern of its elements. The Forth template for Backus-Naur or forms with normal elements bi is

  \ b1 | ... | bn  ( s -- after.s true | s false )
  COND
    b1 NIF
    b2 NIF
    ...
    bn ELSES true THEN

The and sequence requires explicit backtracking, which we implement with the help of three words save-sem (save semantics), 'tis, and 'taint.

In the simplest case, where there is only recognition and no semantic accumulation, they can be defined as:

  : save-sem  ( s -- s s )                  sdup ;
  : 'tis      ( s after.s -- after.s true ) sswap sdrop true ;
  : 'taint    ( s after.s -- s false )      sdrop false ;

When there are semantic side effects, these definitions would occur as factors in more elaborate definitions. The model we have in mind is to do semantic accumulation by pushing items onto one or more semantic stacks, and to use a backtracking stack to record the semantic stack pointers for unwinding the accumulation.

Then save-sem would have the extra function of pushing a copy of the current semantic stack pointers onto the backtracking stack, 'tis would have the extra function of dropping that information from the backtracking stack, leaving the accumulation on the semantic stacks intact, and 'taint would have the extra function of restoring the semantic stack pointers to the values popped from the backtracking stack, thus dropping the semantic accumulation since the last save-sem.

The backtracking stack can also serve to define frames on the semantic stacks, to be replaced by evaluation of subexpressions at the successful completion of bracket levels.

Our policy is to leave the primitive definitions of save-sem, 'tis, and 'taint alone, and to use a text editor to replace the names in generated code with those of words that also handle the semantic and backtracking stacks.

With these words, the Forth template for Backus-Naur and forms with normal elements bi is:

  \ b1 ... bn  ( s -- after.s true | s false )
  COND save-sem
    b1 IF
    ...
    bn IF
    'tis ELSES 'taint THEN

We emphasize that the net stack effect of both or and and templates is the same as that of a normal element. Furthermore, if save-sem, 'tis, and 'taint properly backtrack the semantic state, semantic side effects occur when the result is true.

If we furthermore assume that the semantic side effects in the true branches of the b's are properly designed, then these templates recurse, in the sense that they may themselves appear wherever b's occur in such templates.

We call and and or templates normal templates because they produce normal elements, and can themselves be used as normal arguments in templates.

  \ {b}     ( s -- after.s | s )
  BEGIN b NUNTIL

  \ {n: b}  ( s -- after.s | s )
  n 0 DO b drop LOOP

  \ [b]     ( s -- after.s | s )
  b drop

Any element following a u element in an or sequence would be ignored, because an upto is always satisfied; so we propose no template that or's upto elements with subsequent normal or upto elements.

Upto templates can be turned into normal templates by simply appending true:

  u true

Here u can also be an upto merge, discussed in the next section.

And subsequences of u's have a nice property: a simple code sequence of Forth u templates represents both the recognition and semantic side effects of the corresponding bnf and sequence, and has a combined stack effect of the same form as that of a single element:

  ( s -- after.s | s )

So now let's use u labels, not just for individual upto elements or templates, but also for and sequences of upto elements or code sequences of their templates. We call such a sequence an upto merge.

A Forth code sequence

  u1 ... un b

Seminormal merges work fine in the basic and template, because its backtracking logic undoes the semantic accumulation of previous elements, restoring the semantic state to that at the beginning of the entire sequence.

To help keep track of when seminormal merges are legal in templates, we introduce w labels to represent arguments that can be either normal elements or seminormal merges. In the template summary section, we rewrite the basic and template with w arguments, which covers all cases except those with a trailing upto argument.

To cover that, we add a normal and template with an explicit upto argument:

  \ w1 ... wn u  ( s -- after.s true | s false )
  COND save-sem
    w1 IF
    ...
    wn IF
    u 'tis ELSES 'taint THEN

  \ b u  ( s -- after.s true | s false )
    b IF
    u true ELSE false THEN

Recursion ultimately defines everything in terms of basic, normal elements, which are to have normal stack patterns and semantic side effects.

Normal templates: ( s -- after.s true | s false )

1. A Forth word with appropriate syntax recognition and semantic backtracking.

2. An or template built from two or more normal templates:

     \ b1 | ... | bn
     COND
       b1     NIF
       ...
       b(n-1) NIF
       bn     ELSES true THEN
   

3. An and template built from one or more seminormal arguments:

     \ w1 ... wn
     COND save-sem
       w1 IF
       ...
       wn IF
       'tis ELSES 'taint THEN
   

   For n = 1, this template should be used only with a seminormal argument, which needs the extra backtracking.

4. An upto template followed by true:

     \ u
     u true
   

5. An and template built from one or more normal templates and a trailing upto template:

     \ w1 ... wn u
     COND save-sem
       w1 IF
       ...
       wn IF
       u 'tis ELSES 'taint THEN
   

   Simplification for n = 1 and normal w:

     \ b u
       b IF
       u true ELSE false THEN