BASIC Interpreter, Part V

This is a continuation of Part IV. In Part V we will add support for parentheses in mathematical expressions, add the GOTO and END statements, and implement the remaining program storage statements: CATALOG, SCRATCH, and RENAME.

Now that we have a framework for supporting numerical operations, adding parentheses is not difficult. An expression wrapped in parentheses is equivalent to a literal double or a variable name, so we will put evaluation into the term rule in Bison. We need a new subclass of DoubleExpression, which we will call ParenExpression. It will store a pointer to an inner DoubleExpression, and return its value when queried. The only thing this new class adds is in the list() function it will print out parentheses so that the program line can be printed out and read back in. Here is the header file, parenexpression.h:

#ifndef _PARENEXPRESSION_H_
#define _PARENEXPRESSION_H_

#include <string>

#include "doubleexpression.h"

/*
This class is used to store a parenthesized expression
*/
class ParenExpression : public DoubleExpression {
public:
	ParenExpression(DoubleExpression *exp);
	~ParenExpression();

	const std::string print() const;		// return a printable value
	const std::string list() const;			// print a listing version
	double value() const;				// numerical evaluation

private:
	DoubleExpression *exp;
};

#endif

Here is the implementation, parenexpression.cpp:

#include "parenexpression.h"

ParenExpression::ParenExpression(DoubleExpression *exp) : DoubleExpression(0){
	this->exp = exp;
}

ParenExpression::~ParenExpression(){
	delete exp;
}

// return a printable value
const std::string ParenExpression::print() const{
	return std::to_string(value());
}

// print a listing version
const std::string ParenExpression::list() const{
	return "(" + exp->list() + ")";
}

// numerical evaluation
double ParenExpression::value() const{
	return exp->value();
}

In the Bison input file, include the new header file, add two new tokens to represent the parenthesis literals, and modify the term rule to create the new subclass:

#include "parenexpression.h"

...

%token OPENPAREN
%token CLOSEPAREN

...

term:
	DOUBLE			{ $$ = new DoubleExpression($1); }
	| VAR			{
					$$ = new VariableExpression($1);
					free($1);
				}
	| OPENPAREN addExpr CLOSEPAREN	{ $$ = new ParenExpression($2); }
;

In the flex input file, add scanners for the new parenthesis tokens:

\(		{ return OPENPAREN; }
\)		{ return CLOSEPAREN; }

Add the new header and source files to your Makefile, and after compiling you will be able to run programs likes the example below:

Welcome to BASIC!
Enter a program name: new     
>10 print 2*(3+4)
>run
14.000000
>20 print 2*(3+4)^2
>run
14.000000
98.000000
>list
10 PRINT 2.000000*(3.000000+4.000000)
20 PRINT 2.000000*(3.000000+4.000000)^2.000000

Now we will add the GOTO and END statements. GOTO is used to jump to an arbitrary line number during program execution, allowing lines to be skipped or executed in a different order. END terminates the current program. Per the BASIC manual we are following, an END statement is required in every program, and it must be the highest line number. We have already deviated from that by not requiring an END statement, and we will further deviate by allowing it to appear anywhere.

To support these new statements, we need to change how we handle program execution. Right now, we have a for loop that steps through every statement in order and executes it. Clearly, this won’t work. What we need to do instead is have a program counter variable that keeps track of which line to execute next, and have functions that allow this to be modified.

Let’s start by updating program.h. Add a new private member variable counter to keep track of which line to execute next. This variable is an iterator of the same signature as used in our current execute() function:

private:

...

	std::map<int, const Program*>::iterator counter;	// program line to run next

Next, add the public member functions to manipulate the counter: one to advance to the next line (standard behavior), one to jump to an arbitrary line, and one to go to the end of the program:

public:

...

	void gotoLine(int line);	// jump to program line
	void nextLine();		// go to next program line
	void endProgram();		// end execution

Now we can update the class implementation, basic.cpp. First, update the execute() function to use our new counter variable. Instead of a for loop, we will reset counter to the beginning, and then have a while loop that executes each statement until counter points to the end. Of course, this requires that each statement execution update counter to another line, or we will get stuck execute the same line over and over:

// run the program
void Basic::execute(){
	counter = lines.begin();
	while( counter != lines.end() )
		counter->second->execute();
}

Next, add implementations for the three new functions we declared for manipulating counter:

// jump to program line
void Basic::gotoLine(int line){
	counter = lines.find(line);
}

// go to next program line
void Basic::nextLine(){
	++counter;
}

// end program execution
void Basic::endProgram(){
	counter = lines.end();
}

Now that we have the control logic implemented, we can create the classes that call these function to support the GOTO and END statements. We will create two new subclasses of Program. Goto will take and store a single integer line number; End will take no arguments, and simply call Basic::endProgram() in its execution. Here is the header file goto.h</em:

