Crenshaw - Let's Build a Compiler

[barnacle]

Just to confuse things... execute takes a pointer to the start of a line in memory, but the first executable character - nominally the tokenised instruction - is always the fourth byte into the line. That's the address it calls a line with, and the statement executed on that line returns a pointer to the next line to execute (because many instructions don't change program flow, execute can precalculate the next line address).

Neil

[barnacle]

Cleaned up, I think it's easier to understand what's going on...

Code: Select all

char * do_do (char * where)
{
	char * loop_address;	// first line in the do loop
	char * cont_address;	// first line after the while
	char * while_address;	// the while line 
	
	where -= 4;
	where = find_next_line (where);
	loop_address = where;
	while_address = find_pair (where, DO);
	cont_address = find_next_line (while_address);	// first line after while
	do
	{
		where = loop_address;
		do
		{
			where = execute(where);
		}	
		while ((NULL != where) && (where != cont_address));
	}
	while (NULL == where);
	return where;
}

Having calculated the addresses of the first line of the code in the do clause, the address of the 'while' line, and the address of the following line where execution continues after the while line finishes, the inner do loop executes until either the executed line returns either a NULL (the while condition is true) or an address matching the first line after the while (the while condition is false). The outer do loop loops to reload the address of the start of the tiny basic do clause (the line after the 'do') until it sees something that isn't NULL, at which point we're done.

If we chance to come across a second 'do' - a nested 'do' - then that's simply called by the internal execute loop and it calls itself recursively - no worries until we run out of stack.

Recursion is good for headaches: guaranteed to give you one.

Neil

[Yuri]

barnacle wrote:

Recursion is good for headaches: guaranteed to give you one.

Try debugging an application with a mix of user and kernel space threads running remotely on a server where you can't stop the process or attach a debugger because it's in a production system. ;p

[barnacle]

Woohoo, it appears to be complete, for some values of complete: it executes all the instructions so far defined for it, but I still need to track the error messages and returns and clean them up somewhat.

The following instructions are acted on when entered in direct mode (i.e. at the console, without a preceeding line number):

• Let - Assign a value to a variable
• Print - Output either text, a string, or the value of a variable
• List - List the program as entered to this point
• New - Delete any entered program and start entering a new program
• Run - Execute the program in memory, starting at the lowest line number

Within the program, the following instructions are available – see later for more details:

• Let - Assign a value to a variable
• ' - A comment
• Print - Output either text, a string, or the value of a variable
• Input - Enter either a numeric value to a variable, or text to the string variable
• If/endif - Execute the lines following if the 'if' clause evaluates true; otherwise, continue after the matching 'endif'
• For/to/next - Loop zero or more times, executing all code from the line following until the matching 'next'
• Do/while - Loop at least once, executing all code from the line following until a matching 'while'
• Gosub/return - Call the numbered subroutine, which executes until a matching 'return', and then continue at the line following the gosub
• Goto - Directly jump to a specified line number
• End - Terminate program operation and return to the console

All the flow control instructions are multi-line with matching end-statements; all can include further embedded blocks within their own block. Goto makes me unhappy but it's in there for historical reasons.

I want to modify 'list' slightly to include a range, but I'm cautious of including too much and making this too big. But that done, and the error messages rationalised, it's time to start converting to 65c02 code...

Neil

[barnacle]

Ah, adding range to list was easy

Neil

[barnacle]

Also, computed gosubs, free of charge.

Code: Select all

> list
   10 for q = 1 to 3
   20   gosub q * 1000
   30   next
   40 end
 1000 print 1000
 1010 return
 2000 print 2000
 2010 return
 3000 print 3000
 3010 return
> run
1000 
2000 
3000 
> 

Neil

[barnacle]

Woohoo!

Running Gordon's mandelbrot code, slightly modified for dialect...

Code: Select all

