8

我有兴趣通过实现基于堆栈的编程语言来扩展我的计算机编程知识。我正在寻求关于从哪里开始的建议，因为我打算让它具有像“ 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
4

2 回答 2

16

基于堆栈的语言（例如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>

这真的很简单。您可以摆弄程序并根据需要对其进行修改。祝你好运。

于 2012-12-13T02:36:20.283 回答
2

我想你会发现一篇关于“MetaII”的论文真的很有启发性。它在 10 个简短但令人费解的页面中展示了如何定义下推堆栈编译器机器及其编译器。看到这个答案：https ://stackoverflow.com/a/1005680/120163 一旦你理解了这一点，编写下推堆栈解释器将永远很容易。

于 2012-12-13T04:05:25.500 回答