Stack Machine and RPN

Let’s say we need to implement a simple bytecode interpreter, which approach to the implementation of this task to choose?

Stack data structure provides an opportunity to implement a simple bytecode machine. Features and realization of machines stack described in numerous articles of Western and domestic Internet, just mention that the Java virtual machine is an example of a stack machine.

The principle of operation of the machine is simple, the input is a program containing data and opcodes (opcodes), using the stack manipulations performed realization of necessary operations. Consider the example of the program bytecode my stack machine:

 
пMVkcatS olleHП
 

At the output we get the string “Hello StackVM”. Stack machine reads the program from left to right, character by character by uploading data onto the stack, with the appearance of the opcode to symbol – performs implementation team using the stack.

An example of the implementation of the stack machine to nodejs:

Reverse polish notation (RPN)

Also, stacking machine is easy to use for the implementation of calculators, this is done using RPN (postfix notation).
An example of a conventional infix:
2*2+3*4

Converted into RPN:
22*34*+

To calculate postfix notation use a stack machine:
2 – at the top of the stack (stack 2)
2 – on top of the stack (Stack: 2.2)
* – get the top of the stack twice, multiply the result is sent to the top of the stack (stack of 4)
3 – on top of the stack (the stack 4, 3)
4 – on top of the stack (a stack of 4, 3, 4)
* – get the top of the stack twice, multiply the result is sent to the top of the stack (stack of 4, 12)
+ – get the top of the stack twice, add up the results, go to the top of the stack (stack 16)

As you can see – the result of operations 16 remains on the stack, it can be derived by implementing opcodes stack printing, for example:
п22*34*+П

П – print start opcode stack, n – opcode closure print stack and sending the final line in rendering.
For conversion from arithmetic operations in postfix infix used Edsger Dijkstra algorithm called “Shunting-yard algorithm”. An example implementation can be found above or in the project repository on the machine stack nodejs below.

References

https://tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись

Source Code

https://gitlab.com/demensdeum/stackvm/

0