BASIC Interpreter¶

Years ago, I showed how to write an Interpreter for a dialect of Lisp. Some readers appreciated it, and some asked about an interpreter for a language that isn't just a bunch of parentheses. In 2014 I saw a celebration of the 50th anniversary of the 1964 Dartmouth BASIC interpreter, and thought that I could show how to implement such an interpreter. I never quite finished in 2014, but now it is 2017, I rediscovered this unfinished file, and completed it. For those of you unfamiliar with BASIC, here is a sample program:

Of course I don't have to build everything from scratch in assembly language, and I don't have to worry about every byte of storage, like Kemeny, Gates, and Woz did, so my job is much easier. The interpreter consists of three phases:

• Tokenization: breaking a text into a list of tokens, for example: "10 READ N" becomes ['10', 'READ', 'N'].
• Parsing: building a representation from the tokens: Stmt(num=10, typ='READ', args=['N']).
• Execution: follow the flow of the program and do what each statement says; in this case the READ statement

has the effect of an assignment: variables['N'] = data.popleft().

Tokenization¶

One way to turn a line of text into a list of tokens is with the findall method of a regular expression that defines all the legal tokens:

The only complicated part is the syntax for numbers: optional digits followed by an optional decimal point, some digits, and optionally a power of 10 marked by "E" and followed by an (optional) minus sign and some digits. Example usage of tokenize:

That looks good. Note that my tokens are just strings; it will be the parser's job, not the tokenizer's, to recognize that '2' is a number and 'X' is the name of a variable. (In some interpreters, the tokenizer makes distinctions like these.)

There's one important complication: spaces don't matter in BASIC programs, so the following should all be equivalent:

10 GOTO 99
10GOTO99
10 GO TO 99

The problem is that tokenize gets the last one wrong:

My first thought was to remove all white space from the input. That would work for this example, but it would change the token "HELLO WORLD" to "HELLOWORLD", which is wrong. To remove spaces everywhere except between double quotes, I can tokenize the line and join the tokens back together. Then I can re-tokenize to get the final list of tokens; I do that in my new function below called tokenizer.

Once I have a list of tokens, I access them through this interface:

• peek(): returns the next token in tokens (without changing tokens), or None if there are no more tokens.
• pop(): removes and returns the next token.
• pop(string): removes and returns the next token if it is equal to the string; else return None and leave tokens unchanged.
• pop(predicate): remove and return the next token if predicate(token) is true; else return None, leave tokens alone.

(Note: if I expected program lines to contain many tokens, I would use a deque instead of a list of tokens.)

We can test tokenizer and the related functions:

Parsing: Grammar of Statements¶

Parsing is the process of transforming the text of a program into an internal representation, which can then be executed. For BASIC, the representation will be an ordered list of statements, and we'll need various data types to represent the parts of the statements. I'll start by showing the grammar of BASIC statements, as seen on pages 56-57 of the manual (see also pages 26-30 for a simpler introduction). A statement starts with a line number, and then can be one of the following 15 types of statements, each type introduced by a distinct keyword:

• LET <variable> = <expression>
• READ <list of variable>
• DATA <list of number>
• PRINT <sequence of label and expression>
• GOTO <linenumber>
• IF <expression> <relational> <expression> THEN <linenumber>
• FOR <varname> = <expression> TO <expression> [STEP <expression>]
• NEXT <varname>
• END
• STOP
• DEF <funcname>(<varname>) = <expression>
• GOSUB <linenumber>
• RETURN
• DIM <list of variable>
• REM <any string of characters whatsoever>

The notation <variable> means any variable and <list of variable> means zero or more variables, separated by commas. [STEP <expression>] means that the literal string "STEP" followed by an expression is optional.

Rather than use one of the many language parsing frameworks, I will show how to build a parser from scratch. First I'll translate the grammar above into Python. Not character-for-character (because it would take a lot of work to get Python to understand how to handle those characters), but almost word-for-word (because I can envision a straightforward way to get Python to handle the following format):

Parsing Strategy¶

