in the memory of Microsoft Basic (4K Basic)
lister (lister.zip) and interpreter (interp.zip)
for Retro Basic
A program to print 1 to 10
10 A = 1
20 IF 10 < A 60
30 PRINT A
40 A = A + 1
50 GOTO 20
60 STOP
A program to sum 1 to 10
10 A = 1
20 S = 0
30 IF 10 < A 70
40 S = S + A
50 A = A + 1
60 GOTO 30
70 PRINT S
80 STOP
A program in Retro Basic consists of lines. Each line starts with
line_number follows by a statement. Statements are a) assignment b)
if c) print d) goto e) stop. An assignment is "id = exp" where id is
{A..Z}. An expression is binary op +/- between id and constant.
An if statement is "IF cond line_number", where cond is binary op {<,=}
between id and constant. A print statement is "PRINT id". An
goto statement is "GOTO line_num". A stop statement is "STOP". A
constant is {0..100}.
Here is Retro Basic grammar:
pgm := line pgm | EOF
line := line_num stmt
stmt := asgmnt | if | print | goto | stop
asgmnt := id = exp
exp := term + term | term - term | term
term := id | const
if := IF cond line_num
cond := term < term | term = term
print := PRINT id
goto := GOTO line_num
stop := STOP
id is {A..Z}
const is {1..100}
line_num is {1..1000}
Your job is to write a compiler to translate the source of Retro Basic to
the "intermediate code". Here is the intermediate code (B-code):
B-code is stored in an array of cells (32-bit) where the input source is
tokenised (to help speed up the run-time interpreter). Each token
consists of two consecutive cells: type, value (a tuple).
line_num {#line, num} num
is {1..1000}
id {#id,
ref} ref is index 1..26 corresponded
to A..Z
const {#const, value} value is
{1..100}
IF {#if, 0}
GOTO {#goto,
num} num is {1..1000}
PRINT {#print, 0}
STOP {#stop, 0}
+ {#op, 1}
- {#op, 2}
< {#op,
3}
= {#op, 4}
Example of the translation of a line into B-code
10 A = 1
{#line, 10} {#id, A} {#op, 4} {#const, 1}
30 IF 10 < A 70
{#line, 30} {#if, 0} {#const, 10} {#op, 3} {#id, A} {#goto,
70}
*** line_num became "goto"
Here is the coding of B-code type:
#line 10
#id 11
#const 12
#if 13
#goto 14
#print 15
#stop 16
#op 17
I will provide an B-code interpreter so that you can "run" your output to
check that you correctly compile your source and output the correct
B-code. The input to B-code interpreter is a sequence of integer
representing the B-code cell, with 0 represents the end of file.
For example the above two lines
10 A = 1
30 IF 10 < A 70
...
B-code
10 10 11 1 17 4 12 1
10 30 13 0 12 10 17 3 11 1 14 70
...
0
What you must submit:
1) A report describes your compiler. It consists of two parts
1.1 a scanner, how you scan the source and separate characters
into token
1.2 a parser, how you check the sequence of token that it is
correct according to the grammar.
2) Your pseudo code of the compiler
3) You will get a bonus if you also submit an actual working code.
(You can use any of your favourite programming language, give me the link
to your working code which I can try, both source and executable)
Depend on your programming skill, this project can take a few days up to a
week of programming if you want to produce an actual working code.
You can check your output B-code with my interpreter. You will spend
a lot less time if you just describe your compiler in pseudo code (or in
plain narrative). But it is more fun to have a code that is actually
work!
Due date Tuesday 18 December 2018, at 4pm.
Here is a tool (lister.zip ) to print Basic program from B-code (a listing). Use it to check the correct output from your compiler. The lister package includes an executable file. Here is a sample of the session to use lister.
Assume this is a Retro Basic program to print 1 to 10:
10
A = 1
20 IF 10 < A 60
30 PRINT A
40 A = A + 1
50 GOTO 20
60 STOP
It is translated into B-code like this (showing tuples of B-code):
10
A = 1
(10,10)
(11,1) (17,4) (12,1)
20
IF 10 < A 60
(10,20)
(13,0) (12,10) (17,3) (11,1) (14,60)
30
PRINT A
(10,30)
(15,0) (11,1)
40
A = A + 1
(10,40)
(11,1) (17,4) (11,1) (17,1) (12,1)
50
GOTO 20
(10,50)
(14,20)
60
STOP
The valid output B-code is (assume it is in the file "print1-10.txt") :
10 10 11 1 17 4 12 1
10 20 13 0 12 10 17 3 11 1 14 60
10 30 15 0 11 1
10 40 11 1 17 4 11 1 17 1 12 1
10 50 14 20
10 60 16 0
0
Use lister:
c>basic\lister\lister print1-10.txt
10 10 11 1 17 4 12 1 10 20 13 0 12 10 17 3 11 1 14 60 10 30 15 0 11
1
10 40 11 1 17 4 11 1 17 1 12 1 10 50 14 20 10 60 16 0 0
10
A = 1
20 IF 10 < A GOTO 60
30 PRINT A
40 A = A + 1
50 GOTO 20
60 STOP
c>basic\lister\
The interpreter (interp.zip) takes B-code and run it. The trace of execution is shown. You will see the line number of the current line (# num), the asignment of a variable and the result of boolean test.
c>basic\interp\interp print1-10.txt
. . .
run
# 10
set A with 1
# 20
boolean 0
#30
<1>
# 40
set A with 2
# 50
. . .
<10>
# 40
set A with 11
# 50
# 20
boolean 1
# 60
stop
c>basic\interp
Enjoy
last update 28 Nov 2018