.H 1 "Parser Tools and the BNF parser"

.H 2 "An Overview"

The parser tools are modelled after the (old) REDUCE system META utility
which is a parser-generator program. The definition of a parser, for
our purposes, is a function which takes arguments in the form
.nf
 
        ob1 ... obn n toktyptab string offset token
.fi 
  and returns results in the form
.nf 
       ob1' ... obn' n' toktyptab' string offset' token' flag TRUE
.fi 
  or
.nf 
       ob1 ... obn n toktyptab string offset token false

.fi 

The interpretation of these pieces conforms to the intuitive notion
of a parser. ob1 ... obn are objects previously parsed, and n is a
(system) integer representing the number of objects. Toktyptab is a token-type 
table, described in a later section.
String is the character
string being parsed, token is also a string, but represents the piece
of the string currently being considered. Offset is a (system) integer
offset (base 1) into (or beyond) the string and points to the first character
not accounted for in the token.

The flags returned have the following interpretation. If FALSE is returned,
then parsing was never started. If TRUE TRUE is returned, then parsing was
started and successfully completed. If FALSE TRUE is returned, then parsing
was started, but not completed (usually an error condition).

The parser-generator is included herein as a macro and produces
a parser from its BNF (Backus-Nauer-Form) description. Our version of the 
Backus-Nauer form
consists of a sequence of clauses separated by /'s. Each clause is a sequence
of parsers. The evaluation of a BNF of the form A B C ...  first evaluates A,
and
if A returns FALSE, then 
B C ... is ignored and FALSE is returned. If A returns
FALSE TRUE, then B C ... is again ignored and FALSE TRUE is returned.
If A returns TRUE TRUE then B C ... is evaluated sequentially until either a
FALSE or a FALSE TRUE is returned, or the sequence completes. In the first
case FALSE TRUE is returned, in the second case TRUE TRUE is returned.
 
A BNF of the form  A B / C D is evaluated by evaluating A B as above, and if
the result is FALSE, the evaluate C D as above and return whatever is returned
by this evaluation. On the other hand, if the evaluation of A B returns
TRUE TRUE or FALSE TRUE, then C D is not evaluated, and the result of A B is
returned.

The parser generator is invoked from the normal parser by the token BNF and is
ended by the token ENDBNF. Immediately following the BNF is an optional declaration of the
form
.nf
EXTERNAL name...name ;
.fi
Following this  are a sequence of parser
definitions, each starting with a name and then a colon,
and ending with a semicolon. Between colon and the semicolon, and in addition to the clause
seperator / , are sequences of parser references which can be
.nf
 
      i) a program in <<..>> syntax, which is assumed to be a parser.
     ii) a name, assumed to be the name of a parser.
    iii) the token " followed by another token.
     iv) the token CK" followed by another token
      v) one of the above enclosed in square brackets
     vi) one of SWAPIN or SWAPOUT followed by the name of a tokentype table
      vi) the token // used in the same way as / .

 .fi

In addition, the name in the first definition can be preceded by MAIN indicating that the parser
being defined is a top-level parser which requires only a string on entry (rather than the
standard parser entry conditions given previously.)

As an example of a parser, consider the following parser of a list of names:
.nf
   BNF
   EXTERNAL aname MyTTT ;
   MAIN list : 
          SWAPOUT MyTTT 
        leftbrace terminator ;
   terminator: 
        rightbrace /
        aname terminator /
        list terminator ;
   leftbrace: 
        "{ ;
   rightbrace 
        "} ;
   ENDBNF
 
.fi
The "BNF" indicates to the HP-48's parser that the remainder of this structure should be
interpreted as a BNF definition.

The line starting with "EXTERNAL" indicates that two objects should be taken from the stack
and bound to the names "aname" and "MyTTT".

The next line defines the initial parser (the one which will be called first on entry) and indicates
that it should be referred to as "list" elsewhere in the parser. The MAIN
preceding it indicates that the first call to list should prepare the stack for entry into a parser.
Other calls to list will not be preceeded by this preparatory operation. 

This preparatory operation
will use the standard token-type table which in many cases will be just fine. In this case we wish to
use a different token-type table, "MyTTT". The sequence "SWAPOUT MyTTT" indicates that we want to use
MyTTT instead.

The remainder of the definition says that a list is a leftbrace followed by a terminator, where
each of these is defined elsewhere in the structure.

The next line defines the sub-parser referred to as "terminator".
It says that a terminator is either a rightbrace, or an aname followed by a terminator, or a list followed by
a terminator.

The next two lines say that the parsers "leftbrace" and "rightbrace" which
correspond to literal matching of left-, and right-brace characters, respectively.

