Has anyone written a guide on creating BASIC?

[cbmeeks]

IMHO, one of the coolest things about creating your own computer is creating your own BASIC. The "Woz" way.

I've studied the greats like EhBasic, Microsoft Basic, etc. but those are finished products with years of development and thousands of lines of optimized code.

What I'd like to find is a primer on how to start creating your own BASIC. Preferably for the 6502 but high-level lessons could still be useful.

Even if the primer wasn't the most efficient way to design a BASIC interpreter, it could be a great stepping stone for a better product down the road.

Thanks!

[RichTW]

Not a primer, but there's a very detailed disassembly of BBC BASIC (version 4) here.

In my view, BBC BASIC was the best BASIC implementation of its time, offering named PROCedures as an improved GOSUB, REPEAT...UNTIL, variable names of any length, memory indirection operators, and even a built-in 6502 assembler!

[BigEd]

Tiny Basic could be interesting too: it's a nested interpreter, which lends compactness and portability.
https://github.com/jefftranter/6502/tre ... /tinybasic

[whartung]

Obviously there's optimizations and what not.

But, really, a BASIC is just work. Cramming one in to 8K of RAM can get tricky, but from a language perspective, your rote tokenized, interpreter is pretty, well, basic.

The parser is not difficult, the runtime it not especially sophisticated. I've written interpreters and compilers, but not a basic per se.

A singular magic trick that makes helps implementing them is the Shunting Yard algorithm for expression evaluation.

Most compilers and what not get the advantage of being able to rewrite expressions to suit them for execution. Most tokenized basics do not. For example, most don't rewrite the expression in to a stack based RPN runtime thats trivial to evaluate, because the don't have the room to do it and want to keep the original structure of the expression within the tokenized form.

The Shunting Yard algorithm is good at evaluating those kind of "infix" expressions in place.

Getting expressions parsed is the "Hard Part" of most languages. Get that solved, and the rest is just rote work, nothing fancy.

Floating point is the next "hard part".

Feel free to ask specific questions, if you like.

[cbmeeks]

Thanks for the comments.

I've thought about doing a basic (no pun) interpreter in JavaScript or Java. Mainly as a high-level system. Then, convert to 6502 ASM when the time comes.

[RichTW]

Do 6502 BASIC implementations tend to use shunting yard for expression evaluation though? BBC BASIC does something more akin to a recursive decent parser, hardcoding the expected syntax and precedence in code.

http://8bs.com/basic/basic4-9d3b.htm#9D3B

[jds]

I know that Lee Davison (EhBasic) wrote a commented disassembly of the Commodore 64 including the basic, so he probably got quite a few ideas from looking at other basics. You can find it here https://github.com/Project-64/reloaded/ ... /C64LD11.S.

There is also the Apple /// Business Basic source code available here http://www.apple3.org/iiisourcecode.html.

Possibly the most complete description of a Basic is the Atari Basic Sourcebook, written by the authors of Atari Basic. Physical copies can still be found and there are PDF's on the internet. Atari basic is notable in that it is very slow, firstly because the floating point is all stored in BCD so the floating point routines are slow, and all numbers are floating point, including line numbers, and loops and goto's scan the entire listing for the required line (and line numbers are stored in BCD). But it's a really useful book in understanding what is required for building a basic.

I think that the hardest part of building your own basic would be managing the memory.

[GARTHWILSON]

from my links page (where there are hundreds of 6502 links):
Create your own version of MS BASIC for 6502

[unclouded]

whartung wrote:

Getting expressions parsed is the "Hard Part" of most languages. Get that solved, and the rest is just rote work, nothing fancy.

That's inspirational, thank you. I hope to write a compiler one day and this is the sort of comment from experience that suggests it's achievable.

[drogon]

No guide here, sorry, but in recent years I did write a BASIC - mostly to satisfy my own needs, but it was also turned into a commercial product... (Yay, I sold a BASIC interpreter in the new millennium - why am I not a billionaire like Gates ...)

However it's written in C. Plain old ANSI C. It uses shunting yard and an internal RPN evaluator. The parsting is all more or less done the hard way (no lex, etc.) and the trickiest thing to parse is the unary minus. It tokenises the input (which could be considered a one-pass compiler), then the run command is effectively an interpreter for this hybrid tokenised code. Much like a lot of the 70/80's microprocessor BASICs of the time. The list command is a strict de-tokeniser, however it features a built-in text editor for line-numberless coding.

I don't have a compiler sort of CS background, but have found myself writing lots of little interpreter/scripty type of languages over the years to support various projects I was working on. This is the biggest so-far...

