Expression Evaluation in Z80 Assembly

Tuesday, 24th February 2009

The expression evaluators I've written in the past have been memory hungry and complex. Reading the BBC BASIC ROM user's guide introduced me to the concept of expression evaluation using top-down analysis, which only uses a small amount of constant RAM and the stack.

I took some time out over the weekend to write an expression evaluator in Z80 assembly using this technique. It can take an expression in the form of a NUL-terminated string, like this:

.db "(-8>>2)+ceil(pi())+200E-2**sqrt(abs((~(2&4)>>>(30^sin(rad(90))))-(10>?1)))",0

and produce a single answer (or an error!) in the form of a floating-point number. The source code and some notes can be downloaded here.

I initially wrote a simple evaluator using 32-bit integers. I supported the operations the 8-bit Z80 could do relatively easily (addition, subtraction, shifts and logical operations) and got as far as 32-bit multiplication before deciding to use BBC BASIC's floating-point maths package instead. The downside is that BBC BASIC has to be installed (the program searches for the application and calls its FPP routine).

I'm not sure if the technique used is obvious (I'd never thought of it) but it works well enough and the Z80 code should be easy to follow - someone may find it useful. smile.gif

Nibbles and Logo

Thursday, 19th February 2009

Work on BBC BASIC has slowed down quite a bit, with only minor features being added. A *FONT command lets you output large or font sized text to the graphics cursor position regardless of the current MODE:

Mixed-Fonts.gif
10 MODE 3
20 VDU 5
30 MOVE 0,255 : PRINT "Small"
40 *FONT LARGE
50 MOVE 0,227 : PRINT "Large"
60 VDU 4
70 PRINT TAB(0,3) "Small (VDU 4)"

Another new command is the dangerous *GBUF that can - when used correctly - let you switch the location of the graphics buffer. You can simulate greyscale by quickly flickering between two different images on the LCD, which is where this command may come in use.

2009.02.11.01.gif

Snake/Nibbles is a fun game and an easy one to write, so here's a simple implementation that features variable speeds and mazes. The game runs quickly on a 6MHz TI-83+, which I'm happy with. And yes, I know I'm terrible at it. wink.gif

One thing I've always been pretty bad at is writing language parsers resulting in poor performance and bugs. I've started writing a primitive Logo interpreter in C# to try and improve my skills in this area. So far it supports a handful of the basic language features and statements:

- print [Hello World]
Hello World
- make "animals [cat dog sheep] show :animals
[cat dog sheep]
- make "animals lput "goat :animals show :animals
[cat dog sheep goat]
- print last :animals
goat
- repeat 2 [ print "A repeat 2 [ print "B ] ]
A
B
B
A
B
B
- show fput [1 2 3] [4 5 6]
[[1 2 3] 4 5 6]
- [10 9 8]
Not sure what to do with [10 9 8]

(No, no turtle graphics yet wink.gif). There's no support for infix operators yet. The BBC BASIC ROM manual describes the top-down parsing method it uses to evaluate expressions so I'm going to attempt to reimplement that.

One issue I've already run into are the parenthesis rules: for example the sum function outside parentheses only allows two arguments, but inside parentheses works until the closing parenthesis:

- print (sum 4 5)
9
- print (sum 4 5 6)
15
- print sum 4 5
9
- print sum 4 5 6
9
Not sure what to do with 6

I'm not sure whether a "this statement was preceded by an opening parenthesis" flag would be sufficient.

Extending BBC BASIC

Sunday, 1st February 2009

BBC BASIC may have originated with the 8-bit home computer era, but it's still being updated and its most up-to-date incarnation - BBC BASIC for Windows - has a wealth of features that are unavailable on the Z80 version.

The BBC BASIC graphics API is primarily accessed via the multi-purpose PLOT statement. PLOT is followed by three arguments - the type of graphics operation being carried out followed by an X and a Y coordinate. For example, to draw a line between (20,30) and (100,120) you could do this:

PLOT 4,20,30   : REM Move graphics cursor to (20,30)
PLOT 5,100,120 : REM Draw a line to (100,120)

