Implementazione C++ n-ary tree per l'analisi della discesa ricorsiva

Question

Sono ancora un po 'nuovo in C++, quindi portami con me. Sto implementando un interprete per un linguaggio ipotetico chiamato Core che è descritto da una grammatica BNF. Finora ho implementato un tokenizer che mi dà una bella coda di token che rappresentano un programma Core. Sono ora in procinto di scrivere Parser/Executer che prende l'output dal tokenizer e lo utilizza per popolare un oggetto della classe ParseTree (che devo progettare) utilizzando l'analisi della discesa ricorsiva. Comprendo i fondamenti su come eseguire questa operazione, ma sto riscontrando problemi nell'implementazione della classe ParseTree. Le produzioni descritte dal Core BNF solitamente hanno 2-5 simboli terminali/non terminali, ma alcuni possono avere fino a 20 quindi ho bisogno di un albero n-ary in cui ogni nodo può avere un numero diverso di bambini.

Suppongo che la classe ParseTree non abbia necessariamente bisogno di utilizzare un albero per la sua implementazione ma che sembra avere più senso (esiste una struttura dati diversa che potrebbe essere migliore/più facile?). Non sono a conoscenza di alcun contenitore in STL che si adatta al conto per quello che mi serve. Ho guardato l'albero delle proprietà Boost ma da quello che posso dire che non funzionerà neanche. Preferirei non reinventare la ruota e realizzare un albero da zero se possibile. Inoltre, sono limitato dal fatto di non essere in grado di utilizzare alcuna libreria esterna oltre a Boost. Qual è il modo migliore per implementare il mio ParseTree? Ci sono buone implementazioni di alberi pre-fatte che potrei usare?

Answer 1

Suggerisco di utilizzare l'albero binario "left child, right sibling" per rappresentare l'albero di analisi. È una sostituzione di un albero n-ario. Qualsiasi albero n-ary può essere rappresentato usando l'albero BINARY 'first child, next sibling'.

Il concetto è il seguente: se A ha tre figli: B, C e D e C ha 2 bambini E e F come segue

   A 
      /| \ 
      B C D 
       /\ 
      E F 

questo può essere rappresentato come

   A 
      /
      B 
       \ 
       C 
      /\ 
      E D 
       \ 
       F 

cioè i bambini vanno sempre al nodo sinistro e i fratelli al nodo destro. È anche facile da costruire e l'attraversamento del preordine di questo albero è lo stesso del traversamento di pre-ordine di un albero n-ario.

albero n-ario pre-ordine di attraversamento:

display (node, level) { 
    if (!node) return; 
    print node; 
    display (node->left, level+1); 
    display (node->right, level+1); 
} 

bambino di pari livello albero binario di pre-ordinare travesal

display (node, level) { 
    if (!node) return; 
    print node; 
    display (node->left, level+1); 
    display (node->right, level); 
} 

Come costruire questo albero:

1. Throw your terminals and non-terminals in a Stack. 
2. When you want to combine n nodes under parent node 'p', pop 'n' elements from stack, making the last pop as the right child of the current pop. 
3. Finally make the nth pop the left child of node 'p'.