Implementazione goto in uno

Question

Come progetto breve durante la pausa invernale, sto cercando di implementare un linguaggio di programmazione chiamato Ax (progettato per la creazione di grafici di calcolatrici) utilizzando Python e PLY. Una breve nota: il linguaggio consente solo variabili globali e fa un uso intensivo dei puntatori.

Sto cercando di implementare goto in questa lingua, ma non ho idea di come farlo.

Il mio metodo generale è di usare PLY per analizzare il codice in un ast, quindi eseguirlo mentre procedo.

Ad esempio, l'istruzione

If 3 
    Disp 4 
    Disp 6 
End 

... sarebbe trasformato in ...

['PROGRAM', 
    ['BLOCK', 
    ['IF', 
     ['CONDITION', 3], 
     ['BLOCK', 
     ['DISP', 4], 
     ['DISP', 6] 
     ] 
    ] 
    ] 
] 

... che vorrei eseguire in modo ricorsivo (ho aggiunto trattini per migliorare la leggibilità).

Poiché l'ast è un albero, non sono sicuro di come passare da un nodo all'altro. Ho preso in considerazione la possibilità di convertire l'albero in un array flat-ish ['IF', ['CONDITION', 3], ['DISP', 4], ['DISP', 6]] in modo da poter utilizzare gli indici dell'array flat-ish per andare a specifiche linee nel codice, ma questo sembra mancare di una certa eleganza e sembra quasi un fare un passo indietro (anche se potrei sbagliarmi).

Ho visto this, ma non sono riuscito a capire come funzionava.

Qualsiasi aiuto o suggerimento sarebbe apprezzato.

Answer 1

"esegui in modo ricorsivo" non si adatta bene a goto. Per il funzionamento di goto, è necessario un PC, un "contatore di programma" e ogni istruzione nel programma deve avere un indirizzo distinto. Mentre viene eseguito, l'indirizzo di ogni istruzione è assegnato al PC. Quando viene rilevato goto, l'indirizzo di destinazione del goto (il suo argomento) viene inserito nel PC e l'esecuzione riprende da lì.

Questo è quasi impossibile da ottenere con un approccio ricorsivo basato sullo stack. Sono disponibili due opzioni:

• appiattire l'AST in una sequenza in cui è possibile assegnare un indirizzo diverso per ogni dichiarazione

• Aggiungere una modalità di "saltare" al vostro interprete. Quando viene rilevato goto, lanciare un GotoException che esce da tutti i frame dello stack e torna alla radice. Elaborare le istruzioni (saltarle senza eseguire) finché non si raggiunge l'indirizzo di destinazione.

penso che si può immaginare che questa implementazione di goto non è molto performante e probabilmente fragili da implementare.

Answer 2

Ho preso in considerazione la possibilità di convertire l'albero in un array flat-ish ... ma questo sembra mancare di una certa eleganza e sembra quasi un passo indietro (anche se potrei sbagliarmi).

Si sbaglia. Il codice macchina è sempre piatto. Lingue come C sono appiattite per creare codice macchina.

Una calcolatrice (come altre macchine semplici) è piatta.

Tuttavia. L'appiattimento del proprio albero di sintassi AXE non è completamente necessario.

È sufficiente applicare le etichette della sorgente di programmazione a ciascun nodo nella struttura.

Quindi un "GOTO" cerca semplicemente l'albero per quell'etichetta e riprende l'esecuzione su quell'etichetta.

Answer 3

È inoltre possibile appiattire l'AST su un grafico diretto (il grafico del flusso di controllo). Un esempio di come questo può essere fatto per produrre un grafico networkx che può essere attraversato dall'interprete può essere trovato here. Nota che dovrai scrivere alcune classi AST per questo scopo.