Implementacja drzewa n-arylowego C++ do użytku w przetwarzaniu rekursywnego spadku

Question

Wciąż jestem trochę nowy w C++, więc nie przejmuj się mną. Wdrażam tłumacza hipotetycznego języka o nazwie Core, który opisuje gramatyka BNF. Do tej pory zaimplementowałem tokenizator, który zapewnia miłą kolejkę tokenów reprezentujących program Core. Jestem teraz w trakcie pisania Parser/Executer, który pobiera dane wyjściowe z tokenizera i używa go do zapełnienia obiektu klasy ParseTree (który muszę zaprojektować) przy użyciu rekursywnego parsowania. Rozumiem podstawy, jak to zrobić, ale mam problemy z implementacją klasy ParseTree. Produkcje opisane przez Core BNF zwykle mają 2-5 terminali/nieterminalnych symboli, ale niektóre mogą mieć do 20, więc potrzebuję drzewa n-ary, w którym każdy węzeł może mieć inną liczbę dzieci.

Przypuszczam, że klasa ParseTree niekoniecznie musi używać drzewa do jego implementacji, ale wydaje się, że ma to największy sens (Czy istnieje inna struktura danych, która może być lepsza/łatwiejsza?). Nie jestem świadomy jakiegokolwiek kontenera w STL, który pasuje do rachunku za to, czego potrzebuję. Spojrzałem na drzewo właściwości Boost, ale z tego, co wiem, nie będzie działać. Wolałbym nie wymyślać koła od nowa i zaimplementować drzewo od podstaw, jeśli w ogóle możliwe. Ponadto jestem ograniczony przez to, że nie mogę korzystać z zewnętrznych bibliotek poza Boost. Jaki jest najlepszy sposób na wdrożenie mojego ParseTree? Czy są jakieś dobre, wcześniej przygotowane implementacje drzew, których mogłem użyć?

Answer 1

Proponuję użyć drzewa binarnego "lewe dziecko, prawe rodzeństwo" do reprezentowania drzewa parsowania. Jest to zamiennik drzewa n-ary. Każde drzewo n-ary może być reprezentowane przy użyciu drzewa BINARY "pierwsze dziecko, następne rodzeństwo".

Pojęcie jest następujący: jeżeli A ma trzy dzieci: B, C i D i C z 2 dzieci, E i F jak następuje

   A 
      /| \ 
      B C D 
       /\ 
      E F 

może być reprezentowany jako

   A 
      /
      B 
       \ 
       C 
      /\ 
      E D 
       \ 
       F 

tj. Dzieci zawsze przechodzą do lewego węzła, a rodzeństwo do prawego węzła. Jest również łatwy do zbudowania, a przemierzanie tego drzewa w kolejności wstępnej jest takie samo, jak przemieszczenie drzewa n-ary w zamówieniu wstępnym.

n-ary drzewo pre-order przechodzenie:

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

dziecko rodzeństwa binarne drzewo pre-order travesal

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

Jak budować ten drzewa:

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'.