The grammar of BASIC is designed so that at every point, the next token tells us unambiguously how to parse. For example, the first token after the line number defines the type of statement; also, in an expression we know that all three-letter names are functions while all 1-letter names are variables. So in writing the various grammatical category functions, a common pattern is to either peek() at the next token or try a pop(constraint), and from that decide what to parse next, and never have to back up or undo a pop(). Here is my strategy for parsing statements:

• The grammatical categories, like variable and expression (and also statement), will be defined as functions

(with no argument) that pop tokens from the global variable tokens, and return a data object. For example, calling linenumber() will pop a token, convert it to an int, and return that.

• Consider parsing the statement "20 LET X = X + 1".

• First tokenize to get: tokens = ['20', 'LET', 'X', '=', 'X', '+', '1'].

• Then call statement() (defined below).

  • statement first calls linenumber(), getting back the integer 20 (and removing '20' from tokens).

  • Then it calls pop() to get 'LET' (and removing 'LET' from tokens).

  • Then it indexes into the grammar with 'LET', retrieving the grammar rule [variable, '=', expression].

  • Then it processes the 3 constituents of the grammar rule:

    • First, call variable(), which removes and returns 'X'.
    • Second, call pop('='), which removes '=' from tokens, and discard it.
    • Third, call expression(), which returns a representation of X + 1; let's write that as Opcall('X', '+', 1.0).

  • Finally, statement assembles the pieces and returns Stmt(num=20, typ='LET', args=['X', Opcall('X', '+', 1.0)]).

• If anything goes wrong, call fail("error message"), which raises an error.

Here is the definition of statement:

Some of the grammatical categories, like expression, are complex. But many of the categories are easy one-liners:

Here are the predicates that distinguish different types of tokens:

Note that varname means an unsubscripted variable name (a letter by itself, like X, or followed by a digit, like X3), and that variable is a varname optionally followed by index expressions in parentheses, like A(I) or M(2*I, 3):

list_of is tricky because it works at two different times. When I write list_of(number) in the grammar, this returns an object of class list_of. When this object is called (just as other grammatical categories like variable are called), the effect is that it will parse a list of number. That list can be empty (if there are no more tokens on the line), or can be a single number, or can be several numbers separated by comma tokens. I could have defined list_of as a function that returns a function, but I thought that it would be clearer to define it as a class, so I can clearly separate what happens at the two different times: first the __init__ method determines what category to parse, and later the __call__ method does the actual parsing.

Parsing: Top Level parse, and Handling Errors¶

Most of the parsing action happens inside the function statement(), but at the very top level, parse(program) takes a program text (that is, a string), and parses each line by calling parse_line, sorting the resulting list of lines by line number. If we didn't have to handle errors, this would be simple:

To handle syntactic errors, I add to parse_line a try/except that catches exceptions raised by calls to fail. I acknowledge the interpreter isn't very thorough about handling all errors, and the error messages could be more helpful.

Parsing: Building A Representation of the Program¶

A program is represented by various data structures: a list of statements, where each statement contains various components: subscripted variable references, user-defined functions, function calls, operation calls, variable names, numbers, and labels. Here I define these data structures with namedtuples:

The first four namedtuples should be self-explanatory. The next one, ForState, is used to represent the state of a FOR loop variable while the program is running, but does not appear in the static representation of the program. Function is used to represent the definition of a user defined function. When the user writes "DEF FNC(X) = X ^ 3", we create an object with Function(parm='X', body=Opcall('X', '^', 3)), and whenever the program calls, say, FNC(2) in an expression, the call returns 8, and also assigns 2 to the global variable X (whereas in modern languages, it would temporarily bind a new local variable named X). BASIC has no local variables. Note the technique of making Function be a subclass of a namedtuple; we are then free to add the __call__ method to the subclass.

Parsing: Grammar of PRINT Statements¶

On page 26 of the manual, it appears that the grammar rule for PRINT should be [list_of(expression)]. But in section 3.1, More about PRINT, some complications are introduced:

• Labels (strings enclosed in double quotes) are allowed, as well as expressions.
• The "," is not a separator. A line can end with ",".
• Optionally, ";" can be used instead of ",".
• Optionally, the "," or ";" can be omitted—we can have a label immediately followed by an expression.

