Abstract Sintassi Albero con genitore o no? [chiuso]

0

La mia domanda è semplice come dice il titolo - dovrei implementare AST con il genitore o no?

Attualmente l'ho implementato con il genitore - il vantaggio di questo approccio è che, qualunque cosa io usi, posso andare su o giù senza problemi, tutto ciò di cui ho bisogno è un nodo. E anche le modifiche all'albero sono facili, perché sono locali per un determinato ramo.

Tuttavia ... quando guardo i profili, vedo che oltre il 40% del tempo viene speso per la clonazione dei nodi. Il clone è necessario, perché con il genitore non posso associare il nodo dato a più genitori.

L'opposto - nessun genitore - eliminerebbe la necessità di clonazione (almeno un uso così pesante), l'albero sarebbe più compatto (in realtà non sarebbe più albero, a causa dei nodi condivisi), ma forzerebbe Io uso una classe di navigatore gentile per tenere traccia dei nodi quando li attraverso, e aggiungerò un po 'di peso alla modifica dei rami (prima dovrei fare un clone locale :-) e poi modificarlo).

È difficile per me stimare quale approccio è migliore. Oh bene, forse c'è un terzo modo? Grazie in anticipo per l'aiuto.

    
posta greenoldman 20.11.2015 - 17:13
fonte

2 risposte

1

Il tuo problema immediato può essere risolto non memorizzando tipi di espressioni come nodi AST. Crea un tipo separato per i tipi. Questo può essere immutabile e senza riferimenti genitoriali, quindi non è necessario clonarlo. Non ci dovrebbero essere motivi per voler navigare da un tipo al suo tipo genitore. Evita anche che i tuoi tipi di espressioni portino con sé informazioni come la posizione del token che ha senso per i nodi AST, ma non per il tipo di espressione.

    
risposta data 20.11.2015 - 18:02
fonte
1

In generale, gli alberi non dovrebbero conoscere i loro genitori.

Mentre attraversi l'albero, puoi vedere tutti i bambini (e i loro figli, e così via) per sapere se hai bisogno di lavorare. Decidere quando si arriva ai bambini che è necessario tornare indietro è sciatto e rende molti algoritmi più difficili / complessi. E mantenendo la conoscenza in una direzione, riduci l'accoppiamento, con tutti i benefici che ciò comporta.

    
risposta data 21.11.2015 - 04:27
fonte

Leggi altre domande sui tag