Suponha que precisemos implementar um interpretador de bytecode simples. Que abordagem devemos escolher para implementar essa tarefa?
Estrutura de dados A pilha fornece a capacidade de implementar uma máquina de bytecode simples. Os recursos e implementações de máquinas stack são descritos em muitos artigos na Internet ocidental e doméstica. Apenas mencionarei que a máquina virtual Java é um exemplo de máquina stack.
O princípio de funcionamento da máquina é simples, um programa contendo dados e códigos de operação (opcodes) é fornecido à entrada e as operações necessárias são implementadas por meio de manipulações com a pilha. Vejamos um exemplo de programa de bytecode da minha máquina de pilha:
пMVkcatS olleHП
Na saída receberemos a string “Hello StackVM”. A máquina de pilha lê o programa da esquerda para a direita, carregando dados caractere por caractere na pilha quando um opcode aparece no símbolo – implementa o comando usando a pilha.
Exemplo de implementação de uma máquina stack em nodejs:
Notação polonesa reversa (RPN)
As máquinas Stack também são fáceis de usar para implementar calculadoras, para isso utilizam a notação polonesa reversa (notação postfix).
Exemplo de notação infixa regular:
2*2+3*4
Converte para RPN:
22*34*+
Para contar o registro postfix usamos uma máquina de pilha:
2– para o topo da pilha (pilha: 2)
2– para o topo da pilha (pilha: 2,2)
*– pegue o topo da pilha duas vezes, multiplique o resultado, envie para o topo da pilha (pilha: 4)
3– para o topo da pilha (pilha: 4, 3)
4– para o topo da pilha (pilha: 4, 3, 4)
*– pegue o topo da pilha duas vezes, multiplique o resultado, envie-o para o topo da pilha (pilha: 4, 12)
+– pegue o topo da pilha duas vezes, some o resultado, envie-o para o topo da pilha (pilha: 16)
Como você pode ver – o resultado das operações 16 permanece na pilha, ele pode ser impresso implementando opcodes de impressão da pilha, por exemplo:
p22*34*+P
P – Código de operação de início de impressão da pilha, p – opcode para finalizar a impressão da pilha e enviar a linha final para renderização.
Para converter operações aritméticas de infixo para pós-fixo, é usado o algoritmo de Edsger Dijkstra chamado “Sorting Yard”. Um exemplo da implementação pode ser visto acima, ou no repositório do projeto de pilha de máquinas nodejs abaixo.
Fontes
https:/ /tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись
Código fonte
https://gitlab.com/demensdeum/stackvm/< /p>