This book is new. If you'd like to go through it, then join the Learn Code Forum to get help while you attempt it. I'm also looking for feedback on the difficulty of the projects. If you don't like public forums, then email email@example.com to talk privately.
Exercise 35: Interpreters
This final exercise in parsing should be both challenging and fun. You finally get to see your Puny Python script run and do something. It is quite alright to be struggling with this section and the concept of parsing. If you find that you've reached this point and you don't quite understand what's going on, take a step back and consider doing the exercises in this part again. Repeating this section a couple times before you continue will help you in the last two exercises where you make your own little languages.
I am purposefully not including any code in this exercise so that you have to attempt it based on the description of how an Interpreter works. You already have Python as a reference for how these little statements in our Puny Python example should operate. You know how to walk your parse tree with the visitor pattern. All that's left is for you to write an interpreter that can glue this all together and make your little script run.
Interpreters versus Compilers
In the world of programming languages you have languages that are interpreted, and ones that are compiled. A compiled language takes your input source and does the scanning, parsing, and analyzing phases like you've done here. A compiler then "emits" machine code based on this analysis by walking it and writing the bytes that a real computer (or fake one) needs to run the CPU. Some compilers add an additional step of translating the input source code to an "intermediate language" that is generic enough to then compile down to bytes for the machine. Compilers are normally identified because you typically can't just run them, but first you have to run the source through the compiler, then execute the result. C is a classic compiler, and you run a C program like this:
$ cc ex1.c -o ex1 $ ./ex1
The cc command is the "c compiler", and you're saying take the ex1.c file, scan, parse, and analyze it, then output the executable bytes to the ex1 file. Once you do that you then just run it like you would any other program.
An interpreter doesn't produce compiled bytecode that you run, but instead it just runs the result of the analysis directly. It is "interpreting" the input language the same way a bi-lingual person might interpret my English to my friend's Thai. It loads the source file, then scans, parses, and analyzes it just like a compiler does. Then it simply uses the interpreter's own language (in this case, Python) to run it based on the analysis.
- Scan 1 + 2 and produce tokens INT(1) PLUS INT(2).
- Parse that into an expression AddExpr(IntExpr(1), IntExpr(2).
- Analyze that to convert the text 1 and 2 into actual Python integers.
- Interpret that with the Python code result = 1 + 2, which I can pass to the rest of the parse tree.
By comparison, a compiler would do everything I did with 1-3, but then at 4 it would write bytecode (machine code) to another file, which I can then run on the CPU.
Python Is Both
Python is a bit more modern and takes advantage of faster computers by almost doing both compilation and interpretation. It will work like an interpreter so you don't have to go through a compilation phase. But, interpreters are notorioiusly slow, so Python has an internal virtual machine of sorts. When you run a script like python ex1.py, Python actually runs it and compiles that to a ex1.cpython-36.pyc file in the __pycache__ directory. That file is bytecode that the python program knows how to load and run, and it works kind of like fake machine code.
Your interpreter will never, and should never, be that fancy. Yours should just scan, parse, analyze, and interpret the Puny Python script.
How to Write an Interpreter
When you write an interpreter you are going to need to work between all three stages to fix things you missed or got wrong. I suggest that you get adding numbers to work first, then work on more complicated expressions until your script runs. I would appraoch it like this:
- Add your first interpret method to the AddExpr class and have it just print out a message.
- Get your Interpreter to visit this class reliably, passing in the PunyPyWorld it needs.
- Once you've got that you can get the AddExpr.interpret to do the job of calculating the addition of its two expressions and returning the result.
- After that you then have to figure out where the results of this interpret step should go. To keep things simple, let's assume Puny Python is an expression-based language, so everything returns a value. In that case, calls to one interpreter always have a return that parent calls can use.
- Finally, since Puny Python is expression-based, you can have your Interpreter print out the final result of its interpret call.
If you do that, you'll have the basics of your Interpreter, and you can start to implement all the other interpret methods you need to make this run.
Writing the Interpreter for Puny Python should involve nothing more than writing another visitor pattern that goes through the analyzed parse tree doing what the parse tree says to do. Your only goal is to get this one tiny (puny even) script to run. That seems stupid since this is just three lines of code, but it is three lines that covers a wide range of topics in programming languages: variables, addition, expression, function definitions, and function calls. If you implement if-statements you'd almost have a working programming language.
Your job is to write a PunyPyInterpreter class that takes the PunyPyWorld and the results of running PunyPyAnalyzer to execute the script. You're going to have to implement print as simply something that prints its variables, but the rest of the code should be something you run as you go through each production class.
- Once you have a PunyPyInterpreter, you should implement if-statements and boolean expressions and then expand your set of language tests to make sure this works. Try to push this little Python interpreter as far as you can go.
- What would it take to make Puny Python have statements too?
You should be able to now study the grammars and specifications for as many languages as you like. Go ahead and find some languages and study them, but do it using the source code to the language. You should also do a more complete study of the IETF ABNF specification at https://tools.ietf.org/html/rfc5234 to prepare you for the next two exercises.