{"id":39,"date":"2018-09-07T20:47:48","date_gmt":"2018-09-08T04:47:48","guid":{"rendered":"http:\/\/www.viscerallogic.com\/programming\/blog\/?p=39"},"modified":"2018-09-07T20:50:04","modified_gmt":"2018-09-08T04:50:04","slug":"basic-interpreter-part-i","status":"publish","type":"post","link":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-i\/","title":{"rendered":"BASIC Interpreter, Part I"},"content":{"rendered":"

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<\/a> from Dartmouth as the starting point language reference. All code is available at this GitHub repository: https:\/\/github.com\/VisceralLogic\/basic<\/a>. The interpreter will be written in C++.<\/p>\n

Why use flex\/Bison instead of writing everything from scratch?\u00a0 If you’ve written a parser\/grammar interpreter before (e.g.,\u00a0Numerical Expression Solver in Java<\/a>), you know that even a simple language can get involved.\u00a0 Leveraging flex and Bison allows you to focus on the core language implementation, and not have to re-invent the wheel for parsing.\u00a0Bison is a GNU utility for generating programs to parse a programmer-defined language grammar.\u00a0 A manual with tutorials is here:\u00a0http:\/\/dinosaur.compilertools.net\/bison\/index.html<\/a>.\u00a0Flex is a utility for reading input files and converting them into lexical tokens, useful for consumption by Bison.\u00a0 The same site has the manual and tutorial for flex: http:\/\/dinosaur.compilertools.net\/flex\/index.html<\/a><\/p>\n

Here is a good introduction to both flex and Bison, from which we will start our program: http:\/\/aquamentus.com\/flex_bison.html<\/a><\/p>\n

To start, we need to determine what the language features we need to implement are. The ’64 manual describes a non-interactive language, so that is where we will start. Programs will be entered one line at a time, with a line number at the beginning of each line, and then the program will be run. There is no interactive user input in this language.<\/p>\n

Example input:<\/p>\n

10 FOR X = 1 TO 100\r\n20 PRINT X, SQR(X)\r\n30 NEXT X\r\n40 END<\/pre>\n
Here are the 15 commands we will need to be able to interpret to offer a complete implementation:<\/p>\n
LET\r\nREAD\r\nDATA\r\nPRINT\r\nGOTO\r\nIF-THEN\r\nFOR\r\nNEXT\r\nEND\r\nSTOP\r\nDEF\r\nGOSUB\r\nRETURN\r\nDIM\r\nREM<\/pre>\n
We will start by creating a program that reads just two lines: either a line number followed by a PRINT command, or the RUN statement to execute the stored program. We will start by creating the flex and Bison input files to make sure we have the basics working.<\/p>\n
The flex input file will need to recognize a few different types of tokens: integers for a line number, strings delimited by double quotes, the literals PRINT and RUN, and new line characters. It will ignore other white spaces, and pass anything it doesn’t recognize on to the Bison parser. Here is the initial flex input file:<\/p>\n
%option noyywrap\r\n\r\n%{\r\n#include <cstdio>\r\nusing namespace std;\r\n\r\n#define YY_DECL extern \"C\" int yylex()\r\n\r\n#include \"basic.tab.h\"\r\n%}\r\n\r\n%%\r\n\r\n[ \\t]+\t;\t\t\/\/ skip white space\r\n[0-9]+\t\t\t{ yylval.iVal = atoi(yytext); return LINE; }\r\n\\\"[^\\\"\\n]*\\\"\t\t{ yylval.sVal = strdup(yytext); return STRING; }\r\nPRINT\t\t\t{ return PRINT; }\r\nRUN\t\t\t{ return RUN; }\r\n\\n\t\t\treturn ENDL;\r\n\r\n%%\r\n<\/pre>\n
The first section of the file is for definitions<\/em>, and comes before the first %%<\/em>. We denote C declarations with %{<\/em> and %}<\/em>, and everything inside those braces is ignored by flex and passed on to the C program it generates. The second section, coming after the first %%<\/em>, provides the flex rules<\/em>. Flex will follow whichever rule matches the most text, or if multiple match the same amount, the first of those rules.<\/p>\n
The first rule, [ \\t]+ ;<\/em>, matches one or more spaces or tabs, and silently discards them. The second rule, [0-9]+<\/em>, is designed for reading line numbers, and matches one ore more digits. It converts the text it has read into an integer using the atoi<\/em> function, and returns the LINE<\/em> token (which will be defined in the Bison input file. The next rule, \\”[^\\”\\n]*\\”<\/em>, matches strings; it looks for an initial double quote, and then reads all subsequent characters except a new line or double quote, until it reaches a closing double quote. This text is returned as-is, as a STRING<\/em> token. The rules PRINT<\/em> and RUN<\/em> match that text exactly, and return the corresponding token. The final rule, \\n<\/em>, reads a new line character and returns the ENDL<\/em> token.<\/p>\n
The Bison input file is a bit more complicated.\u00a0 It starts similarly in the first section with C declarations, and then token definitions.\u00a0 The second section contains the grammar rules.\u00a0 The final section contains additional C code, which in our initial iteration includes the <em>main<\/em> function definition:<\/p>\n
\/\/ A BASIC grammar interpreter\r\n\r\n%{\r\n#include <cstdio>\r\n#include <iostream>\r\nusing namespace std;\r\n\r\nextern \"C\" int yylex();\r\nextern \"C\" int yyparse();\r\nextern \"C\" FILE *yyin;\r\n\r\nvoid yyerror(const char *s);\r\n%}\r\n\r\n\/\/ token type definition\r\n%union {\r\n\tint iVal;\r\n\tchar *sVal;\r\n}\r\n\r\n\/\/ constant tokens\r\n%token PRINT\r\n%token RUN\r\n%token ENDL\r\n\r\n\/\/ terminal symbols\r\n%token <iVal> LINE\r\n%token <sVal> STRING\r\n\r\n%% \/* Grammar rules and actions follow *\/\r\n\r\ninput:\r\n\t\/* empty *\/\r\n\t| input line\r\n;\r\n\r\nline:\r\n\tENDL\r\n\t| stmt ENDL\r\n;\r\n\r\nstmt:\r\n\tLINE program\t\t{ cout << \"> Programming line \" << $1 << \" ^^^\" << endl; }\r\n\t| RUN\t\t\t{ cout << \"> running...\" << endl; }\r\n;\r\n\r\nprogram:\r\n\tPRINT STRING\t\t{ cout << \">\\tPRINT \" << $2 << endl; }\r\n;\r\n\r\n%%\r\n\r\nint main(int argc, char **argv){\r\n\tdo {\r\n\t\tyyparse();\r\n\t} while( !feof(yyin) );\r\n\t\r\n\treturn 0;\r\n}\r\n\r\nvoid yyerror(const char *s){\r\n\tcout << \"Error: \" << s << endl;\r\n}<\/pre>\n
Since we will be parsing tokens of multiple types, we use the %union<\/em> token definition. To start with, the only types whose value we need are integers (int iVal<\/em>) for line numbers, and strings (char *sVal<\/em>). The constant tokens PRINT<\/em>, RUN<\/em>, and ENDL<\/em>, do not need values, they represent themselves. The terminal symbols LINE<\/em> and STRING<\/em> use the token type values defined previously. These five tokens will be exported to the file basic.tab.h<\/em>, which is imported by the flex input file to maintain consistency in token definitions.<\/p>\n
Next is the grammar rules section, where the heart of the Bison file lies. The first rule defined is what Bison will attempt to match. It can be defined in terms of sub-rules. For our BASIC grammar, the primary rule is:<\/p>\n
input:\r\n\t\/* empty *\/\r\n\t| input line\r\n;<\/pre>\n
This means the non-terminal symbol input<\/em> matches either an empty input, or the non-terminal symbol input<\/em> followed by the non-terminal symbol line<\/em>. This is a recursive rule, which allows multiple lines to be read. For example, a line<\/em> non-terminal symbol matches this rule by being empty<\/em> (which is a valid input<\/em>) followed by a line<\/em>, so this matches the second case. This single line<\/em> symbol is therefore a valid input<\/em> symbol, and can be followed by another line<\/em> to again reduce to the second case.<\/p>\n
Our second rule defines the line<\/em> non-terminal symbol as either a blank line (represented by the terminal symbol ENDL<\/em> as read by our flex analyzer), or a stmt<\/em> non-terminal followed by the ENDL<\/em> terminal symbol. This ensures that we will be reading in one line of input at a time:<\/p>\n
line:\r\n\tENDL\r\n\t| stmt ENDL\r\n;<\/pre>\n
Things start to get a little more interesting with our third rule, for the stmt<\/em> symbol. We define this as either a line number (the terminal symbol LINE<\/em>) followed by a program<\/em> symbol, or the terminal symbol RUN<\/em>. In either case, we take an action to provide output as to what is being matched, so that we can verify what our program is doing:<\/p>\n
stmt:\r\n\tLINE program\t\t{ cout << \"> Programming line \" << $1 << \" ^^^\" << endl; }\r\n\t| RUN\t\t\t{ cout << \"> running...\" << endl; }\r\n;<\/pre>\n
Our final rule defines the single acceptable pattern to make a program<\/em> symbol: the terminal symbol PRINT<\/em> followed by a STRING<\/em>. If this is matched, we will provide feedback to that effect:<\/p>\n
program:\r\n\tPRINT STRING\t\t{ cout << \">\\tPRINT \" << $2 << endl; }\r\n;<\/pre>\n
The $N<\/em> entries in the actions of the last two rules represent the Nth<\/em> token being matched. As long as the token type has a value associated with it from the tokens declaration section, its value can be accessed.<\/p>\n
The final section of our Bison input file provides a simple main<\/em> function that calls the Bison-generated function yyparse()<\/em> until the input file (which defaults to stdin<\/em>) reaches the end, and an error function that is called when Bison is unable to successfully match a rule:<\/p>\n
int main(int argc, char **argv){\r\n\tdo {\r\n\t\tyyparse();\r\n\t} while( !feof(yyin) );\r\n\t\r\n\treturn 0;\r\n}\r\n\r\nvoid yyerror(const char *s){\r\n\tcout << \"Error: \" << s << endl;\r\n}<\/pre>\n
The program is now ready to be built and run. Since the flex input file depends on basic.tab.h<\/em>, we must first run Bison to generate this file. Call bison with the -d<\/em> option to generate the header file:<\/p>\n
> bison -d basic.y<\/pre>\n
This generates the two files basic.tab.c<\/em>, which contains the grammar parsing code, and basic.tab.h<\/em>, which defines the tokens for consumption by flex. Next run flex to generate the output file lex.yy.c<\/em>:<\/p>\n
> flex basic.l<\/pre>\n
Compile these with the g++<\/em> program:<\/p>\n
> g++ basic.tab.c lex.yy.c -o basic<\/pre>\n
Running these commands over and over can get tedious, and it is easy to forget to run one, especially as we add more files. So it will make your life easier to use a make<\/em> file, such as this one:<\/p>\n
.PHONY: all clean\r\n\r\nall: basic.tab.c lex.yy.c\r\n\tg++ basic.tab.c lex.yy.c -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
Save this as Makefile<\/em> in the same directory, and you can run it with the command make<\/em>. Call make clean<\/em> to remove all the generated files.<\/p>\n
Run your BASIC program by calling .\/basic<\/em> at the command line, type ctrl-D to generate an end-of-file signal to finish. You should be able to enter lines such as the following, with anything else printing a syntax error message:<\/p>\n
10 PRINT \"hello\"\r\n20 PRINT \"world\"\r\n00000 PRINT \"!\"\r\nRUN<\/pre>\n
If you enter the above lines, you should see the following output:<\/p>\n
10 PRINT \"hello\"\r\n>\tPRINT \"hello\"\r\n> Programming line 10 ^^^\r\n20 PRINT \"world\"\r\n>\tPRINT \"world\"\r\n> Programming line 20 ^^^\r\n00000 PRINT \"!\"\r\n>\tPRINT \"!\"\r\n> Programming line 0 ^^^\r\nRUN\r\n> running...\r\n<\/pre>\n
As you can see from the output, the program<\/em> non-terminal symbol is being matched and evaluated prior to the stmt<\/em> non-terminal symbol, resulting in the > PRINT “hello”<\/em> being printed before the > Programming line 10 ^^^<\/em>. You can also see that the input 00000<\/em> is being converted to the integer 0<\/em> by flex, and passed to Bison in that way.<\/p>\n
All the files used in this example are available for download here: https:\/\/github.com\/VisceralLogic\/basic\/tree\/part-1<\/a><\/p>\n
In the Part II<\/a>, we will begin expanding this program.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 be written in C++.<\/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-D","jetpack_likes_enabled":true,"jetpack-related-posts":[{"id":46,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-ii\/","url_meta":{"origin":39,"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":39,"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":72,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpeter-part-iii\/","url_meta":{"origin":39,"position":2},"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":111,"url":"https:\/\/www.viscerallogic.com\/programming\/blog\/basic-interpreter-part-v\/","url_meta":{"origin":39,"position":3},"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":39,"position":4},"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":39,"position":5},"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":[]}],"_links":{"self":[{"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/posts\/39"}],"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=39"}],"version-history":[{"count":8,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/posts\/39\/revisions"}],"predecessor-version":[{"id":161,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/posts\/39\/revisions\/161"}],"wp:attachment":[{"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/media?parent=39"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/categories?post=39"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.viscerallogic.com\/programming\/blog\/wp-json\/wp\/v2\/tags?post=39"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}