我将如何实现一个简单的基于堆栈的编程语言

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>

这很简单.您可以调整程序并根据需要进行修改.祝你好运.