#ifndef _GOTO_H_
#define _GOTO_H_

#include 

#include "program.h"

/*
This class implements the GOTO statement
*/
class Goto : public Program {
public:
	Goto(int line);				// instantiate goto statement
	
	void execute() const;			// run this line of the program
	void list(std::ostream& os) const;	// list this line

private:
	int line;				// line to goto
};

#endif

Here is its implementation, goto.cpp:

#include "goto.h"
#include "basic.h"

// instantiate goto statement
Goto::Goto(int line){
	this->line = line;
}

// run this line of the program
void Goto::execute() const{
	Basic::instance()->gotoLine(line);
}

// list this line
void Goto::list(std::ostream& os) const{
	os << "GOTO " << line;
}

The End class is even simpler; all it needs to do is provide implementations of the virtual functions defined by Program. Here is the header file, end.h:

#ifndef _END_H_
#define _END_H_

#include 

#include "program.h"

class End : public Program {
public:
	void execute() const;			// run this line of the program
	void list(std::ostream& os) const;	// list this line
};

#endif

And the implementation, end.cpp:

#include "end.h"
#include "basic.h"

// run this line of the program
void End::execute() const{
	Basic::instance()->endProgram();
}

// list this line
void End::list(std::ostream& os) const{
	os << "END";
}

Our new statements will now work, but if we left it like this and tried to run a program, any of the old statements would get stuck in a loop; we need to update them to call Basic::nextLine(). We will call this in Program::execute(), which previously did nothing, and the subclasses will then call Program::execute() after performing their own execution. Here is the new program.cpp:

#include "program.h"
#include "basic.h"

// advance to next line
void Program::execute() const{
	Basic::instance()->nextLine();
}

// if you ever see this, something is wrong
void Program::list(std::ostream& os) const{
	os << "GENERIC PROGRAM (SHOULDN'T SEE THIS)";
}

Here is the update to Let::execute():

// store the value of the Expression in the Basic vars map
void Let::execute() const{
	Basic::instance()->assign(var, expression->value());
	Program::execute();
}

And similarly in print.cpp:

// prints out each expression to std::cout
void Print::execute() const{
	for( int i = 0; i < exprList->size()-1; i++ ){
		cout << exprList->at(i)->print() << ' ';
	}
	cout << exprList->at(exprList->size()-1)->print() << endl;
	Program::execute();
}

Next we will update our Bison input file to use our new statements. First, include the new header files:

#include "goto.h"
#include "end.h"

Add two new constant tokens:

%token GOTO
%token END

We are going to make some changes to how flex scans for LINE tokens. Right now, it recognizes an integer starting at the beginning of a line as a LINE token. But since the GOTO statement requires a line number to be provided later, we have to recognize an integer anywhere. This will screw up our DOUBLE recognition, which scans for any number not at the beginning of a line, so let’s just rename our LINE token to INT:

%token <iVal> INT

Since we no longer have a LINE token, update the stmt rule to use the new INT token:

stmt:
	INT			{ Basic::instance()->remove($1); }
	| INT program		{ Basic::instance()->add($1, $2); }
	| RUN			{ Basic::instance()->execute(); }
	| LIST			{ Basic::instance()->list(std::cout); }
	| NEW			{ Basic::instance()->newProgram(); }
	| OLD			{ Basic::instance()->oldProgram(); }
	| SAVE			{ Basic::instance()->saveProgram(); }
	| UNSAVE		{ Basic::instance()->unsaveProgram(); }
;

Now add our two new statements to the program rule:

program:
	PRINT exprList			{ $$ = new Print($2); }
	| LET VAR EQUAL doubleExpr	{
						$$ = new Let($2, $4);
						free($2);	// malloced in basic.l
					}
	| GOTO INT			{ $$ = new Goto($2); }
	| END				{ $$ = new End(); }
;

And since flex will now preferentially return an INT token rather than a DOUBLE, we need to support that in our term rule:

term:
	DOUBLE			{ $$ = new DoubleExpression($1); }
	| INT			{ $$ = new DoubleExpression($1); }
	| VAR			{
					$$ = new VariableExpression($1);
					free($1);
				}
	| OPENPAREN addExpr CLOSEPAREN	{ $$ = new ParenExpression($2); }
;

In the flex input file, change the LINE scanner to return INT, and remove the caret at the beginning so that it will match an INT anywhere:

{DIGIT}+	{ yylval.iVal = atoi(yytext); return INT; }

Also, add scanners for the two new constant tokens:

GOTO		{ return GOTO; }
END		{ return END; }

Lastly, add the new header and implementation files to your Makefile. Here is the updated file at this point in time:

.PHONY: all clean