This results in needing to remember a lot of different plot codes (there is a logic to how they are formed but I still need to consult a list of codes from time to time). All implementations of BBC BASIC feature two helper statements to aid the user:

  • MOVE x,y (equivalent to PLOT 4,x,y)
  • DRAW x,y (equivalent to PLOT 5,x,y)

More recent versions, such as BBC BASIC for Windows, also implements the following helper statements, amongst others:

  • CIRCLE x,y,r (equivalent to MOVE x,y : PLOT 145,r,0)
  • ELLIPSE x,y,w,h (equivalent to MOVE x,y : PLOT 0,w,0 : PLOT 193,0,h)
  • FILL x,y (equivalent to PLOT 133,x,y)
  • RECTANGLE FILL x,y,w,h (equivalent to MOVE x,y : PLOT 97,w,h)

This is all very well, but the BBC BASIC (Z80) interpreter is a sealed box as far as I am concerned. I can ask it to perform tasks for me ("evaluate this expression") and it can ask me to perform tasks for it ("output this character to the display") but I can't modify its behaviour.

BASIC ROM User Guide for the BBC Microcomputer and Acorn Electron coverOr, so I thought - until I read through the copy of BASIC ROM User Guide that a friend had rescued and sent to me. It has a section on adding statements, which it achieves by using a clever - but simple - trick.

When BBC BASIC encounters a statement it doesn't recognise it triggers the Mistake error. On the BBC Micro the error handler is vectored, meaning that it loads the address of the error handling routine from RAM first instead of jumping to a fixed address. This allows the user to override the normal error handler, detect the Mistake condition and try and parse the erroneous statement themselves. If they can't handle the statement either control is passed back to BBC BASIC's usual error handler, otherwise the error condition is cleared and execution continues as normal.

BBC BASIC (Z80) follows the same procedure but with one major difference - the error handler routine is not vectored. Unfortunately, the only practical workaround I can think of is to patch the interpreter's error handler routine directly. Richard Russell somehow managed to add support for additional commands to the Z88 version via a patch that runs from RAM, but I haven't been able to work out how he managed to do that yet.

Demonstration of ELLIPSE FILLThe first series of additional statements I added were the graphics helper statements listed above, WAIT (which pauses execution for a certain number of centi-seconds) and SWAP which exchanges the contents of two variables. These are all relatively simple statements to implement as they do not affect the state of BBC BASIC in any other way; they perform a single, simple task then exit.

One of the more useful additions to more recent versions of BBC BASIC is the WHILE...ENDWHILE loop structure. A limitation of BBC BASIC (Z80)'s statement blocks is that their contents must be executed at least once, hence IF statements must fit on one line, multi-line procedures or functions should be placed at the end of the file after an END statement and REPEAT...UNTIL loops - where the looping conditional is at the end of the block, rather than the start - are provided. If a WHILE condition evaluates to FALSE, control needs to resume at the matching ENDWHILE. This is an interesting technical challenge, as it needs to handle nested WHILE...ENDWHILE stataments when searching through the code to find the terminating ENDWHILE, but appears to work pretty well now.

Another useful recent addition is EXIT (in three variations - EXIT FOR, EXIT REPEAT and EXIT WHILE) which breaks out of a loop structure. This has the same technical challenges as the WHILE...ENDWHILE loop structure (searching for the matching loop terminator) with the additional difficulty of unwinding the stack to the correct position.

By combining WHILE loops and EXIT WHILE you can simulate multi-line IF statement blocks, so

IF <condition> THEN <statements>

becomes

WHILE <condition>
  <statements>
EXIT WHILE:ENDWHILE

These additions are not without their downsides. Most of the statements supported natively by BBC BASIC (Z80) are represented by single-byte tokens, whereas these extensions are stored as ASCII text. This makes them take up more room in the source file and slower to execute (searching for and handling strings is a much more complex operation than searching for bytes). Using them makes your programs incompatible with other versions of BBC BASIC (Z80). I personally feel that these disadvantages are far outweighed by the advantage of easier to read code, however.

To round the entry off, have a fractal. smile.gif

FirstJanuary 2009March 2009Last RSSSearchBrowse by dateIndexTags