{"id":72,"date":"2018-09-07T20:50:46","date_gmt":"2018-09-08T04:50:46","guid":{"rendered":"https:\/\/www.viscerallogic.com\/programming\/blog\/?p=72"},"modified":"2018-09-07T20:53:02","modified_gmt":"2018-09-08T04:53:02","slug":"basic-interpeter-part-iii","status":"publish","type":"post","link":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpeter-part-iii\/","title":{"rendered":"BASIC Interpeter, Part III"},"content":{"rendered":"

This is a continuation of Part II<\/a>. In this part, we will add support for numerical as well as string expressions, support multiple expression in a PRINT<\/em> statement, and add functionality for deleting program lines.
\n<\/p>\n

Let’s start with the Basic<\/em> class header file, basic.h<\/em>. All we need to do here is add a member function for deleting lines from the stored program:<\/p>\n

\tvoid remove(int index);\t\/\/ remove program line<\/pre>\n
For the class file, basic.cpp<\/em>, since we already have code in in the add<\/em> function to remove a line if it already exists, we will move that into the new remove<\/em> function, and then call remove<\/em> from add<\/em>. Here are the changes:<\/p>\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\tremove(index);\r\n\t\r\n\tlines.insert(std::pair<int, const Program *>(index, program));\r\n}\r\n\r\n\/\/ remove an existing line from the program\r\nvoid Basic::remove(int index){\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}\t\r\n}<\/pre>\n
The Program<\/em> base class doesn’t change at all. The derived Print<\/em> class has a minor change: we will be sub-classing Expression<\/em> to support numerical and string expressions, so we need to make its functions virtual and use pointers in the Print<\/em> class so the derived class member functions will be called. In the header file, print.h<\/em>, change the constructor signature to use Expression *<\/em>:<\/p>\n
\tPrint(const std::vector<Expression*> *exprList);\t\/\/ create with a vector of expressions to print<\/pre>\n
Also change the member variable declaration exprList<\/em> to match:<\/p>\n
\tconst std::vector<Expression*> *exprList;\t\/\/ store the expressions here<\/pre>\n
In the class file, print.cpp<\/em>, we have to update the method signatures to use pointers, and make a small change to how we access the elements in the vector. Because the elements are now pointers instead of actual objects, instead of using the array subscript method, we have to use the at()<\/em> function. Here is the updated class file:<\/p>\n
#include \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->at(i)->value() << ' ';\r\n\t}\r\n\tcout << exprList->at(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->at(i)->print() << \", \";\r\n\t}\r\n\tos << exprList->at(exprList->size()-1)->print();\r\n}<\/pre>\n
The Expression<\/code> class has a few changes. Since we will be creating subclasses of it, its member functions need to be virtual. Also, since we will only be using subclasses, we no longer need the member variable text<\/code>. 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\n\/*\r\nBase class used for storing and evaluating data items\r\n*\/\r\nclass Expression {\r\npublic:\r\n\tvirtual const std::string value() const;\t\t\t\/\/ return the stored value\r\n\tvirtual const std::string print() const;\t\t\t\/\/ printable version\r\n};\r\n\r\n#endif<\/pre>\n
The class file, expression.cpp<\/em>, likewise becomes simplified:<\/p>\n
#include \"expression.h\"\r\n\r\n\/\/ return the text value\r\nconst std::string Expression::value() const{\r\n\treturn std::string(\"BASE EXPRESSION\");\r\n}\r\n\r\n\/\/ return a string for printing\r\nconst std::string Expression::print() const{\r\n\treturn std::string(\"BASE EXPRESSION\");\r\n}<\/pre>\n
Our first subclass of Expression<\/code> is StringExpression<\/code>, which is basically the same as our original implementation of Expression<\/code>. Here is the header file, stringexpression.h<\/em>:<\/p>\n
#ifndef _STRINGEXPRESSION_H_\r\n#define _STRINGEXPRESSION_H_\r\n\r\n#include \"expression.h\"\r\n\r\n\/*\r\nClass used for storing a text value\r\n*\/\r\nclass StringExpression : public Expression {\r\npublic:\r\n\tStringExpression(const char *text);\t\t\/\/ take a string as input\r\n\t\r\n\tconst std::string value() const;\t\t\/\/ return the stored value\r\n\tconst std::string print() const;\t\t\/\/ printable version\r\n\t\r\nprivate:\r\n\tstd::string text;\t\t\t\t\/\/ data storage\r\n};\r\n\r\n#endif<\/pre>\n
Likewise, the implementation in stringexpression.cpp<\/em> duplicates the functionality of the old Expression<\/code> class:<\/p>\n
#include \"stringexpression.h\"\r\n\r\n\/\/ create a new StringExpression, storing its text\r\nStringExpression::StringExpression(const char *text){\r\n\tthis->text = std::string(text);\r\n}\r\n\r\n\/\/ return the text value\r\nconst std::string StringExpression::value() const{\r\n\treturn text;\r\n}\r\n\r\n\/\/ return a string for printing\r\nconst std::string StringExpression::print() const{\r\n\treturn '\"' + text + '\"';\r\n}\r\n<\/pre>\n
The class DoubleExpression<\/code> is very similar to StringExpression<\/code>, with the only difference being it stores a numerical value instead of a string value. Here is the header file, doubleexpression.h<\/em>:<\/p>\n
#ifndef _DOUBLEEXPRESSION_H_\r\n#define _DOUBLEEXPRESSION_H_\r\n\r\n#include \"expression.h\"\r\n\r\n\/*\r\nClass used for storing a numerical value\r\n*\/\r\nclass DoubleExpression : public Expression {\r\npublic:\r\n\tDoubleExpression(double d);\t\t\t\/\/ take a double as input\r\n\t\r\n\tconst std::string value() const;\t\t\/\/ return the stored value\r\n\tconst std::string print() const;\t\t\/\/ printable version\r\n\t\r\nprivate:\r\n\tdouble d;\t\t\t\t\t\/\/ data storage\r\n};\r\n\r\n#endif<\/pre>\n
The implementation file, doublexpression.cpp<\/em>, is naturally also very similar. Note that since printable version for calling LIST<\/code> on a numerical expression is the same as its text value, the print<\/code> function simply makes a call to value<\/code>:<\/p>\n
#include \"doubleexpression.h\"\r\n\r\n\/\/ create a new DoubleExpression, storing its value\r\nDoubleExpression::DoubleExpression(double d){\r\n\tthis->d = d;\r\n}\r\n\r\n\/\/ return the text value\r\nconst std::string DoubleExpression::value() const{\r\n\treturn std::to_string(d);\r\n}\r\n\r\n\/\/ return a string for printing\r\nconst std::string DoubleExpression::print() const{\r\n\treturn value();\r\n}<\/pre>\n
OK, now that we’ve got our classes set up, let’s update our Bison input file. The first change is to add our two new header files in the C declarations section:<\/p>\n
#include \"stringexpression.h\"\r\n#include \"doubleexpression.h\"<\/pre>\n
Next, in the Bison declarations, we need to add some new token types to the %union<\/em>. We need to support reading double<\/code>s, Expression *<\/code>s, and std::vector<Expression*> *<\/code>s:<\/p>\n
%union {\r\n\tint iVal;\r\n\tdouble dVal;\r\n\tchar *sVal;\r\n\tProgram *progVal;\r\n\tExpression *eVal;\r\n\tstd::vector<Expression*> *eList;\r\n}<\/pre>\n
Since we will now be able to enter a comma-separated list of expressions for the PRINT<\/code> statement, we need to add a new constant token:<\/p>\n
%token COMMA<\/pre>\n
We also have a new terminal symbol token type for reading doubles:<\/p>\n
%token <dVal> DOUBLE<\/pre>\n
And we will round out the Bison declarations with two new non-terminal symbols to use our single expression and expression list types:<\/p>\n
%type <eList> exprList\r\n%type <eVal> expr<\/pre>\n
Now that we’ve got the symbol types defined, we need to update the grammar rules. The input<\/code> and line<\/code> rules remain the same, but we will change the program<\/code> rule and add two new rules for reading expressions: exprList<\/code> and expr<\/code>. Here are the new rules:<\/p>\n
stmt:\r\n\tLINE\t\t\t{ Basic::instance()->remove($1); }\r\n\t| LINE 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;\r\n\r\nprogram:\r\n\tPRINT exprList\t\t{ $$ = new Print($2); }\r\n;\r\n\r\nexprList:\r\n\texpr\t\t\t{ $$ = new std::vector<Expression*>(1, $1); }\r\n\t| exprList COMMA expr\t{\r\n\t\t\t\t\t$1->push_back($3);\r\n\t\t\t\t\t$$ = $1;\r\n\t\t\t\t}\r\n;\r\n\r\nexpr:\r\n\tSTRING\t\t\t{\r\n\t\t\t\t\t$$ = new StringExpression($1);\r\n\t\t\t\t\tfree($1);\t\/\/ malloced in basic.l\r\n\t\t\t\t}\r\n\t| DOUBLE\t\t{ $$ = new DoubleExpression($1); }\r\n;<\/pre>\n
We have added one new option to the stmt<\/code> rule: a single LINE<\/code> terminal symbol can be input to delete that line from the stored program. The program<\/code> rule is simpler now: it reads a PRINT<\/code> symbol followed by a new non-terminal symbol exprList<\/code>, which we defined in our Bison declarations section to be of type std::vector<Expression*> *<\/code>. We can pass this symbol to our updated Print<\/code> constructor.<\/p>\n
Now we have our new rules. The exprList<\/code> rule is satisfied by either a single expr<\/code>, or by recursion a sequence of expr<\/code>s separated by commas (the terminal symbol COMMA<\/code> we added). When Bison encounters the first matching expr<\/code>, it creates a new std::vector<Expression *><\/code>, which matches the eList<\/code> symbol type we defined, and populates it with the single Expression<\/code> it read. As additional expression separated by commas are matched, they are pushed onto the end of the vector (the exprList<\/code> symbol in the first matching position), and then that vector is set as the result of the rule.<\/p>\n
The expr<\/code> rule matches either a STRING<\/code> or a DOUBLE<\/code> terminal symbol, and builds the appropriate Expression<\/code> derived class, as appropriate. For the case of the string, we again need to free the terminal symbol value, since we explicitly allocated it in the flex scanner.<\/p>\n
Something that would be nice is if we had a prompt character at the beginning of each input line when running our BASIC interpreter, to make the input and output lines a little more distinguishable. So, in the main<\/code> function, before the while<\/code> loop, print out a welcome statement (we will change the flex scanner so that it will print out another prompt character every time it reads a new line):<\/p>\n
\tstd::cout << \"Welcome to BASIC!\\n>\";<\/pre>\n
OK, on to the flex scanner! We need to add support for the new terminal symbols we added in Bison, as well as a couple other minor changes. First, it gets annoying having to enter the BASIC commands using capital letters. Fortunately for us, flex provides an option to make the input matching case-insensitive, so we don’t need to redefine our rules; simply add the case-insensitive<\/code> option to the first line:<\/p>\n
%option noyywrap case-insensitive<\/pre>\n
We’re going to be doing some printing directly from our flex scanner now, so be sure to include iostream<\/code>. We also have defined a token type that uses std::vector<\/code>, so we need to include that header:<\/p>\n
#include <iostream>\r\n#include <vector><\/pre>\n
The next change is to add a declaration of the Expression<\/code> class, since it is used in the symbol type definitions that Bison exports. The flex code never uses this class, so instead of including its header file, we just declare it:<\/p>\n
class Program;\r\nclass Expression;<\/pre>\n
Since we now need to be able to read in a double-type numerical value, we will be using the pattern [0-9]<\/code> many times, so we will create a flex declaration to use DIGIT<\/code> in its place. While this isn’t necessary, it can make the patterns a little more clear. Put this line after the end of the C declarations (%}<\/code>) and before the start of the pattern matching (%%<\/code>):<\/p>\n
%}\r\n\r\nDIGIT    [0-9]\r\n\r\n%%<\/pre>\n
Now we can use the pattern {DIGIT}<\/code> wherever we would use [0-9]<\/code>. We will make use of this for both the LINE<\/code> symbol and the DOUBLE<\/code> symbol. Here are the updated rules:<\/p>\n
[ \\t]+\t;\t\/\/ skip white space\r\n^{DIGIT}+\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\n(({DIGIT}+\".\"?)|(\".\"{DIGIT}+)){DIGIT}*(E-?{DIGIT}+)?\t{ yylval.dVal = atof(yytext); return DOUBLE; }\r\nPRINT\t\t{ return PRINT; }\r\nRUN\t\t{ return RUN; }\r\nLIST\t\t{ return LIST; }\r\n,\t\t{ return COMMA; }\r\n\\n\t\t{ std::cout << \">\"; return ENDL; }\r\n.\t;\t\/\/ skip any characters that aren't part of a recognized pattern<\/pre>\n
The updated rule that matches a LINE<\/code> symbol now requires the sequence of digits to be at the beginning of a line. This ensure that flex won’t match a numerical expression and return it as a LINE<\/code> symbol.<\/p>\n
The new rule for matching a DOUBLE<\/code> is a little bit tricky. There are two ways to start this pattern: either one or more digits followed by an optional dot, or a starting dot followed by one or more digits. After the start, there may be zero or more digits, optionally followed by a literal E<\/em> with an optional minus sign followed by one or more digits. Essentially, this rule requires that there be one or more digits, on either side of an optional
\ndot, and support for exponential notation followed. Here are some examples of inputs that this will match:<\/p>\n
123\r\n123.\r\n.123\r\n123.123\r\n123E123\r\n123E-123\r\n123.123E-123\r\n.123E-123\r\netc.<\/pre>\n
Since we have a new COMMA<\/code> terminal symbol defined in Bison to support comma-separated expression lists, we need to match that here (line 32). Since we want to have a prompt character show up at the beginning of each new input line, we updated the ENDL<\/code> match to print one out every time we read a new line character. Lastly, we have a new rule, .+ ;<\/code>, which silently reads and discards any characters that it can’t match to previous rules; this prevents some unwanted input for reaching Bison, where it could cause a parsing error.<\/p>\n
And of course, we need to update our makefile to include our new header and source files. I’ve been compiling on macOS, but on Linux we also need to tell g++ to use the C++11 standard, by adding the -std=c++11<\/code> argument. Here is the updated all<\/code> rule:<\/p>\n
all:\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\t\tstringexpression.h stringexpression.cpp \\\r\n\t\tdoubleexpression.h doubleexpression.cpp\r\n\tg++ -std=c++11 basic.tab.c lex.yy.c program.cpp basic.cpp print.cpp expression.cpp \\\r\n\tstringexpression.cpp doubleexpression.cpp \\\r\n\t-o basic<\/pre>\n
Here is an example session made from this Part III code:<\/p>\n
Welcome to BASIC!\r\n>10 print \"Hello\"\r\n>20 print 123, .123, 123.123E123\r\n>30 print \"Big Number!\"\r\n>list\r\n10 PRINT \"Hello\"\r\n20 PRINT 123.000000, 0.123000, 123122999999999995047514223697997329420208162078904722947470938484432926767618625996126391524302018196895898346062018145943552.000000\r\n30 PRINT \"Big Number!\"\r\n>run\r\nHello\r\n123.000000 0.123000 123122999999999995047514223697997329420208162078904722947470938484432926767618625996126391524302018196895898346062018145943552.000000\r\nBig Number!\r\n>20\r\n>list\r\n10 PRINT \"Hello\"\r\n30 PRINT \"Big Number!\"\r\n>run\r\nHello\r\nBig Number!\r\n><\/pre>\n
As you can see, we’ll want to clean up the numerical printing a bit, but otherwise, things are looking good! The complete source files from this part are available here: https:\/\/github.com\/VisceralLogic\/basic\/tree\/part-3<\/a><\/p>\n
Continue to\u00a0Part IV<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
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.<\/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-1a","jetpack_likes_enabled":true,"jetpack-related-posts":[{"id":46,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-ii\/","url_meta":{"origin":72,"position":0},"title":"BASIC Interpreter, Part II","date":"September 7, 2018","format":false,"excerpt":"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. We will be adding a number of new\u2026","rel":"","context":"In "BASIC"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":90,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-iv\/","url_meta":{"origin":72,"position":1},"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":111,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-v\/","url_meta":{"origin":72,"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":72,"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":149,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-vii\/","url_meta":{"origin":72,"position":4},"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":39,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-i\/","url_meta":{"origin":72,"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\/72"}],"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=72"}],"version-history":[{"count":21,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/posts\/72\/revisions"}],"predecessor-version":[{"id":165,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/posts\/72\/revisions\/165"}],"wp:attachment":[{"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/media?parent=72"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/categories?post=72"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/tags?post=72"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}