all:	basic.tab.c lex.yy.c \
		basic.h basic.cpp \
		program.h program.cpp \
		print.h print.cpp \
		expression.h expression.cpp \
		stringexpression.h stringexpression.cpp \
		doubleexpression.h doubleexpression.cpp \
		operatorexpression.h operatorexpression.cpp \
		let.h let.cpp \
		variableexpression.h variableexpression.cpp \
		parenexpression.h parenexpression.cpp \
		goto.h goto.cpp \
		end.h end.cpp
	g++ -std=c++11 basic.tab.c lex.yy.c program.cpp basic.cpp print.cpp expression.cpp \
	stringexpression.cpp doubleexpression.cpp operatorexpression.cpp let.cpp \
	variableexpression.cpp parenexpression.cpp goto.cpp end.cpp \
	-o basic

basic.tab.c: basic.y basic.h expression.h stringexpression.h doubleexpression.h \
		operatorexpression.h print.h program.h let.h variableexpression.h parenexpression.h \
		goto.h end.h
	bison -d basic.y
	
basic.tab.h: basic.y
	bison -d basic.y

lex.yy.c: basic.tab.h basic.l
	flex basic.l

clean:
	rm basic.tab.c basic.tab.h lex.yy.c basic *.o

You can now build and run programs like the following:

Welcome to BASIC!
Enter a program name: test
>10 print 10
>20 goto 40
>30 end
>40 print 40
>50 goto 25
>25 print 25
>list
10 PRINT 10.000000
20 GOTO 40
25 PRINT 25.000000
30 END
40 PRINT 40.000000
50 GOTO 25
>run
10.000000
40.000000
25.000000

OK, the last things we want to add this time are the final program storage statements: CATALOG, SCRATCH, and RENAME. CATALOG lists the saved BASIC files in the current directory; SCRATCH erases the current stored program, but keeps its name; and RENAME keeps the stored program but lets the user enter a new name. This will involve changes to the Basic class, as well as the Bison and flex input files. Let’s start with the Basic header file. We already have a private function erase() that we can repurpose for the SCRATCH functionality, so make that a public function. Also, add two new functions: renameProgram() and catalogPrograms():

class Basic {
public:

...

	void saveProgram();				// save active program to disk
	void unsaveProgram();				// delete saved program from disk
	void newProgram();				// start a new program
	void oldProgram();				// load program from disk
	void erase();					// clear stored program lines
	void renameProgram();				// rename the current program
	void catalogPrograms();				// list saved programs

...

For the implementation, our existing newProgram() function contains what we need for our newProgram() function, but first calls erase(). So we will move everything after erase() into the newProgram() and then call newProgram():

// start a new program
void Basic::newProgram(){
	erase();
	renameProgram();
}

// rename the current program
void Basic::renameProgram(){
	std::cout << "Enter a program name: ";
	std::cin >> name;
	std::cin.ignore();	// consume the newline character
}

Listing the programs that have been saved to disk is a little more complicated. C++ has not included directory access in the standard until very recently. I have used some code that works on Linux and Mac OS X; Windows users will have to find a different solution. First, we need to include a few more headers in basic.cpp:

#include <cstring>
#include <set>
#include <unistd.h>
#include <sys/dir.h>

Now we can add our new catalogPrograms() function:

// list saved programs
void Basic::catalogPrograms(){
	char cwd[FILENAME_MAX];
	getcwd(cwd, FILENAME_MAX);

	DIR* dirp = opendir(cwd);
	struct dirent * dp;
	std::set set;	// store in a set to get alphabetical ordering
	while ((dp = readdir(dirp)) != NULL) {
		char *sub = strstr(dp->d_name, ".bas");
		if( strstr(dp->d_name, ".bas") ){
			sub[0] = 0;	// end name before .bas
			set.insert(dp->d_name);
		}
	}
	closedir(dirp);
	// print them out
	for( std::set::iterator it = set.begin(); it != set.end(); ++it ){
		std::cout << *it << std::endl;
	}
}

First we create a character buffer (cwd) that can store the maximum filename length, and populate it with the current directory. Then we open this directory for reading, and step through it, adding every file that ends in “.bas” to a std::set (this automatically sorts them alphabetically, which the directory read may not do). Once we have added them all, we iterate through the std::set and print the results.

Since we haven’t added any new files, our existing Makefile does not need to be changed. The complete source files for this part can be found here: https://github.com/VisceralLogic/basic/tree/part-5

Continue to Part VI.

2 thoughts on “BASIC Interpreter, Part V

  1. Pingback: BASIC Interpreter, Part IV | Visceral Logic Programming

  2. Pingback: BASIC Interpreter, Part VI | Visceral Logic Programming

Leave a Reply

Your email address will not be published. Required fields are marked *