The effect of a comma is to advance the output to the next column that is a multiple of 15 (and to a new line if this goes past column 100). The effect of a semicolon is similar, but works in multiples of 3, not 15. (Note that column numbering starts at 0, not 1.) Normally, at the end of a PRINT statement we advance to a new line, but this is not done if the statement ends in "," or ";". Here are some examples:

• 10 PRINT X, Y

Prints the value of X in column 0 and Y in column 15. Advances to new line.

• 20 PRINT "X =", X

Prints the string "X =" in column 0 and the value of X in column 15. Advances to new line.

• 30 PRINT "X = " X

Prints the string "X =" in column 0 and the value of X immediately after. Advances to new line.

• 40 PRINT X; Y,

Prints the value of X in column 0, and the value of Y in the column that is the first available multiple of 3 after that. For example, if X is '0', then print Y in column 3, but if X is '12345', then we've gone past column 3, so print Y in column 6. Then, because the statement ends in a comma, advance to the next column that is a multiple of 15, but not to a new line.

That explanation was long, but the implementation is short (at least for the parsing part; later we will see the execution part):

Parsing: Grammar of Expressions¶

Now for the single most complicated part of the grammar: the expression. The biggest complication is operator precedence: the string "A + B * X + C" should be parsed as if it were "A + (B * X) + C", and not as "(A + B) * (X + C)," because multiplication binds more tightly than addition. There are many schemes for parsing expressions, I'll use an approach attributed to Keith Clarke.

Like all our grammatical categories, calling expression() pops off some tokens and returns a data object. The first thing it does is parse one of five types of simple "primary" expressions: a number like 1.23; a possibly-subscripted variable like X or A(I); a function call like SIN(X); a unary negation like -X; or a parenthesied expression like (X + 1).

Next, expression looks for infix operators. To parse 'X + 1' as an expression, first primary() would parse 'X', then it would pop off the '+' operator, then a recursive call to expression() would parse 1, and the results can then be combined into an Opcall('X', '+', 1). If there are multiple infix operators, they can all be handled, as in 'X+1+Y+2', which gets parsed as Opcall(Opcall(Opcall('X', '+', 1), '+', 'Y'), '+', 2).

When there are multiple infix operators of different precedence, as in "A + B * X + C", the trick is to know which operators are parsed by the top-level call to expression, and which by recursive calls. When we first call expression(), the optional parameter prec gets the default value, 1, which is the precedence of addition and subtraction. When expression makes a recursive call, it passes the precedence of the current operator, and we only parse off operator/expression pairs at an equal or higher precedence. So, in parsing "A + B * X + C", when we pop off the '*' operator (which has precedence 2), we then recursively call expression(2), which parses off an expression containing operators of precedence 2 or higher, which means the recursive call will parse X, but it won't pop off the '+', because that is at a lower precedence. So we correctly get the structure "(A + ((B * X) + C)".

The function associativity ensures that the operator '^' is right associative, meaning 10^2^3 = (10^(2^3)), whereas the other operators are left associative, so 10-2-3 = ((10-2)-3).

Here is the implementation of expression:

Parsing: The Complete Parser in Action¶

I've now written all the grammatical categories, so I can now safely instantiate the global variable grammar by calling Grammar(), and parse a program:

Here are some more tests:

Execution¶

Now that we can parse programs, we're ready to execute them. I'll first define run to parse and execute a program:

The function execute(stmts) first calls preprocess(stmts) to handle declarations: DATA and DEF statements that are processed one time only, before the program runs, regardless of their line numbers. (DIM statements are also declarations, but I decided that all lists/tables can have any number of elements, so I can ignore DIM declarations.) execute keeps track of the state of the program, partially in three globals:

• variables: A mapping of the values of all BASIC variables (both subscripted and unsubscripted).
  For example, {'P1': 3.14, ('M', (1, 1)): 42.0} says that the value of P1 is 3.14 and M(1, 1) is 42.0.
• functions: A mapping of the values of all BASIC functions (both built-in and user-defined).
  For example, {'FNC': Function('X', Opcall('X', '^', 3)), 'SIN': math.sin}
• column: The column that PRINT will print in next.

And also with these local variables:

