This section contains the formal specification of the BBB language.
A program line always begins with a line number, and may not contain
more than 80 characters after the line number. The line numbers
determine the order in which the lines will be executed, and are also
used as references for branching. Line numbers may be any integer
between 1 and 32760 (inclusive).
A variable name must begin with a letter, and may be followed by any
combination of letters and digits. The name may end with a
``$'' character if the variable contains a string. If it
contains an integer, there should be no ``$'' after it.
Variable names and keywords are not case sensitive. You can have two
variables with the same name but different types (i.e., ``foo''
and ``foo$'' should be considered different variable names).
A comment begins with a single quote character (') and continues
until the end of the line. A comment is treated as white space by the
interpreter (i.e., the beginning of the comment marks the end of the
line). A comment may appear on a line by itself (it still needs a
line number), or it may appear following the code on a line.
A number must begin with a digit, and may contain any number of digits
afterwards. The language only deals with 16-bit signed integers, so
the maximum value is 32767. If a number larger than this is entered
into the program, the results are undefined. A negative number is
actually treated as a unary minus operator followed by a positive
number.
A literal string must begin and end with a double quote character
("). The string may contain any printable characters including
spaces and tabs. The string may not contain any line breaks, or
double quote characters.
Here is the formal definition of the BBB language syntax:
primary_exp ::= Tfor var = expression to
line ::= number statement
statement ::= end 
for var = expression to
expression
for var = expression to
expression step number
next var
gosub number
return
goto number
if condition goto number
let var = expression
input var_list
input str_const var_list
print exp_list
print exp_list ;
var_list ::= var
var , var_list
exp_list ::= expression
expression , exp_list
condition ::= relation
relation and condition
relation or condition
rel_op ::= = <> < >
<= >=
relation ::= expression rel_op expression
not condition
expression ::= term
term + expression
term - expression
term ::= factor
factor * term
factor / term
factor mod term
factor ::= primary_exp
- primary_exp
function ::= abs len str val
primary_exp ::= var
number
string
( expression )
function ( expression )
This section will tell you how all the various constructs in the BBB
language should work.
There are two data types in BBB: integers and strings. Integers are
16-bit signed integers. The implementation of strings is not specified.
It may be a null-terminated array of characters, or a length byte may
be used, or any other method of implementation chosen.
Operators
The relational operators (=, <>, <, >,
<=, >=) work on either strings or integers, and result in
a boolean value. The expressions on each side of the operator must be
the same type (i.e., "Hello" = 3 should be a type error. They
should perform the comparison that you might expect: equality,
inequality, strictly less than, strictly greater than, less than or
equal to, or greater than or equal to, respectively. String
comparisons should be case-sensitive, and should compare in
ASCII-logical order (i.e., compare the ASCII values of the first
character, if they are the same go on to the second, and so on). If
two strings have the same ASCII values, the shorter string is less
than the longer string. For two strings to be equal, they must have
the same ASCII values and be the same length.
The boolean operators (and, or, not) work only on
boolean (true or false) values
(which can only be created by a relational operator),
and result in a boolean value. The and operator should return
true if both operands are true, false otherwise. If the left operand
is false, the right operand should not be evaluated, as we already
know the condition to be false. The or operator should return
true if either operand is true, false otherwise. If the left operand
is true, the right operand should not be evaluated, as we already know
the condition to be true. The not operator is a unary operator
and returns the inverse of its operand.
The plus operator (+) can work on either strings or integers,
and the result should be of the same type as the operands. The
expressions on each side of the operator must be the same type. When
working on strings, the result should be the concatenation of the
strings. When working on integers, the result should be the sum.
There is no unary plus operator.
The other arithmetic operators (-, *, /, mod)
can only work on integers, and result in integers. The results should
be as you might expect: the difference, product, quotient, and
remainder, respectively. The minus operator (-) may also be a
unary operator, in which case it returns the negative of its operand.
Built-in functions
The abs function takes an integer and returns an integer.
The result should be the absolute value of the argument.
The len function takes a string and returns an integer.
The result should be the number of characters in the argument string,
excluding any length byte or null character.
The str function takes an integer and returns a string.
The result should be a string representation of the argument.
For example, str(123) returns the string ``123''.
The val function takes a string and returns an integer.
The result should be the integer representation of the string.
For example val(``123'') returns the integer 123. If
there are any characters in the string that are not digits, the
function should produce an error.
Operator precedence
The following chart shows the precedence of the operators, listed in
increasing order of precedence (i.e., operators lower on the chart get
executed before ones higher on the chart). Operators listed on the
same line have equal precedence, in which case they are executed from
left to right.
Other notes
If a variable is used in an expression and it does not exist, it
should be created, and initialized to a zero/empty value.
Notice that the BNF does not allow you to put parentheses around a
condition. This is because if you were parsing a condition, and your
next token was a left parenthesis, there would be no way to know if
the parentheses were wrapped around a condition, or part of an
expression beginning a relation.
return ¯let let var = expression
end end
print print exp_list
print exp_list ;
input input var_list
input str_const var_list
goto goto number
if if condition goto number
for for var = expression to
expression
next for var = expression to
expression step number
next var
gosub gosub number
return return
During the execution of a program, the interpreter may come upon
something that doesn't fit into the specification of the program, or
something that just doesn't make sense. Should this occur, the
interpreter should print out an error message and stop executing the
program. Any error message should begin on a new line, and start with
"Error: ". If a line number is associated with this error, it
should be printed out in parentheses (for example, "(line
100)"). Following this, you should print out a message that
describes the nature of the error. You should be as detailed as
possible, but the error message should fit on one line.
One of the main purposes of this project is to test your ability to
construct a robust program (i.e., a program that detects and handles
errors in a graceful way). When we test your program, we will do
everything we can to try and cause your program to fail. You should
try to think of every possible thing which can go wrong, and check for
it in your program. We may have intentionally left some errors
unhandled in the code that we provided.
The following limits have been placed on the interpreter to make it
easier to implement.
- a program will not have more than 200 lines (including
lines which only contain comments)
- a line may not have more than 80 characters (excluding the
line number)
- a variable name may not be more than 15 characters (including
the "$" if any)
- there may not be more than 50 string variables
- a string variable may not contain more than 127 characters
- there may not be more than 200 integer variables
- subroutine calls may not nest more than 200 calls deep
If you wish to earn bonus points, you can implement your interpreter
in a way that there is no limit in one (or more) of these areas:
- Number of lines of code in the program
- Number of variables
- Number of nested subroutine calls
This will require using much more complicated structures to represent
these things. Note: to get the bonus points, you should implement it
in a way that it is only limited by the amount of memory available in
the computer, not simply increase these limits to a higher limit.
The bonus points will not represent a large portion of your score.
You should not spend time performing these extensions until you have
finished everything else. Make sure you save a copy of your working
interpreter before you try implementing these extensions in case you
don't get them working. The bonus will not be so big as to offset
sacrificing the functionality of the interpreter.
Alyosha Efros
Mon Mar 3 17:43:27 MST 1997