> run
Mandelbrot - Neo Tiny Basic
Start
,,,,,,......................'''''''''~~~~~:;*&XB*%::~~''''''...........,,,,
,,,,,,,.....................'''''''''~~~::;$&B  %%$:~~~~'''''.........,,,,,
,,,,,,,,................''''''''~~~'::::;;*       $;;:~~~~''.........,,,,,,
,,,,,,,,...........'....'''''''~~~:;;**;%%&       $%*;;::::''''......,,,,,,
,,,,,............''''''''~~~~~~~::;% OX$              %&%X;:~'..........,,,
,,,...........''''''''''~~~~~~:::**%                       ;~''''.........,
,,,,...........'''~~~:::::::::;;;O                       $*::~~'''.......,,
,,,,,......''''''~~:;#**;% *;;;*%$                        OO:~~'''.......,,
,,,,..''''''''~~~~:;*$  &B  @&%&$                          X:~~''........,,
......''''''~~~~~:;;%&#        @                            :~~'''.........
.....'''~~~~:::::%&$O                                      ;:~~''..........
....''~~::;;;;*;&O                                       B*:~~''''''.......
....'                                                   $%;::~~''''........
....''~~::;;;;*;&O                                       B*:~~''''''.......
.....'''~~~~:::::%&$O                                      ;:~~''..........
......''''''~~~~~:;;%&#        @                            :~~'''.........
,,,,..''''''''~~~~:;*$  &B  @&%&$                          X:~~''........,,
,,,,,......''''''~~:;#**;% *;;;*%$                        OO:~~'''.......,,
,,,,...........'''~~~:::::::::;;;O                       $*::~~'''.......,,
,,,...........''''''''''~~~~~~:::**%                       ;~''''.........,
,,,,,............''''''''~~~~~~~::;% OX$              %&%X;:~'..........,,,
,,,,,,,,...........'....'''''''~~~:;;**;%%&       $%*;;::::''''......,,,,,,
,,,,,,,,................''''''''~~~'::::;;*       $;;:~~~~''.........,,,,,,
,,,,,,,.....................'''''''''~~~::;$&B  %%$:~~~~'''''.........,,,,,
,,,,,,......................'''''''''~~~~~:;*&XB*%::~~''''''...........,,,,
Finished

I forget just how fast modern computers are; this finishes in less than a frame of video, going through who knows how many layers of abstraction before it gets to the screen...

Neil

[drogon]

barnacle wrote:

Woohoo!

Running Gordon's mandelbrot code, slightly modified for dialect...

Yay! Well done.

-Gordon

[barnacle]

I think that at this point the C version is complete (until I find further issues with it) so here it is if anyone wants to play - it's about 1200 lines of C (including lots of {} and comments) and is deliberately written to be as easy as possible to convert to 65c02 assembly by hand.

Neo Tiny Basic.zip

(8.33 KiB) Downloaded 135 times

I think it's worth replacing all the printf with putc, puts, and something to output limited formatted numbers, again to simplify conversion to assembly, but I haven't got around to that yet.

I run it on a Linux machine, but it should build without issue on Windows. One point: there is no escape key currently implemented; you can implement a routine to tell you whether a key is waiting, and what it is, but it's a pain, so I didn't bother for now...

This differs from earlier posts in that I have removed the logic instructions from the arithmetic expression parsing.

The following instructions are acted on when entered in direct mode (i.e. at the console, without a preceding line number):
let print list new run
Within the program, the following instructions are available:
let ' print input if endif for next do while gosub return goto end

One command per line, and if/for/do have to be matched with their corresponding endif/next/while instructions but they may be nested.

Have fun...

Neil

[vbc]

barnacle wrote:

I think that at this point the C version is complete (until I find further issues with it) so here it is if anyone wants to play

Out of curiosity I compiled it for C64 with vbcc. With a small for-loop it was about twice as fast as Commodore-Basic (which of course uses floating point).

As a hint, you probably did not mean to write

Code: Select all

char tokens[][LAST_KW] =

I replaced that by:

Code: Select all

const char *tokens[] =

[barnacle]

Thanks, vbc... for curiosity, what size is the 6502 compiled version?

Neil

[vbc]

barnacle wrote:

Thanks, vbc... for curiosity, what size is the 6502 compiled version?

The code for your file was slightly under 7K plus another several KB for printf, buffered I/O etc. That was without any further modifications and not optimized for size. Also, I think it includes a few functions that are not actually called. So it could be reduced quite a bit, I presume.

[barnacle]

Thanks, that gives me something to aim for in the hand-coded version. It's about 26k in the 64 bit x86 version, but again, I expect there's a lot of unused library in there.

Neil