An experiment in the design of a basic interpreter
Hal Pitts · 1977
This paper describes the author's experience on the design and implementation of a BASIC interpretive compiler written in Algol W programming language. The experiment was initiated to gain full control of an executing BASIC program for run time debugging and automating the grading of students programs in beginning BASIC programming classes. The interpreter is implemented in Algol W programming language. The block structure and the control structures of Algol W provided a convenient environment for designing a truely structured program. The powerful data structures facilities available in Algol W gave the author better control of the program. The input/output facilities of the Algol W version at Georgia State University simplified the task of internal/external numerical conversions. In the opinion of this author, Algol W is an excellent language for debugging and writing interpretive compilers. The BASIC interpreter operates in two loosely connected phases: a parsing phase and an interpretive phase. The parsing phase analyzes the complete source program and translates the input program into pseudo machine-like code. Major tasks of this phase are: Allocation of memory locations to variables and constants, conversion of expressions into Reverse Polish form, and the generation of pseudo machine code. The interpretive phase executes the pseudo code simulating a BASIC machine. The pseudo machine code was designed to minimize the time needed to decode and execute it.