PScript Interpreter – Part 1 – Stack

I surpriced myself with how easy it was to implement the PScript Interpreter and would like to share the basic technique that I am using. The language is still under development, but the idea is to have a minimalistic Interpreter that can be used embedded so I need a very small footprint on the core language. Current tests indicate < 20Kb Flash and 1020 bytes SRAM as a minimum. In addition to that we obviously always have the text – the actual source code that is stored. But, as I target small scripts we actually store a lot in 1-2Kb text. And some of the MCU’s have quite a lot Flash/SRAM available. Lets annotate an example:

func test(uint32 v)
    print(v)
end
uint32 b
test(14)
for b=1 to 10
   test(b)
end

The example above is one of my small test scripts, and to illustrate the inside of the Interpreter I want to annotate stack usage and design. Each statement is a struct with variables and pointers that I need. So as I parse the statements I put these entries on a stack that basically is a 1Kb buffer as follows:

As I interpret “func” I add a func entry on the stack. Func body is parsed without execution.

Next I interpret “uint32 b” and insert the variable b on the stack.

Next I interpret “test(14)” and a call to function test is put on the stack. As this is outside a func we execute the function “test” with 14 as parameter.

What happens now is stack magic. I parse func test again and this time I add v as a parameter on the stack before I assign v the value of 14. v is now a variable with local scope inside the function.

Next I execute test by parsing and executing its body. The next statement is print and I do the same trick of calling print with the value 14. At this point we should get “14” printed out. Stack entry for print and parameter is removed after execution.

The next statement is “end” and as the previous stack entry now is the call to test and it’s parameters I now remove these from the stack and continue on the next line after the call to test. I am now only left with func and var b on the stack again.

Next I interpret the “for” statement and put that on the stack. For is now executed so b is assigned the value 1.

Next I interpret “test(b)” and set up a call to test using the current value of b as parameter. We now execute function “test” as illustrated before and will get the value 1 printed out.

Finally I reach “end” and with “for” being my previous entry I increment and test b with +1 until I reach the value 10. With b=10 I delete the for entry on the stack and continue. As we now are at the end of the script we are finished.

It might be details I need to change, but the key concept of the stack usage means that I can execute quite large scripts on very little SRAM usage. I bviously need sufficient stack to support functions and variables, but this simple technique is already working very well. And with a my MCU’s mostly being 168Mhz monsters it is quite fast as well. That said an Interpreter will always be slow compared to native code.

Leave a Reply