If you have a Raspberry Pi running Raspbian, then sudo apt-get install rtb will get it for you. (although an older version)

My aim is to re-write it (porting would be too grand a task!) for the 6502 once I have my own SBC thingy up and running. I'm actually looking at writing it in itself which will require some changes (e.g. byte accesses to strings, peek/poke, etc. which it doesn't has as it was intended to run under Linux) however it might be fun - or a nightmare, who knows.

For the curious, an example program can be found here: https://unicorn.drogon.net/snake.rtb (Line numbers are optional) A slightly familiar thing can also be found here: https://unicorn.drogon.net/wumpus.rtb

-Gordon

[Dr Jefyll]

drogon wrote:

the trickiest thing to parse is the unary minus

Glad I'm not the only one who had trouble with that! Back in the 20th century I wrote an assembler for Intel's MCS-48 family of microprocessors and microcontrollers (think: 8048 keyboard controller). Although the assembler was written in Forth it accepted standard Intel source code -- ie, forward notation, not RPN. I wrote my own parser for expressions, and it all worked out according to expectations... except for the unary minus. The order of precedence was accounted for, and nested parentheses and so on -- all that good stuff was taken care of. But my assembler couldn't abide a simple expression like -1 on the grounds that it was incomplete. I set the problem aside and moved on to something else. As a workaround my MCS48 source code would have to present that expression as 0 - 1.

-- Jeff

[Chromatix]

I think a good practice when writing a parser is to work out the eBNF grammar of whatever you're trying to parse - even if you then don't use anything like 'lex' and 'yacc' on it, but hand-write the parser. It's simply a good way to tease out the ambiguities, such as the unary-minus.

Thinking along those lines, you soon realise that the unary-minus occurs when an infix operator is inappropriate (because you've just seen one, or it's the beginning of the expression). This is the same context in which open-brackets are legal. Conversely, the subtraction operator occurs only when an infix operator is expected - the same context in which close-brackets are legal (if there is a matching open-bracket). If you can distinguish those contexts when you encounter the ASCII hyphen character, you can emit distinct "subtract" and "negate" operator tokens.

[mvk]

Dr Jefyll wrote:

drogon wrote:

the trickiest thing to parse is the unary minus

Glad I'm not the only one who had trouble with that!

TinyBASIC hacks in the unary minus quite nicely.
You'll only notice it is a little trick when things such as A*-1 and A/-1 won't parse.
You have to type A/(-1), but in reality you don't see that needed in programs.

If you want a quick result in getting a BASIC: port TinyBASIC and skip the intermediate interpreter.
It should really fit in 2K. It took me about a week to port to the Gigatron this summer.

From there, BASIC is never finished. You need POKE/PEEK/USR() etc. Then RND().
You can add FOR-TO-NEXT, perhaps STEP as well, arrays, SAVE/LOAD, perhaps strings.
Colon (:) sounds too-trivial and not-really-needed, but it eliminates many GOTOs
and reduces the craving for ELSE. You can also get pretty far in "faking" strings if you have arrays.

Having TinyBASIC as a start it will always be slow however, and if you plan for speed: tokenise.
TinyBASIC spends most of its time parsing integers and searching for line numbers.
Making a tokenised version requires much more planning ahead, especially if you want LIST...
If you want floating point, all bets are off.. Bill Gates also didn't do that part for his BASIC...

Links I found useful:

https://en.wikipedia.org/wiki/Tiny_BASIC
Wikipedia article

http://www.ittybittycomputers.com/IttyB ... esign.html
DESIGN NOTES FOR TINY BASIC (Dennis Allison et al.)

http://www.ittybittycomputers.com/IttyBitty/TinyBasic/
Tom Pittman's implementation

http://p112.sourceforge.net/tbp112.html
P112 Tiny Basic User's Guide (V1.0, 18 FEB 1999)

http://www.bitsavers.org/pdf/interfaceA ... 92-108.pdf
Dr. Wang's Palo Alto Tiny Basic (Roger Rauskolb)

https://www.applefritter.com/node/2859
Apple 1 BASIC

[barrym95838]

Dr Jefyll wrote:

As a workaround my MCS48 source code would have to present that expression as 0 - 1.

-- Jeff

Yeah, VTL02 has to do that as well. A unary minus doesn't trigger an error though, because VTL02 doesn't know what "error" means (or what a negative number means, FTM). It simply treats the unary minus as a reference to the (unsigned integer) variable by the name of "-" and proceeds.

[BigEd]

(Great links mvk, thanks - would love to hear more about the gigatron work, maybe in Introduce Yourself?)