Как мне приступить к реализации простого языка программирования на основе стека?

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

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

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

Любые советы / критика приветствуются, и, пожалуйста, учтите, что я все еще достаточно новичок в программировании (я только недавно закончил 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

parsing lexer stack-based
person Wingpad    schedule 20.11.2012    source источник
comment
По совпадению, синтаксис вашего нового языка программирования очень похож на синтаксис языка программирования rebol.   -  person Anderson Green    schedule 14.06.2014
comment
@AndersonGreen этот синтаксис был фактически основан на кодах операций Adobe ActionScript Virtual Machine 2 (AVM2). Хотя Ребол смотрится интересно!   -  person Wingpad    schedule 15.06.2014

Ответы (2)


arrow_upward
15
arrow_downward

Язык на основе стека, такой как 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>

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

person Aadit M Shah    schedule 13.12.2012
comment
Спасибо за ваш ответ, он прояснил мои вопросы по этой проблеме. Я начал реализацию виртуальной машины на основе стека! - person Wingpad; 18.12.2012

arrow_upward
2
arrow_downward

Я думаю, вы найдете статью о «MetaII» действительно поучительной. Он показывает, как определить машину для компиляции стека с опусканием вниз и компилятор для нее, на 10 коротких, но умопомрачительных страницах. См. Этот ответ: https://stackoverflow.com/a/1005680/120163 Как только вы это поймете, напишите интерпретаторы стека pushdown навсегда будет легко.

person Ira Baxter    schedule 13.12.2012
comment
Кроме того, спасибо за ваш ответ, я прочитаю статью, на которую вы ссылаетесь, надеюсь, это поможет! - person Wingpad; 18.12.2012