﻿==============================================================================
Expression Parser Using Top-Down Analysis - Ben Ryves 2009
==============================================================================

This sample program implements a simple expression parser using top-down
analysis. Feel free to use it in your own programs; it is possibly of limited
usefulness as it relies on BBC BASIC being installed to provide its floating-
point arithmetic library. It has not been extensively tested, but the concept
is sound.

The evaluator uses a very small amount of constant memory for itself. All
dynamic allocation happens directly on the hardware stack.

See the BBC BASIC documentation for further information about the FPP routine,
PRINT statement and format of the five-byte floating point variables.

There are three main routines of interest to the user; these are documented
below.

------------------------------------------------------------------------------
Initialise
------------------------------------------------------------------------------

This searches for the BBCBasic application. If it found it, it returns with
the carry flag reset; if it was not found, the carry flag is set.

------------------------------------------------------------------------------
Evaluate
------------------------------------------------------------------------------

This routine evaluates the expression in the NUL-terminated string pointed to
by IX. If the operation was successful, the carry flag is reset and the
Accumulator variable (a five byte floating-point number) contains the result.
If the operation failed for any reason, the carry flag is set and A contains
the error code. (These are mostly the same as the BBC BASIC error codes for
convenience).

This routine destroys all registers apart from I and IY. Interrupts are
disabled.

------------------------------------------------------------------------------
ToString
------------------------------------------------------------------------------

This routine converts the accumulator variable into a NUL-terminated string.
DE should point to the place to store the output string. The two byte variable
OutputFormat determines the string's format. This is the two middle bytes that
would form BBC BASIC's @% variable; the least significant byte is the number
of digits to display, the most significant is the format - 00 for general, 01
for exponential ("scientific") and 02 for fixed ("engineering").

This routine destroys all registers apart from I and IY. Interrupts are
disabled.

==============================================================================
Operators
==============================================================================

The following operators are available, grouped in order of precedence from
highest to lowest.

             .----------------.-----.--------------------------.
             | Unary          | +   | Unary addition           |
             |                | -   | Unary subtraction        |
             |                | !   | Conditional NOT          |
             |                | ~   | Logical NOT              |
             |----------------|-----|--------------------------|
             | Power          | **  | Power                    |
             |----------------|-----|--------------------------|
             | Multiplicative | *   | Multiplication           |
             |                | /   | Floating-point division  |
             |                | \   | Integer division         |
             |                | %   | Modulo                   |
             |----------------|-----|--------------------------|
             | Additive       | +   | Addition                 |
             |                | -   | Subtraction              |
             |----------------|-----|--------------------------|
             | Shift          | <<  | Shift left               |
             |                | >>  | Signed shift right       |
             |                | >>> | Unsigned shift right     |
             |----------------|-----|--------------------------|
             | Relational     | <   | Less than                |
             |                | >   | Greater than             |
             |                | <=  | Less than or equal to    |
             |                | >=  | Greater than or equal to |
             |                | <?  | Minimum                  |
             |                | >?  | Maximum                  |
             |----------------|-----|--------------------------|
             | Equality       | ==  | Equality                 |
             |                | !=  | Inequality               |
             |----------------|-----|--------------------------|
             | LogicalAnd     | &   | Logical AND              |
             |----------------|-----|--------------------------|
             | LogicalXor     | ^   | Logical XOR              |
             |----------------|-----|--------------------------|
             | LogicalOr      | |   | Logical OR               |
             '----------------'-----'--------------------------'

==============================================================================
Functions
==============================================================================

Functions have the same level of precedence as literals and unary operators.

    .----------.---------------------------------------------------------.
    | abs(n)   | Returns the absolute value of n (|n|)                   |
    | sgn(n)   | Returns the sign of n (-1 if n<0, +1 if n>0, 0 if n==0) |
    |----------|---------------------------------------------------------|
    | floor(n) | Rounds n towards negative infinity                      |
    | int(n)   | Rounds n towards zero (truncation)                      |
    | ceil(n)  | Rounds n towards positive infinity                      |
    |----------|---------------------------------------------------------|
    | sin(n)   | Returns the sine of n (radians)                         |
    | cos(n)   | Returns the cosine of n (radians)                       |
    | tan(n)   | Returns the tangent of n (radians)                      |
    |----------|---------------------------------------------------------|
    | asin(n)  | Returns the arcsine of n in radians                     |
    | acos(n)  | Returns the arccos of n in radians                      |
    | atan(n)  | Returns the arctangent of n in radians                  |
    |----------|---------------------------------------------------------|
    | deg(n)   | Converts n from radians to degrees                      |
    | rad(n)   | Converts n from degrees to radians                      |
    |----------|---------------------------------------------------------|
    | pi()     | Returns π (3.141...)                                    |
    |----------|---------------------------------------------------------|
    | sqrt(n)  | Returns the square root of n                            |
    |----------|---------------------------------------------------------|
    | exp(n)   | Returns e raised to the power of n                      |
    |----------|---------------------------------------------------------|
    | ln(n)    | Returns the natural logarithm of n                      |
    | log(n)   | Returns the base-10 logarithm of n                      |
    '----------'---------------------------------------------------------'

==============================================================================
Room for Improvement
==============================================================================

There's certainly room for improvement with the parser. Here are some things
that I think could be worked on.

 * Stack overflow protection. Before pushing operands to the stack or
   recursively calling the evaluator it would seem sensible to check the
   current level of the stack and trigger a stack overflow exception if
   necessary. This version does not provide that protection, so a suitably
   lengthy expression may overflow the stack, corrupt data and cause a crash.
 * Support for the conditional operators && and ||. This is easy enough to do,
   the challenge would come from lazy evaluation.
 * Support for the ternary conditional operator ?:.
 * Improved function name searching (this is currently a linear search through
   every possible function name).
 * Numeric literals in binary, octal and hexadecimal.

The biggest improvement would be to add support for named variables (allocated
on a heap).