(Alberi di sintassi) ricorsivamente iterazione di alberi bottom-up con percorso di corrente top-down

Question

Ho un albero sintassi astratta, che ho bisogno di iterare. L'AST è generato dal a PHP .

Ora "normalmente", lo farei con il nuovo e brillante (PHP 5.3.1) classi SPL, e sarebbe simile a questa:

$it = new \RecursiveIteratorIterator(
  new \RecursiveArrayIterator($ast['rule']),
  \RecursiveIteratorIterator::SELF_FIRST);

In realtà, questo è quello che sto già facendo in un'altra parte del codice che si determina un tipo di massima dell'intero albero (cioè può essere un incarico, una condizione, ecc). Ora Dettagli a parte, l'unica cosa importante è l'iterazione è fatto RecursiveIteratorIterator :: SELF_FIRST, vale a dire, dall'alto verso il basso.

Tornando al mio problema, ho bisogno di iterare l'AST basso verso l'alto, cioè, qualcosa di simile RecursiveIteratorIterator :: CHILD_FIRST, al fine di fare alcune sostituzioni e ottimizzazioni nella struttura.

Il problema è che queste operazioni devono essere sensibili al contesto, cioè devo il percorso verso il nodo corrente. E siccome voglio iterare bottom-up, non posso avere che con RecursiveIteratorIterator.

Bene pensarci per un secondo. Voglio iterare ascendente e avere contesto top-down (una pila) del nodo corrente, ad ogni iterazione. Tecnicamente dovrebbe essere possibile, poiché RecursiveIteratorIterator deve prima andare alla coda dell'albero, per scorrere all'indietro. Nel suo cammino verso la coda, si potrebbe memorizzare nella cache la posizione corrente, e semplicemente saltar fuori elementi come si ritorna indietro da ricorsione.

Ora, questa è una parola chiave: caching . Questo è il motivo per cui ho il sospetto che dovrebbe essere possibile con un'altra classe SPL:. RecursiveCachingIterator

La domanda è: è davvero possibile? Se sì, come?

Ho cercato di decifrare in giro con un po 'di codice, senza successo, e la documentazione è scarsa. Davvero, davvero scarse.

Chi avrà trovato la soluzione più elegante a questo utilizzando SPL, tanto di cappello! Sei un guru PHP!

PS: nel caso in cui non si capisce bene, sto cercando il più SPL ( re ) utilizzo il più possibile . So che avrei potuto scrivere le mie funzioni ricorsive con uno stack personalizzato, non c'è bisogno di ricordare a me di questo.

Answer 1

Sono riuscito a farlo funzionare ereditando RecursiveIteratorIterator e la gestione dello stack in :: endChildren () e :: callGetChildren rispettivamente. Forse questo aiuterà qualcuno. Tanto di cappello a me: -)