AST uitvoeren... maar niet recursief!

Status
Niet open voor verdere reacties.

That Guy

Meubilair
Lid geworden
28 nov 2006
Berichten
5.010
Al een tijd ben ik bezig met een interpreter schrijven in C++.
Ik heb 'm al aan de gang gekregen door recursief door de AST te lopen. Voor deze vraag kan er uit worden gegaan dat de taal welke uitgevoerd wordt JavaScript is.
Een voorbeeld van de AST tree (debug output):
test.cb.png
Deze AST wordt dan recursief uitgevoerd. Dit werkt allemaal prima; execute_block() maakt een nieuwe scope aan, called dan voor elk kind de correcte uitvoer-functie, en uiteindelijk komt de functie weer terug in execute_block(); welke dan de scope deleted.
(Voor de duidelijkheid is dit pseudo-code voor execute_block):
[CPP]Executer::execute_block()
{
Scope * scope = new Scope(); // maak een nieuwe scope voor dit block

foreach( child in AST )
{
execute_node( child );
}

delete scope; // wis de scope; we zijn klaar met alle variables in deze scope.
}[/CPP]
Zoals duidelijk zal zijn, heeft deze aanpak een hele grote hoeveelheid recursie. Een block kan in een ander block staan, et cetera. Maar goed, dat is geen probleem. Daarnaast: bij een execution error, throwt het programma een CodeRuntimeException.


Echter, met deze aanpak is er een probleem: het is onmogelijk* om 'dieper' te returnen. Bijvoorbeeld: een while-loop kan een if-statement hebben, waarin een continue of return of break statement staat:
[JS]while(true)
{
if( foo == bar )
{
if( baz == qux )
{
break;
}
}
}[/JS]
In de code wordt in de dieptste execute_if een break gezien; deze gaat echter niet over de if, maar over de while.

Ik had dit probleem allereerst opgelost door iets extreem naars te doen: exception throwing. I.e.: bij een while() wordt een try{} gezet, en als er een break ergens dieper zit, throwt deze een BreakException. Deze wordt opgevangen in de catch(BreakException){} van de while(), werkt dit prima.

Mijn punt is alleen dat dit niet echt subtiel is. Of netjes. Ja, het werkt, maar dit kan niet *de* oplossing zijn voor dit probleem (omdat er o.a. interpreters geschreven worden in talen die geen exceptions hebben).


De vraag: is er een andere manier om een AST uit te voeren? Ik had bedacht dat het kon door een globale 'current_node' welke naar een node in de AST wijst, en deze steeds uitvoeren. Echter, bij bijvoorbeeld een execute_block, gaat dit niet goedkomen: NA alle kinderen moet de cleanup-fase nog komen om de Scope te wissen.



* zo ver ik weet. Maar daar gaat deze vraag ook over.
 
Status
Niet open voor verdere reacties.

Nieuwste berichten

Terug
Bovenaan Onderaan