Стековый вычислитель -- вычислительное устройство выполняющее операций над элементами стека. Данные ВычМ удобны для вычисления выражений в постфиксной форме, так как на прямую интерпретируют выражения, и не требуют дополнительных регистров для хранения промежуточных результатов.
Рассмотрим описание стекового интерпретатора с таблицей символов и переходами.
Интерпретатор состоит из следующих частей.
STACK -- стек. Для реализации достаточно массива чисел с операциями push, pop, top.
SYMTAB -- таблица символов. Реализуется хеш-таблицей или массивом чисел, хранящим значение символа по соответствующему индексу
!!! Переход от имен к индексам осуществляет компилятор.
PROG -- программа. Массив чисел, где каждый элемент обозначает: число, символ или операцию, в зависимости от места.
!!! Так как символы и операции можно закодировать числами, то для представления программы достаточно числового вектора.
POS -- курсор. Индекс очередного интерпретируемого элемента.
Набор операций выполняемой интерпретатором:
!!! В скобках указано выталкиваемое содержимое стека, слева направо
- nop (<val>) -- не выполнять операцию, вытолкнуть содержимое стека,
- lit, <val> -- интерпретировать следующий элемент как литерал и добавить его в стек,
- set (sym, val) -- интерпретировать первый элемент стека как символ и в SYMTAB установить его значение равное второму элементу,
- get (sym) -- интерпретировать верхний элемент как символ и заменить его на его значение из SYMTAB
- if (else, then, cond) -- если третий элемент не равен 0, то оставить в стеке второй элемент, иначе первый
- jmp (pos) -- изменить значение POS на значение элемента стека
- add/sub/mul/div/mod (<val1>, <val2>) -- арифметические операции, первого элемента над вторым
- not/and/or/xor -- побитовые операции
- eq/ne/gt/lt/ge/le -- сравнения первого операнда со вторым
- halt -- остановка машины, если оператор не распознан.
Реализация на javascript
var prog = [
1,0x48, 1,0, 3,
1,0x65, 1,0, 3,
1,0x6c, 1,0, 3,
1,0x6c, 1,0, 3,
1,0x6f, 1,0, 3,
-1];//программа выводящая hello
function run(){
var stack= new Array();
var symtab = new Array();
var pos=0;
run:while(true){
let b = prog[pos++];
if(b === undefined) break;
switch(b){
case 0:{//nop (<val>)
stack.pop();
}break;
case 1:{//lit <val>
stack.push(prog[pos++]);
}break;
case 2:{//cp (<val>)
stack.push(stack[stack.length-1]);
}break;
case 3:{//set (<sym>,<val>)
let sym = stack.pop();
let val = stack.pop();
if(sym == 0) console.log(val+"\t("+ String.fromCharCode(val) +")");//OUT
else symtab[sym] = val;
}break;
case 4:{//get (<sym>)
let sym = stack.pop();
if(sym == 0) stack.push(parseInt(prompt()));//IN
else stack.push(symtab[sym]);
}break;
case 6:{//ifr (<else>, <then>, <cond>)
let els = stack.pop();
let thn = stack.pop();
let cond = stack.pop();
if(cond != 0) stack.push(thn);
else stack.push(els);
}break;
case 7:{//jmp (<pos>)
pos = stack.pop();
}break;
case 11:{//add (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
stack.push(a+b);
}break;
case 12:{//sub (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
stack.push(b-a);
}break;
case 13:{//mul (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
stack.push(a*b);
}break;
case 14:{//div (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
stack.push(b/a);
}break;
case 15:{//add (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
stack.push(a % b);
}break;
case 21:{//not (<opn1>)
let a = stack.pop();
stack.push(~a);
}break;
case 22:{//and (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
stack.push(a & b);
}break;
case 23:{//or (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
stack.push(a | b);
}break;
case 24:{//xor (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
stack.push(a ^ b);
}break;
case 31:{//eq (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
if(a == b)
stack.push(1);
else
stack.push(0);
}break;
case 32:{//ne (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
if(a != b)
stack.push(1);
else
stack.push(0);
}break;
case 33:{//gt (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
if(a > b)
stack.push(1);
else
stack.push(0);
}break;
case 34:{//lt (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
if(a < b)
stack.push(1);
else
stack.push(0);
}break;
case 35:{//ge (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
if(a >= b)
stack.push(1);
else
stack.push(0);
}break;
case 36:{//le (<opn1>, <opn2>)
let a = stack.pop();
let b = stack.pop();
if(a <= b)
stack.push(1);
else
stack.push(0);
}break;
default: break run;//halt
}
}
}