tiny basic

CONTENTS of THIS PAGE...

Introduction (just below), Tiny Basic Formal Syntax, Testing and Marking, Examples, Bonuses

And if you still need more help try THIS (Help)

Exercises, Exercises Form; Exercises Solutions

Sample Marking Guide

Your job this time is to design and implement an Object Oriented program that will parse and interpret a computer program written in a language we will call Tiny Basic. Input to the program will be a text file (with the suffix '.tb') that contains a program written in Tiny Basic (rules below). The output will be the output as generated by the Tiny Basic program.

 

See the Lab Notes for background on Interpreters and a "plan of attack".

 

A minimal solution may assume that the input is valid and correct.

 

Rules of Syntax for Tiny Basic:

Each line of a Tiny Basic program has the following form:

[<spaces>]<line-number><spaces><statement>

 

Which means:

1. there may be optional leading blank spaces

2. there will be a line number (required) which starts with 1, and increases by one on each line

3. there are one or more blank spaces following the line number

4. the statement may be one of the following:

LET<spaces><variable>=<expression>

PRINT<spaces><variable>

GOTO<spaces><expression>

IF<spaces><expression>

STOP

 

Formal Syntax Rules (Bakkus Naur Form, or BNF):

::= means 'is defined as' or "consists of"

<something> means an entity that is further defined (usually later)

{<something>} means that the thing enclosed in braces is optional and can be omitted

X | Y means that either 'X' or 'Y' can be used here

all other marks must appear literally

 

<program> ::= <line> | <line> {<line>}

 

<line> ::= {<spaces>}<line number><spaces><statement>

 

<statement> ::=

LET<spaces><variable>=<expression> |

PRINT<spaces><variable> |

GOTO<spaces><expression> |

IF<spaces><expression |

STOP

 

<expression> ::= <constant> | <variable> |

<variable><operator><variable>

<operator> ::= + | >

<constant> ::= -10000 ... 10000

<variable> ::= A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

<spaces> ::= \040 | \040 {<spaces>}

<line number> ::= 1 | 2 | 3 | ... | 100

 

<variable> > <variable> evaluates to 1 if true; 0 if false

 

There are to be no blanks surrounding the "=" of a LET statement or within an expression.

The maximum number of lines in a Tiny Basic program is 100.

 

Rules of Execution of a Tiny Basic Program:

Program execution of the program begins at line 1.

All variables used in the program have the initial value 0.

Statements are executed consecutively, with the exception of the IF and the GOTO statements.

 

Rules defining each of the five types of statements:

 

LET

- for assigning a value to a variable

- the result of adding two variables must be in the range [-10000 ... 10000]

 

PRINT

- prints out the value of a variable in the form:

<name>=<value>

which must be left-justified and followed by a new-line

- there are no blank spaces surrounding the '=' sign

 

GOTO

- jumps to a new location in the program given by <expression>

- <expression> is not necessarily a constant

- <expression> must evaluate to a valid line number within the program

 

IF

-skips the next line of code if the value of the expression is zero

- the program must have at least two statements that follow any IF statement

 

STOP

- halts execution

- prints a brief message to the screen (like "END PROGRAM")

 

- the program must eventually execute a STOP statement

- the program may contain more than one STOP statement

- the last statement in the program does not need to be a STOP statement

---

Testing and Marking:

Test your interpreter on the following files:

all files in the course directory /home/233/Parser

(note: some files will be missing; number ranges were chosen to keep different

kinds of tests identifiable)

prog1.tb - prog9.tb : test normal function statements correct

prog10.tb -prog19.tb: test various error conditions [bonus # 4]

prog20.tb - prog29.tb: test bonus 5

prog30.tb - prog39.tb : test bonus 1 and 2

prog40.tb -prog49.tb test bonus 3 & 6

 

Notes on Marking:

We will be looking for the usual good, clean design; documentation, etc. as always.

In order to pass it must work. (Some marks will be given to all *reasonable* attempts, working or not)

Specifics we will be looking for when marking:

- external documentation IS DEFINITELY necessary on this one; it must include:

- an outline of the main algorithm including the key data structures (diagram is best)

- an outline for each major task in the main algorithm

- input to the program should be done using command-line arguments

- division into classes should be reasonable (can you justify your choices?)

- do you have some sort of debugging facility built in?

Important Note: if your program does not function properly it is possible to verify that some parts work if you have produced a reasonable trace (see sample solution)

- does your program read and recognize tokens?

- can it classify them correctly into descriptors?

- do you have some sort of "memory"?

- are the Scanner and Interpreter logically separate?

 

How to submit your assignment:

This assignment MUST be submitted electronically using submit.

Include:

- all '.cc' files

- all '.h' files

- your external documentation

- any additional test files ('.tb') you wish to include

 

Example 1: Here is an example of a Tiny Basic program which prints out the first A odd integers, where A is set on line 1:

1 LET A=10

2 LET I=0

3 LET X=I+I

4 LET T=1

5 LET X=X+T

6 PRINT X

7 LET T=1

8 LET I=I+T

9 IF A>I

10 GOTO 3

11 STOP

Running the Tiny Basic interpreter with this input should produce the following output:

X=1

X=3

X=5

X=7

X=9

X=11

X=13

X=15

X=17

X=19

END PROGRAM

 

Example 2: This example computes the negatives of three numbers, which are set on line 1, 5, and 9

1 LET X=-12

2 LET R=4

3 GOTO 14

4 PRINT V

5 LET X=3

6 LET R=8

7 GOTO 14

8 PRINT V

9 LET X=0

10 LET R=12

11 GOTO 14

12 PRINT V

13 STOP

14 IF Z>X

15 GOTO 23

16 LET V=1

17 LET T=-1

18 LET V=V+T

19 LET T=V+X

20 IF T>Z

21 GOTO 17

22 GOTO R+Z

23 LET V=-1

24 LET T=1

25 LET V=V+T

26 LET T=V+X

27 IF Z>T

28 GOTO 24

29 GOTO R+Z

 

Running the Tiny Basic interpreter with this input should produce the following output:

V=12

V=-3

V=0

END PROGRAM

 

BONUSES:

1. [2 points] Allow comments (identified by REM) - they still need line numbers

2. [2 points] Allow in-line (actually, end-of-line) comments

3. [2 points] Allow - * / as additional operators

4. [2 points] Check line numbers for validity (both at the start of the line and in GOTO's)

5. [3-6 points] detect invalid statements, print a diagnostic message and terminate or continue gracefully

6. [3-5 points] Allow expressions as:

<expression> ::= <operand> |

<operand><operator><operand>

<operand> ::= <variable> | <constant>

Updated: August 6, 2005 12:08 AM