If the external parser "aname" parses standard HP-48 names, you can see from the
above description that { } is a list, that { ABC } is
a list, that { ABC { CDE } } is a list, etc. Note that this parser doesn't actually
produce a list. In fact, with the possible exception of aname whose definition
is external to the above code, the parser simply simply returns
.nf
    0 MyTTT string offset' token' TRUE TRUE
.fi
if the input was a list and
.nf
   0 MyTTT string offset' token' FALSE
.fi
if the first token was not a left-brace, and
.nf
  0 MyTTT string offset' token' FALSE TRUE
.fi
in any other case.

.fi
The parser corresponding to "  creates a
parser using the token that follows. The parser created doesn't start
unless the current token corresponds to that passed to the creator.
If a match is made, then the created parser returns TRUE TRUE and
drops the current token and gets the next one.

The parser corresponding to CK" is nearly identical to the above,
except that it leaves the current token right where it is. It is
useful to implement things like "super-rightbrackets" which can match
any number of left brackets.

Square brackets around a parser reference indicate that this item is optional. This is only useful in the "and" part
of a sequence. For example if our version of "list" was
.nf
   list: leftbrace [count] terminator;
.fi
where "count" referred to a parser which accepted a number, then our lists of names could optionally have
a number as their first element.

The // is used as a clause separator with the same meaning as /, except
that it modifies the manner in which the last object in the terminated
clause is evaluated. It is useful for tail-recursive calls to a parser
which always completes or fails, that is, never returns FALSE. If such a
parser is the last object in a clause, then it can be evaluated with a special mechanism
known as COLA which throws away the current pending program before evaluating the function in question.
Since in this case there is no need to change its returned value from FALSE to
FALSE TRUE, this allows for more efficient tail-recursion, when it is
possible. The // token indicates such a situation to the BNF parser so
that it can compile a more efficient parser.

The sub-program construct allows the parser to do something in addition to
simply accepting or regecting an input string. You can use all of the
normal '48 functionality to construct new objects, modify other environments,
call other parsers, or further validate the input in some other way. It is
only necessary that these sub-programs observe the input and output conditions
of generic parsers. Additional utilities provided by the parser generator for
use in these sub-programs is detailed in a separate section later in this document.

.H 2 "Tokens and Token-Type Tables"
 
A token is the smallest unit handled by a typical parser. The manner in
which a string is broken into tokens can make a significant contribution
to the overall efficiency of a parser. Moreover, different situations may
call for quite different "tokenizers". RPL token-type tables take care
of varying needs. A token-type table is any hex-string containing 256 hex digits
(or a character string containing 128 characters), one
for each ASCII character. A token-type table gives an implicit correspondence
between ASCII characters and integers in the range 0 - 15. The integer
corresponding to a character is called its type. The RPL token system
recognizes several character types as especially significant.
.nf


              0  - neutral character
              1  - normal character
              2  - digit
              3  - left delimiter
              4  - right delimiter
              5  - self delimiter
              6  - escape character
              7  - diphthong start
              8  - radix/separator 1
              9  - radix/separator 2
             10 - radix/separator 3
             11 - radix/separator 4
             12 - other (used in symbolics)
             13 - comment toggle
             14 - comment off
             15 - exponent separator
.fi

  Generally speaking, the tokenizer throws away characters until it
  finds a non-neutral character, and then returns the substring
  following consisting of characters of the same type. In this way,
  the tokenizer "chunks" the string to be parsed into individual tokens
  for processing. Exceptions to this general scheme make life more
  interesting: 
.nf

.BL
.LI
  digits are treated as ordinary characters if they follow an ordinary 
  character; 
.LI
  delimiters always form single character tokens;
.LI
  escape characters force the escape itself and the character following to acts as if it
  were ordinary; 
.LI
  a diphthong characters and the character following are
  always returned as a two character token; 
.LI
  the radix/separator characters each behave as one of two 
  other character types depending on the  current radix mark, namely
  0 and 2 (for types 8 and 9) and 5 and 2 (for types 10 and 11); 
.LI
  any characters between a comment toggle character and another comment
  toggle or comment-off character behave as neutral characters;
.LI
  an exponent separator acts like an ordinary character if it either
  begins a token or follows a digit, and behaves like a digit otherwise.
.LE
The tokenizer returns the token-type table, the string, a new offset, and
a token culled from the string. If there are no tokens to be returned from
the string, then a null token (that is, a string of length 0) is returned,
and the new offset is greater than the length of the string.
 
Note that since one of the arguments for a parser is a token, each parser
that successfully completes parsing must provide the token for the next
parser in line for evaluation. In particular, the token-type table for entry
into a given parser is determined by the previous successfully completed
parser, unless otherwise declared.

