シンプルなスタックベースのプログラミング言語を実装するにはどうすればいいですか

Question

私はスタックベースのプログラミング言語を実装してコンピュータプログラミングの知識を広げることに興味があります。スタックの先頭に値1の整数を、「L01: jump L01:」のようなラベルでフロー制御をプッシュする「pushint 1」のような機能を持つことを意図しているので、どこから始めるべきかアドバイスを求めています。

これまでのところ、私は自分の言語のように動作させたい（IDEOneはブロックされていましたが）、C＃の実装を行っていますが、非常に面倒で最適化が必要です。入力を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 

Answer 1

のようなスタックベースの言語Factorの構文は次のとおりです。

2 3 + 5 - print 

これはequ次のCスタイルのコードと同義です。

print(2 + 3 - 5); 

スタックベースの言語を使用する利点は、実装が簡単だということです。さらに、言語がreverse polish notationを使用する場合、ほとんどのスタックベースの言語と同様に、あなたの言語のfront endに必要なのはレクサーです。トークンのストリームをデコードする唯一の方法があるので、トークンを構文木に解析する必要はありません。

作成しようとしているのはスタックベースのプログラミング言語ではなく、スタックベースのvirtual machineです。アプリケーション仮想マシンは、stack basedまたはregister basedのいずれかになります。たとえば、Java Virtual Machineはスタックベースです。 Java bytecode（仮想マシン用のバイトコード）を実行します。しかし、このバイトコード（Java、Erlang、Groovyなど）でコンパイルするプログラミング言語はスタックベースではありません。

作成しようとしているのは、自分の仮想マシンのアセンブリレベル言語のようなものです。これは、スタックベースのものです。スタックベースの仮想マシンは、レジスタベースの仮想マシンを実装する方が簡単です。ここでもまた必要なのは、flexのようなレクサーです。ここでlexerと呼ばれるライブラリを使用してJavaScriptで小さな例です：

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"についての論文を実際に啓発していると思います。これは、10個の短くて心が曲がるページで、プッシュダウンスタックコンパイラマシンとそのコンパイラを定義する方法を示しています。この回答を見るhttps://stackoverflow.com/a/1005680/120163これを理解すれば、プッシュダウンスタックインタプリタの作成はずっと簡単になります。