Как бы я реализовал простой язык программирования на основе стека

Question

Я заинтересован в расширении моих знаний в области компьютерного программирования путем реализации стекового языка программирования. Я ищу совет о том, с чего начать, так как намерен, чтобы у него были такие функции, как "pushint 1"который поместил бы целое число со значением 1 в верхнюю часть стека и управлял потоком с помощью меток вроде"L01: jump L01:".

До сих пор я реализовал на C# то, что я хочу, чтобы мой язык действовал (хотел связать с ним, но IDEOne заблокирован), но он очень грязный и требует оптимизации. Он переводит ввод в XML и затем анализирует его. Мои цели - перейти на язык более низкого уровня (возможно, C/C++), но мои проблемы заключаются в реализации стека, который может содержать различные типы данных и не имеет фиксированного размера.

В конце концов я также хотел бы реализовать массивы и функции. Кроме того, я думаю, что мне нужен лучший Lexer, и мне интересно, будет ли дерево разбора хорошей идеей для такого упрощенного языка.

Любые советы / критика приветствуются, и, пожалуйста, учтите, что я все еще достаточно новичок в программировании (я только недавно закончил AP CompSci I). Также приветствуются ссылки на языки на основе стека с открытым исходным кодом.

Вот основная программа, которую я хотел бы попробовать интерпретировать / скомпилировать (где [this is a comment]):

[Hello World!]
pushchar    '\n'
pushstring  "Hello World!"
print
[Count to 5 and then count down!]
pushint     1
setlocal    0
L01:
pushchar    '\n'
getlocal    0
print           [print x + '\n']
getlocal    0
increment
setlocal    0   [x = x + 1]
pushint     5
getlocal    0
lessthan        [x < 5]
iftrue      L01
L02:
pushchar    '\n'
getlocal    0
print           [print x + '\n']
getlocal    0
decrement
setlocal    0   [x = x - 1]
pushint     0
getlocal    0
greaterthan     [x > 0]
iftrue      L02

Ожидаемый результат будет:

Hello World!
1
2
3
4
5
4
3
2
1

Answer 1

Язык на основе стека, такой как Factor, имеет следующий синтаксис:

2 3 + 5 - print

Это эквивалентно следующему коду стиля C:

print(2 + 3 - 5);

Преимущество использования стекового языка в том, что он прост в реализации. Кроме того, если язык использует обратную польскую нотацию, как это делает большинство языков, основанных на стеке, тогда все, что вам нужно для внешнего интерфейса вашего языка, - это лексер. Вам не нужно анализировать токены в синтаксическое дерево, так как есть только один способ декодировать поток токенов.

Вы пытаетесь создать не язык программирования на основе стека, а виртуальную машину на основе стека. Виртуальные машины приложений могут быть либо на основе стека, либо на основе регистров. Например, виртуальная машина Java основана на стеке. Он выполняет Java-байт-код (это то, что вы создаете - байт-код для виртуальной машины). Однако языки программирования, которые компилируются в этот байт-код (например, Java, Erlang, Groovy и т. Д.), Не основаны на стеке.

То, что вы пытаетесь создать, похоже на язык уровня сборки вашей собственной виртуальной машины, который основан на стеке. Тем не менее, это будет довольно легко сделать - виртуальные машины на основе стека проще реализовать с помощью виртуальных машин на основе регистра. Опять же, все, что вам нужно, это лексер, такой как flex. Вот небольшой пример в JavaScript с использованием библиотеки под названием lexer:

var program = "[print(2 + 3)]";
program += "\n push 2";
program += "\n push 3";
program += "\n add";
program += "\n print";

lexer.setInput(program);

var token;
var stack = [];
var push = false;

while (token = lexer.lex()) {
    switch (token) {
    case "NUMBER":
        if (push) stack.push(lexer.yytext);
        else alert("Unexpected number.");
        break;
    case "ADD":
        if (push) alert("Expected number.");
        else stack.push(stack.pop() + stack.pop());
        break;
    case "PRINT":
        if (push) alert("Expected number.");
        else alert(stack.pop());
        break;
    }

    push = token === "PUSH";
}

<script src="https://rawgit.com/aaditmshah/lexer/master/lexer.js"></script>
<script>
var lexer = new Lexer;

lexer.addRule(/\s+/, function () {
    // matched whitespace - discard it
});

lexer.addRule(/\[.*\]/, function () {
    // matched a comment - discard it
});

lexer.addRule(/\d+/, function (lexeme) {
    this.yytext = parseInt(lexeme);
    return "NUMBER";
});

lexer.addRule(/push/, function () {
    return "PUSH";
});

lexer.addRule(/add/, function () {
    return "ADD";
});

lexer.addRule(/print/, function () {
    return "PRINT";
});
</script>

Это действительно просто. Вы можете поиграть с программой и изменить ее в соответствии со своими потребностями. Удачи.

Answer 2

Я думаю, что вы найдете статью о "MetaII" действительно поучительной. Он показывает, как определить машину компилятора стека pushdown и компилятор для нее, на 10 коротких, но изнурительных страницах. Смотрите этот ответ: /questions/25407486/uchebnyie-resursyi-po-parseram-interpretatoram-i-kompilyatoram/25407526#25407526 Как только вы это поймете, написание интерпретаторов стека pushdown будет всегда легко.