Come implementare un linguaggio di programmazione semplice basato su stack

Question

Sono interessato ad estendere la mia conoscenza della programmazione per computer implementando un linguaggio di programmazione basato su stack. Sto cercando un consiglio su dove iniziare, poiché ho intenzione di avere funzioni come "pushint 1" che spingono un intero con valore 1 in cima allo stack e controllo del flusso tramite etichette come "L01: jump L01:".

Finora ho implementato un C# di ciò che voglio che il mio linguaggio agisca come (volevo collegarlo ma IDEOne è bloccato), ma è molto caotico e necessita di ottimizzazione. Traduce l'input in XML e poi lo analizza. I miei obiettivi sono di passare ad un linguaggio di livello inferiore, (forse C/C++) ma i miei problemi stanno implementando uno stack che può contenere vari tipi di dati e non ha una dimensione fissa.

Eventualmente vorrei anche implementare matrici e funzioni. Inoltre, penso di aver bisogno di un Lexer migliore e mi chiedo se un parsing tree sarebbe una buona idea per un linguaggio così semplicistico.

Qualsiasi consiglio/critica è il benvenuto, e per favore considera che sono ancora abbastanza nuovo per la programmazione (ho appena completato AP CompSci I). Inoltre, i collegamenti ai linguaggi basati su stack open source sono i benvenuti.

Ecco un programma di base che mi piacerebbe provare e interpretare/compilazione (dove [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 

Il risultato atteso sarebbe:

Hello World! 
1 
2 
3 
4 
5 
4 
3 
2 
1 

Answer 1

un linguaggio basato pila come Factor ha la seguente sintassi:

2 3 + 5 - print 

Questo è equ ivalent al seguente codice di stile C:

print(2 + 3 - 5); 

Il vantaggio di usare un linguaggio basato pila è che è semplice da implementare. Inoltre, se la lingua utilizza reverse polish notation, come la maggior parte dei linguaggi basati sullo stack, tutto ciò che serve per lo front end della tua lingua è un lexer. Non è necessario analizzare i token in un albero di sintassi poiché esiste un solo modo per decodificare il flusso di token.

Quello che stai cercando di creare non è un linguaggio di programmazione basato su stack, ma uno stack basato su virtual machine. Le macchine virtuali dell'applicazione possono essere sia stack based o register based. Ad esempio, lo Java Virtual Machine è basato sullo stack. Esegue Java bytecode (che è ciò che stai creando - bytecode per una macchina virtuale). Tuttavia, i linguaggi di programmazione che compilano questo codice byte (ad es. Java, Erlang, Groovy, ecc.) Non sono basati sullo stack.

Quello che stai cercando di creare è come il linguaggio a livello di assieme della tua macchina virtuale, che sembra essere basata sullo stack. Detto questo, sarà abbastanza facile farlo: le macchine virtuali basate su stack sono più facili da implementare su quelle macchine virtuali basate su registri. Di nuovo, tutto ciò che serve è un lexer come flex. Ecco un piccolo esempio in JavaScript utilizzando una libreria chiamata 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>

E 'davvero semplice. Puoi giocare con il programma e modificarlo in base alle tue esigenze.Buona fortuna.

Answer 2

Penso che troverete un documento su "MetaII" davvero illuminante. Mostra come definire un compilatore per stack di pushdown e un compilatore per esso, in 10 pagine brevi ma mind-bending. Vedi questa risposta: https://stackoverflow.com/a/1005680/120163 Una volta compreso questo, scrivere interpreti di stack di pushdown sarà semplicissimo.