我将如何实现一种简单的基于堆栈的编程语言 [英] How would I go about Implementing A Simple Stack-Based Programming Language

问题描述

我有兴趣通过实现基于堆栈的编程语言来扩展我的计算机编程知识.我正在寻找关于从哪里开始的建议，因为我打算让它具有"pushint 1"之类的功能，该功能会将具有值1的整数压入堆栈的顶部，并通过"L01: jump L01:"之类的标签进行流控制.

I am interested in extending my knowledge of computer programming by implementing a stack-based programming language. I am seeking out advice on where to begin, as I intend for it to have functions like "pushint 1" which would push an integer with value 1 on to the top of the stack and flow-control via labels like "L01: jump L01:".

到目前为止，我已经实现了我希望我的语言表现出来的C#实现(希望链接到它，但是IDEOne被阻止了)，但是它非常混乱并且需要优化.它将输入转换为XML，然后对其进行解析.我的目标是使用较低级的语言(也许是C/C ++)，但是我的问题是实现一个可容纳各种数据类型且大小不固定的堆栈.

So far I have made a C# implementation of what I want my language to act like (wanted to link to it but IDEOne is blocked), but it is very messy and needs optimization. It translates the input to XML and then parses it. My goals are to go to a lower level language, (perhaps C/C++) but my issues are implementing a stack that can hold various data types and does not have a fixed size.

最终我也想实现数组和函数.另外，我认为我需要一个更好的Lexer，我想知道解析树对于这样一种简单的语言是否是一个好主意.

Eventually I would also like to implement arrays and functions. In addition, I think that I need to have a better Lexer and I am wondering if a parsing-tree would be a good idea for such a simplistic language.

欢迎提出任何建议/批评，请考虑我对编程还是相当陌生的(我最近刚完成AP CompSci I).另外，欢迎使用开放源代码的基于堆栈的语言的链接.

Any advice/criticism is welcome, and please consider that I am still reasonably new to programming (I have just recently completed AP CompSci I). Also, links to open-source stack-based languages are welcome.

这是我想尝试解释/编译的基本程序(其中[this is a comment]):

Here is a basic program that I would like to try and interpret/compile (where [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

推荐答案

基于堆栈的语言，例如因子具有以下语法:

A stack based language such as Factor has the following syntax:

2 3 + 5 - print

这等效于以下C样式代码:

This is equivalent to the following C style code:

print(2 + 3 - 5);

使用基于堆栈的语言的优点是易于实现.此外，如果该语言使用反向波兰符号，就像大多数基于堆栈的语言一样，那么

The advantage of using a stack based language is that it's simple to implement. In addition if the language uses reverse polish notation, as most stack based languages do, then all you need for the front end of your language is a lexer. You don't need to parse the tokens into a syntax tree as there's only one way to decode the stream of tokens.

您要创建的不是基于堆栈的编程语言，而是基于堆栈的虚拟机.应用程序虚拟机可以是基于堆栈的或基于注册的.例如， Java虚拟机基于堆栈.它执行 Java字节码(这就是您正在创建-虚拟机的字节码).但是，编译为此字节码的编程语言(例如Java，Erlang，Groovy等)不是基于堆栈的.

What you're trying to create is not a stack based programming language, but a stack based virtual machine. Application virtual machines can be either stack based or register based. For example, the Java Virtual Machine is stack based. It executes Java bytecode (which is what you're creating - bytecode for a virtual machine). However the programming languages that compile to this bytecode (e.g. Java, Erlang, Groovy, etc.) are not stack based.

您要创建的内容就像您自己的虚拟机的汇编级语言一样，该语言恰好是基于堆栈的.话虽如此，这样做会相当容易-基于堆栈的虚拟机更易于实现基于寄存器的虚拟机.同样，您只需要一个词法分析器，例如 flex .这是一个使用JavaScript的小示例，该JavaScript使用名为 lexer

What you're trying to create is like the assembly level language of your own virtual machine, which happens to be stack based. That being said it'll be fairly easy to do so - stack based virtual machines are easier to implement that register based virtual machines. Again, all you need is a lexer such as flex. Here's a small example in JavaScript using a library called 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>

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

It's really simple. You can fiddle with the program and modify it to your needs. Best of luck.

这篇关于我将如何实现一种简单的基于堆栈的编程语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！