• data: a queue of all the numbers in DATA statements.
• pc: program counter; the index into the list of statements.
• ret: the index where a RETURN statement will return to.
• fors: a map of {varname: ForState(...)} which gives the state of each FOR loop variable.
• goto: a mapping of {linenumber: index}, for example {10: 0, 20: 1} for a program with two line numbers, 10 and 20.

Running the program means executing the statement that the program counter (pc) is currently pointing at, repeatedly, until we hit an END or STOP statement (or a READ statement when there is no more data). The variable pc is initialized to 0 (the index of the first statement in the program) and is then incremented by 1 each cycle to go to the following statement; but a branching statement (GOTO, IF, GOSUB, or RETURN) can change the pc to something other than the following statement. Note that branching statements refer to line numbers, but the pc refers to the index number within the list of statements. The variable goto maps from line numbers to index numbers. In BASIC there is no notion of a stack, neither for variables nor return addresses. If I do a GOSUB to a subroutine that itself does a GOSUB, then the original return address is lost, because BASIC has only one return address register (which we call ret).

The main body of execute checks the statement type, and takes appropriate action. All the statement types are straightforward, except for FOR and NEXT, which are explained a bit later.

Here are the functions referenced by execute:

Execution: FOR/NEXT Statements¶

I have to admit I don't completely understand FOR loops. My questions include:

• Are the END and STEP expressions evaluated once when we first enter the FOR loop, or each time through the loop?
• After executing "FOR V = 1 TO 10", is the value of V equal to 10 or 11? (Answer: the manual says 10.)
• Does "FOR V = 0 TO -2" execute zero times? Or do all loops execute at least once, with the termination test done by the NEXT?
• What if control branches into the middle of a loop and hits the NEXT statement, without ever executing the corresponding FOR statement?
• What if control branches into the middle of a loop and hits the NEXT statement, without ever executing the corresponding FOR statement, but we have previously

executed a FOR statement of a different loop that happens to use the same variable name?

I chose a solution that is easy to implement, and correctly runs all the examples in the manual, but I'm not certain that my solution is true to the original intent. Consider this program:

10 PRINT "TABLE OF SQUARES"
20 LET N = 10
30 FOR V = 1 to N STEP N/5
40   PRINT V, V * V
50 NEXT V
60 END

• When control hits the "FOR V" statement in line 30, I assign:

variables['V'] = 1
fors['V'] = ForState(continu=3, end=10, step=2)
where 3 is the index of line 40 (the line right after the FOR statement); 10 is the value of N; and 2 is the value of N/5.

• When control hits the "NEXT V" statement in line 50, I do the following:

Examine fors['V'] to check if V incremented by the step value, 2, is within the bounds defined by the end, 10.
If it is, increment V and assign pc to be 3, the continu value.
If not, continue on to the following statement, 60.

Execution: Printing¶

We showed how to parse a PRINT statement with labels_and_expressions(); now it is time to execute a PRINT statement, printing each of the labels and expressions, and keeping track of what column to print at next, using the global variable column.

Running the First Sample Program¶

Let's re-examine, parse, and run our first sample program:

Running More Programs¶

Rather than put together a suite of unit tests for execute, I'll run integration tests—additional whole programs. I've also added a few assertions.

We can look at the variables that have been stored for this program:

Checking for Syntax Errors¶

Here we show a collection of syntax errors, and the messages they generate:

Longer Program: Life¶

Now for a final, slightly more complicated example: Conway's Game of Life.

Actually, this was an assignment in my high school BASIC class. (We used a slightly different version of BASIC.) Back then, output was on rolls of paper, and I thought it was wasteful to print only one generation per line. So I arranged to print multiple generations on the same line, storing them until it was time to print them out. But BASIC doesn't have three-dimensional arrays, so I needed to store several generations worth of data in one A(X, Y) value. Today, I know that that could be done by allocating one bit for each generation, but back then I don't think I knew about binary representation, so I stored one generation in each decimal digit. That means I no longer need two matrixes, A and B; instead, the current generation will always be the value in the one's place, the previous generation in the ten's place, and the one before that in the hundred's place. (Also, I admit I cheated: I added the mod operatoir, %, which did not appear in early versions of BASIC, just because it was useful for this program.)