{"id":46,"date":"2018-09-07T20:49:16","date_gmt":"2018-09-08T04:49:16","guid":{"rendered":"https:\/\/www.viscerallogic.com\/programming\/blog\/?p=46"},"modified":"2018-09-07T20:51:39","modified_gmt":"2018-09-08T04:51:39","slug":"basic-interpreter-part-ii","status":"publish","type":"post","link":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-ii\/","title":{"rendered":"BASIC Interpreter, Part II"},"content":{"rendered":"

This is a continuation of Part I<\/a>. In Part II, we will add functionality to store and run BASIC programs, although still limited to the PRINT<\/em> statement. We will also be adding a LIST<\/em> statement to print out the currently stored program.
\n<\/p>\n

We will be adding a number of new C++ classes now. The overall architecture is to have a singleton class named Basic<\/em> which maintains all the lines of code, and can update and execute them as needed. The program lines will be kept in a std::map<int, const Program*><\/em>, where Program<\/em> is another new class we will be creating that is the base class for all BASIC program lines. Here is the header file basic.h<\/em>:<\/p>\n

#ifndef _BASIC_H_\r\n#define _BASIC_H_\r\n\r\n#include <map>\r\n\r\n#include \"program.h\"\r\n\r\n\/*\r\nThis is a singleton class which contains all the program lines.\r\n*\/\r\nclass Basic {\r\npublic:\r\n\tvoid add(int index, const Program *program);\t\t\/\/ add a new line to the program\r\n\tvoid list();\t\t\t\t\t\t\t\t\t\t\/\/ list out all the existing lines\r\n\tvoid execute();\t\t\t\t\t\t\t\t\t\t\/\/ run the program\r\n\t\r\n\tstatic Basic *instance();\t\t\t\t\t\t\t\/\/ access the singleton instance\r\n\t\r\nprivate:\r\n\tstd::map<int, const Program*> lines;\t\t\t\t\/\/ store the lines in a map\r\n\t\r\n\tstatic Basic *b;\t\t\t\t\t\t\t\t\t\/\/ singleton instance\r\n};\r\n\r\n#endif<\/pre>\n
Here is the corresponding implementation, basic.cpp<\/em>:<\/p>\n
#include <iostream>\r\n\r\n#include \"basic.h\"\r\n\r\nusing std::map;\r\n\r\nBasic *Basic::b;\r\n\r\n\/\/ add a program line at index, overwriting if it exists\r\nvoid Basic::add(int index, const Program *program){\r\n\t\/\/ see if index already exists, if so delete it\r\n\tmap<int, const Program*>::iterator it = lines.find(index);\r\n\tif( it != lines.end() ){\r\n\t\tconst Program *old = it->second;\r\n\t\tdelete old;\r\n\t\tlines.erase(index);\r\n\t}\r\n\t\r\n\tlines.insert(std::pair<int, const Program *>(index, program));\r\n}\r\n\r\n\/\/ print out the program lines\r\nvoid Basic::list(){\r\n\tfor( map<int, const Program *>::iterator it = lines.begin(); it!= lines.end(); ++it ){\r\n\t\tstd::cout << it->first << \" \";\r\n\t\tit->second->list(std::cout);\r\n\t\tstd::cout << std::endl;\r\n\t}\r\n}\r\n\r\n\/\/ run the program\r\nvoid Basic::execute(){\r\n\tfor( map<int, const Program*>::iterator it = lines.begin(); it != lines.end(); ++it ){\r\n\t\tit->second->execute();\r\n\t}\r\n}\r\n\r\n\/\/ access the singleton instance, creating it if necessary\r\nBasic *Basic::instance(){\r\n\tif( b == NULL )\r\n\t\tb = new Basic();\r\n\treturn b;\r\n}<\/pre>\n
The add<\/em> function will insert an executable line into the map lines<\/em>. If that line number already exists, the Program<\/em> at the line will be deleted. We are using pointers to the programs because they will are derived classes, and we want to call the virtual functions belonging to the instances, not to the base class. The list<\/em> function will print out all the source lines, in order, to the standard output stream. The function execute<\/em> steps through each program line and runs it. The static function instance<\/em> returns the singleton instance of the Basic<\/em> class, creating it for the first time if necessary.<\/p>\n
Here is the header file program.h<\/em>, which declares the Program<\/em> base class. The base class has two functions, which all sub-classes must implement:<\/p>\n
#ifndef _PROGRAM_H_\r\n#define _PROGRAM_H_\r\n\r\n#include <iostream>\r\n\r\n\/*\r\nThis is the base class for executable program lines\r\n*\/\r\nclass Program{\r\npublic:\r\n\tvirtual void execute() const;\t\t\t\t\/\/ run this line of the program\r\n\tvirtual void list(std::ostream& os) const;\t\/\/ list this line\r\n};\r\n\r\n#endif<\/pre>\n
The implementation file is pretty self-explanatory, program.cpp<\/em>:<\/p>\n
#include \"program.h\"\r\n\r\n\/\/ nothing to do in the base class\r\nvoid Program::execute() const{\r\n}\r\n\r\n\/\/ if you ever see this, something is wrong\r\nvoid Program::list(std::ostream& os) const{\r\n\tos << \"GENERIC PROGRAM (SHOULDN'T SEE THIS)\";\r\n}<\/pre>\n
Since we decided to make the PRINT statement our first implemented BASIC call, we create a Print<\/em> subclass of Program<\/em>. Our PRINT statement will take in one or more Expression<\/em>s to print, and provides an implementation of the execute<\/em> and list<\/em> functions it inherits from Program<\/em>. Here is the header file print.h<\/em>:<\/p>\n
#ifndef _PRINT_H_\r\n#define _PRINT_H_\r\n\r\n#include <vector>\r\n\r\n#include \"program.h\"\r\n#include \"expression.h\"\r\n\r\nusing std::ostream;\r\n\r\n\/*\r\nThis is the implementation for the PRINT statement\r\n*\/\r\nclass Print : public Program {\r\npublic:\r\n\tPrint(const std::vector<Expression>& exprList);\t\/\/ create with a vector of expressions to print\r\n\r\n\tvirtual void execute() const;\t\t\t\t\t\/\/ print the expression\r\n\tvirtual void list(ostream& os) const;\t\t\t\/\/ list this statement\r\n\t\r\nprivate:\r\n\tstd::vector<Expression> exprList;\t\t\t\t\/\/ store the expressions here\r\n};\r\n\r\n#endif<\/pre>\n
Here is the source file, print.cpp<\/em>:<\/p>\n
#include <iostream>\r\n\r\n#include \"print.h\"\r\n\r\nusing std::endl;\r\nusing std::cout;\r\n\r\n\/\/ constructor for Print class\r\nPrint::Print(const std::vector<Expression>& exprList){\r\n\tthis->exprList = exprList;\r\n}\r\n\r\n\/\/ prints out each expression to std::cout\r\nvoid Print::execute() const{\r\n\tfor( int i = 0; i < exprList.size()-1; i++ ){\r\n\t\tcout << exprList[i].value() << ' ';\r\n\t}\r\n\tcout << exprList[exprList.size()-1].value() << endl;\r\n}\r\n\r\n\/\/ lists the expressions, as they were originally given\r\nvoid Print::list(ostream& os) const{\r\n\tos << \"PRINT \";\r\n\tfor( int i = 0; i < exprList.size()-1; i++ ){\r\n\t\tos << exprList[i].print() << \", \";\r\n\t}\r\n\tos << exprList[exprList.size()-1].print();\r\n}<\/pre>\n
The constructor takes a reference to a std::vector<Expression><\/em>, since we never modify anything once the statement has been created. The execute<\/em> function prints out the value of each Expression<\/em> in order, separated by commas. The list<\/em> function prints out the source definition of each Expression<\/em>.<\/p>\n
The last piece of the puzzle is the Expression<\/em> class. An Expression<\/em> at this stage will only be a text string, but will later include all data items, such as numbers, variables, functions, and operators. Here is the header file, expression.h<\/em>:<\/p>\n
#ifndef _EXPRESSION_H_\r\n#define _EXPRESSION_H_\r\n\r\n#include <string>\r\n\r\nusing std::string;\r\n\r\n\/*\r\nBase class used for storing and evaluating data items\r\n*\/\r\nclass Expression {\r\npublic:\r\n\tExpression(const char *text);\t\t\/\/ our first implementation will take a string as input\r\n\t\r\n\tconst string value() const;\t\t\t\/\/ return the stored value\r\n\tconst string print() const;\t\t\t\/\/ printable version\r\n\t\r\nprivate:\r\n\tstring text;\t\t\t\t\t\t\/\/ data storage\r\n};\r\n\r\n#endif<\/pre>\n
Note that once the object is created, the only accessor functions are declared const<\/em>, since they will will either evaluate, or print the value, but never change it. Here is the implementation, expression.cpp<\/em>:<\/p>\n
#include \"expression.h\"\r\n\r\n#include <iostream>\r\n\r\n\/\/ create a new Expression, storing its text\r\nExpression::Expression(const char *text){\r\n\tthis->text = std::string(text);\r\n}\r\n\r\n\/\/ return the text value\r\nconst string Expression::value() const{\r\n\treturn text;\r\n}\r\n\r\n\/\/ return a string for printing\r\nconst string Expression::print() const{\r\n\treturn '\"' + text + '\"';\r\n}\r\n<\/pre>\n
The constructor takes a c-style char *<\/em> and stores it in the C++ string<\/em> member variable text<\/em>. The function value<\/em> is designed to evaluate the expression, which for a string means simply returning the stored text<\/em>. The printable version, returned by print<\/em>, adds double quotes, to provide the original definition.<\/p>\n
Now that we have our implementation created, we need to update the scanning and parsing to take advantage of our new features. Let’s start with the updates we need to make to the Bison file. In the C Declarations<\/em> portion at the top, we need to include a couple more STL header files:<\/p>\n
#include <vector>\r\n#include <string><\/pre>\n
At the bottom of that section, we will include our new local header files:<\/p>\n
#include \"basic.h\"\r\n#include \"expression.h\"\r\n#include \"print.h\"\r\n#include \"program.h\"<\/pre>\n
We need to add one more token type to our available options in the Bison Declarations<\/em> section:<\/p>\n
\/\/ token type definition\r\n%union {\r\n\tint iVal;\r\n\tchar *sVal;\r\n\tProgram *progVal;\r\n}<\/pre>\n
Next, add a new terminal token for the LIST<\/em> operation:<\/p>\n
%token LIST<\/pre>\n
At this point we will begin needing token types defined for some of our non-terminal symbols. Add this to the end of your Bison declarations to declare that the program<\/em> non-terminal symbol will be of the type progVal<\/em>, defined above in the Bison union:<\/p>\n
\/\/ non-terminal symbols\r\n%type <progVal> program<\/pre>\n
The grammar rules start off the same, keeping the input<\/em> and line<\/em> definitions. However, we will be modifying the stmt<\/em> definition as follows:<\/p>\n
stmt:\r\n\tLINE program\t\t{ Basic::instance()->add($1, $2); }\r\n\t| RUN\t\t\t{ Basic::instance()->execute(); }\r\n\t| LIST\t\t\t{ Basic::instance()->list(); }\r\n;<\/pre>\n
This is where we begin making use of our new C++ classes. If the Bison parser matches a line number followed by a program rule, it will add it to the Basic<\/em> singleton instance. The $1<\/em> represents the LINE<\/em> token, which we defined to be of type intVal<\/em>, i.e., an int<\/em>. The $2<\/em> represents the program<\/em> non-terminal token, which we defined to be of type progVal<\/em>, i.e., a Program *<\/em>. This matches the signature for the Basic::add<\/em> member function: void add(int index, const Program *program)<\/em>, so the C++ call will succeed. Likewise, matching the terminal symbols RUN<\/em> or LIST<\/em> will result in calls to the Basic<\/em> singleton instance to run or list the stored program.<\/p>\n
Next, update the program<\/em> non-terminal symbol to match a PRINT<\/em> statement:<\/p>\n
program:\r\n\tPRINT STRING\t\t{\r\n\t\t\t\t\tExpression e($2);\r\n\t\t\t\t\tvector<Expression> v(1, e);\r\n\t\t\t\t\tfree($2);\t\/\/ malloced in basic.l\r\n\t\t\t\t\t$$ = new Print(v);\r\n\t\t\t\t}\r\n;<\/pre>\n
When Bison reads a PRINT<\/em> token followed by a STRING<\/em> token, it will create a new instance of the Expression<\/em> class, passing the string to its constructor. It then puts the Expression<\/em> instance into a vector<\/em>; frees the string (since we allocated space for it manually in flex); and creates a pointer to a new Print<\/em> instance, which is returned as the value of the entire program<\/em> non-terminal token, to be consumed above by the stmt<\/em> rule. Although our Print<\/em> class supports taking in a vector of multiple expression to print, for now in our parser we only support a single string.<\/p>\n
The remainder of the Bison input file, consisting of the main<\/em> and yyerror<\/em> functions, stays the same. Let’s take a look at the changes we made to the flex input file:<\/p>\n
%option noyywrap\r\n\r\n%{\r\n#include \r\n\r\n#define YY_DECL extern \"C\" int yylex()\r\n\r\n class Program;\r\n\r\n#include \"basic.tab.h\"\r\n\r\n%}\r\n\r\n%%\r\n\r\n[ \\t]+\t;\t\/\/ skip white space\r\n[0-9]+\t\t{ yylval.iVal = atoi(yytext); return LINE; }\r\n\\\"[^\\\"\\n]*\\\"\t{\t\/\/ remove the quote marks from either end\r\n\t\t\tyylval.sVal = (char *)malloc(sizeof(char)*strlen(yytext)-1);\r\n\t\t\tstrncpy(yylval.sVal, yytext+1, strlen(yytext)-2);\r\n\t\t\tyylval.sVal[strlen(yytext)-2] = '\\0';\t\/\/ terminate the string!\r\n\t\t\treturn STRING;\r\n\t\t}\r\nPRINT\t\t{ return PRINT; }\r\nRUN\t\t{ return RUN; }\r\nLIST\t\t{ return LIST; }\r\n\\n\t\treturn ENDL;\r\n\r\n%%<\/pre>\n
The first new line, %option noyywrap<\/em>, tells flex that it will not need to parse multiple input files. This removes the dependence on the flex library to be linked in, so we will remove that from the make file. Next, in the C declarations section, we put class Program;<\/em>. This is because the Bison type union now has a Program *<\/em> defined, which gets picked up in the file basic.tab.h<\/em> that we include. Since we don’t actually use that class inside flex, we just declare it instead of importing its header file. The next change is our string matcher. The regular expression is the same, but we want to remove the quotation marks from either end of what we read. So instead of duplicating the string, we copy out the inside, and then make sure to terminate the new string with a ‘\\0’<\/em>. The last new part is that we added a rule to match the LIST<\/em> statement.<\/p>\n
Of course, we also need to update the make file to include all the new header and source files we have created, and remove the flex library link:<\/p>\n
.PHONY: all clean\r\n\r\nall:\tbasic.tab.c lex.yy.c \\\r\n\t\tbasic.h basic.cpp \\\r\n\t\tprogram.h program.cpp \\\r\n\t\tprint.h print.cpp \\\r\n\t\texpression.h expression.cpp\r\n\tg++ basic.tab.c lex.yy.c program.cpp basic.cpp print.cpp expression.cpp -o basic\r\n\r\nbasic.tab.c: basic.y\r\n\tbison -d basic.y\r\n\t\r\nbasic.tab.h: basic.y\r\n\tbison -d basic.y\r\n\r\nlex.yy.c: basic.tab.h basic.l\r\n\tflex basic.l\r\n\r\nclean:\r\n\trm basic.tab.c basic.tab.h lex.yy.c basic<\/pre>\n
You can now make and run the new basic<\/em> application. Here is an example session:<\/p>\n
10 PRINT \"hello\"\r\n20 PRINT \"Hi\"\r\nRUN\r\nhello\r\nHi\r\nLIST\r\n10 PRINT \"hello\"\r\n20 PRINT \"Hi\"<\/pre>\n
The complete source files from this part are available here: https:\/\/github.com\/VisceralLogic\/basic\/tree\/part-2<\/a><\/p>\n
Continue to\u00a0Part III<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
This is a continuation of Part I. In Part II, we will add functionality to store and run BASIC programs, although still limited to the PRINT statement. We will also be adding a LIST statement to print out the currently stored program.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[12,16,13,15],"tags":[],"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9npkn-K","jetpack_likes_enabled":true,"jetpack-related-posts":[{"id":90,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-iv\/","url_meta":{"origin":46,"position":0},"title":"BASIC Interpreter, Part IV","date":"September 7, 2018","format":false,"excerpt":"This is a continuation of Part III. This time we will add some mathematical operators, the ability to save and load programs, and support numerical variables. To enable mathematical operations, we will create a subclass of DoubleExpression that takes two DoubleExpressions as inputs, as well as a character code signifying\u2026","rel":"","context":"In "BASIC"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":149,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-vii\/","url_meta":{"origin":46,"position":1},"title":"Basic Interpreter, Part VII","date":"September 7, 2018","format":false,"excerpt":"This is a continuation of Part VI. This time, we will be adding the FOR-NEXT loop and unary negation. The FOR-NEXT loop takes a couple forms: FOR  =  TO  ... NEXT  or FOR  =  TO  STEP  ... NEXT  In the former\u2026","rel":"","context":"In "BASIC"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":111,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-v\/","url_meta":{"origin":46,"position":2},"title":"BASIC Interpreter, Part V","date":"September 7, 2018","format":false,"excerpt":"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\u2026","rel":"","context":"In "BASIC"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":131,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-vi\/","url_meta":{"origin":46,"position":3},"title":"BASIC Interpreter, Part VI","date":"September 7, 2018","format":false,"excerpt":"This is a continuation of Part V. In the previous section, we added support for the GOTO statement. Since we don't yet have any control logic, that is not very useful, but it does lay the infrastructure for one of the features we will add this time: IF-THEN. We will\u2026","rel":"","context":"In "BASIC"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":72,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpeter-part-iii\/","url_meta":{"origin":46,"position":4},"title":"BASIC Interpeter, Part III","date":"September 7, 2018","format":false,"excerpt":"This is a continuation of Part II. In this part, we will add support for numerical as well as string expressions, support multiple expression in a PRINT statement, and add functionality for deleting program lines. Let's start with the Basic class header file, basic.h. All we need to do here\u2026","rel":"","context":"In "BASIC"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":39,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-i\/","url_meta":{"origin":46,"position":5},"title":"BASIC Interpreter, Part I","date":"September 7, 2018","format":false,"excerpt":"This is the first of a multi-post tutorial on using flex and Bison to write a programming language interpreter, in this case, BASIC. We'll be using the 1964 BASIC manual from Dartmouth as the starting point language reference. All code is available at this GitHub repository: https:\/\/github.com\/VisceralLogic\/basic. The interpreter will\u2026","rel":"","context":"In "BASIC"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/posts\/46"}],"collection":[{"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/comments?post=46"}],"version-history":[{"count":25,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/posts\/46\/revisions"}],"predecessor-version":[{"id":163,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/posts\/46\/revisions\/163"}],"wp:attachment":[{"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/media?parent=46"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/categories?post=46"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/tags?post=46"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}