If a parser needs to change token-type tables one of two situations prevail.
In the first case, the current token has already been used but a new token
has not yet been generated (CK " has this property). In this case we can switch
to a new token-type table by replacing the current one with the new one, disposing
of the current token and getting a new one. This operation is indicated by
SWAPIN <token-type-table-name>.

On the other hand, the current token may have been generated by an incorrect
token-type table for the current situation, in which case we will need to
"put back" the current token and compute a new one using the new token-type
table. This operation is indicated by SWAPOUT <token-type-table-name>.

.H 2 "Other Provided Keywords and Utilities"

In addition to the basic syntactic constructs outlined above, the
parser generator provides access to a number of
.nf
.BL
.LI
Built-in parsers,
.LI
Built-in token-type tables, and
.LI
Parser utilities.
.LE
.fi

In each case, the corresponding keyword causes an object which is already
included in the native '48 to be compiled into the parser under
construction. The result is that the parser program so constructed will be
completely independent of the parser generator and will continue operating
even when the the parser generator is no longer present in the machine. As
a consequence, the resulting program will be most unsightly when
visited or viewed on the stack since these utilities are not associated with
any user-level names.

The names given to the built-in parsers and token-type tables will be recognized
only within the scope of the BNF structure, exclusive of the << >>-delimited
sub-programs.

The names given to the parser utilities, on the other hand, will be recognized
only outside of the BNF structure, or within the << >>-delimited sub-programs.

.H 3 "Built-in Parsers"

In the diagrams below, we will give the name (case-sensitive) of the built-in
parser followed by the stack diagram for a sucessful parse. If the parser doesn't
start the parse, the stack will be unchanged except for FALSE on top of the
stack. If it fails, no guarantess are made on the output except that it is
a valid parser output. Comments on the parser are made below these two items.
All of these parsers assume that the current token-type table is the standard
one (NormalTTT.)
.nf

Real
 ...n ttt string ofset token \(-> ...real n+1 ttt string ofset' token' TRUE TRUE
Parses a real number using the current radix/separator mode.

Complex
 ...n ttt string ofset token \(-> ...complex n+1 ttt string ofset' token' TRUE TRUE
Parses a (numeric) complex number using the current radix/separator mode.

List
 ...n ttt string ofset token \(-> ...list n+1 ttt string ofset' token' TRUE TRUE
Parses any valid list.

Prog
 ...n ttt string ofset token \(-> ...program n+1 ttt string ofset' token' TRUE TRUE
Parses a user-level RPL program.

Object
 ...n ttt string ofset token \(-> ...object n+1 ttt string ofset' token' TRUE TRUE
Parses any single user-level RPL object.

Expr
 ...n ttt string ofset token \(-> ...expression n+1 ttt string ofset' token' TRUE TRUE
Parses any valid symbolic expression.

Name
 ...n ttt string ofset token \(-> ...name n+1 ttt string ofset' token' TRUE TRUE
Parses any syntactically valid name, but does not check to see if it should be a
local name, or is the name of an extant keyword.
.fi

.H 3 "Token-type Tables"

There are three token-type tables available, NormalTTT which is the one used in
normal command-line parsing, SymbolicTTT which is used when parsing an expression,
and HexTTT which is used in tokenizing the data part of a hex string.

.H 3 "Other Utilities"

.nf
 &OB
 ...n ttt string ofset token object \(-> ...object n+1 ttt string ofset token
Appends an object to the counted set of objects below the standard parser
objects.

 &MAKEPROG
 ...n ob1..obk k ttt string ofset token \(-> ...program n+1 ttt string ofset' token' TRUE TRUE
Collects the top set of counted objects into a program object and adds the program to the counted
set of objects beyond this. Note, the resulting program does not have the
usual << >> in it, but it will still execute o.k.

 &MAKELIST
 ...n ob1..obk k ttt string ofset token \(-> ...list n+1 ttt string ofset' token' TRUE TRUE
Collects the top set of counted objects into a list object and adds the program to the counted
set of objects beyond this.

 INTtoREAL
 system_binary_integer \(-> real
Canonical conversion of a system binary integer into a real.

 REALtoINT
 real \(-> system_binary_integer
Canonical conversion of a real into a system binary integer.

 TRUE
 \(-> TRUE
Self-returning system object recognized as TRUE to the RPL system.

 FALSE
 \(-> FALSE
Self-returning system object recognized as FALSE to the RPL system.

 COMPLETED
 \(-> TRUE TRUE

 FAILED
 \(-> FALSE TRUE
