C++ n-äre Baumimplementierung für die Verwendung beim rekursiven Abstiegsparsing

Question

Ich bin immer noch ein wenig neu in C++, also bitte hab Geduld mit mir. Ich implementiere einen Interpreter für eine hypothetische Sprache namens Core, die durch eine BNF-Grammatik beschrieben wird. Bisher habe ich einen Tokenizer implementiert, der mir eine schöne Warteschlange von Tokens liefert, die ein Core-Programm darstellen. Jetzt bin ich dabei, den Parser/Executor zu schreiben, der den Output des Tokenizers verwendet, um ein Objekt der Klasse ParseTree (die ich entwerfen muss) mithilfe der rekursiven Abstiegsanalyse zu füllen. Ich verstehe die Grundlagen, wie man das macht, habe aber Schwierigkeiten bei der Implementierung der ParseTree-Klasse. Die Produktionen, die durch die Core-BNF beschrieben werden, haben normalerweise 2-5 terminale/nichtterminale Symbole, aber einige können bis zu 20 haben, daher benötige ich einen n-ären Baum, in dem jeder Knoten eine unterschiedliche Anzahl von Kindern haben kann.

Ich vermute, die ParseTree-Klasse muss für ihre Implementierung nicht unbedingt einen Baum verwendet, aber das scheint am sinnvollsten zu sein (gibt es eine andere Datenstruktur, die möglicherweise besser/einfacher wäre?). Mir ist keine Container in der STL bekannt, der meinen Anforderungen entspricht. Ich habe mir den Boost-Eigenschaftsbaum angesehen, aber soweit ich sehen kann, würde das auch nicht funktionieren. Ich würde es bevorzugen, das Rad nicht neu zu erfinden und einen Baum von Grund auf zu implementieren, wenn möglich. Außerdem bin ich eingeschränkt darin, keine externen Bibliotheken außer Boost verwenden zu können. Wie kann ich meinen ParseTree am besten implementieren? Gibt es gute vorgefertigte Baum-Implementierungen, die ich verwenden könnte?

Answer 1

Ich schlage vor, den 'linken Kind, rechter Geschwister' binären Baum zur Darstellung des Parsebaums zu verwenden. Es ist ein Ersatz für einen n-ären Baum. Jeder n-äre Baum kann mit einem 'erstes Kind, nächster Geschwister' BINÄRBAUM dargestellt werden.

Das Konzept ist wie folgt: Wenn A drei Kinder hat: B, C und D und C wie folgt zwei Kinder E und F hat

              A
            / | \
           B  C  D
              /\
             E  F

kann dies wie folgt dargestellt werden

              A
             /
             B
              \
               C
              / \
             E   D
              \
               F

d.h. die Kinder gehen immer zum linken Knoten und die Geschwister zum rechten Knoten. Es ist auch einfach zu erstellen und der Pre-Order-Durchlauf dieses Baumes ist derselbe wie der Pre-Order-Durchlauf eines n-ären Baumes.

n-ärer Baum Pre-Order-Durchlauf:

display (Knoten, Ebene) {
    if (!Knoten) return;
    drucke Knoten;
    display (Knoten->links, Ebene+1);
    display (Knoten->rechts, Ebene+1);
}

Kind-Geschwister-Binärbaum Pre-Order-Durchlauf

display (Knoten, Ebene) {
    if (!Knoten) return;
    drucke Knoten;
    display (Knoten->links, Ebene+1);
    display (Knoten->rechts, Ebene);
}

Wie man diesen Baum erstellt:

1. Wirf deine Terminale und Nicht-Terminals in einen Stapel.
2. Wenn du n Knoten unter dem Elternknoten 'p' kombinieren möchtest, nimm 'n' Elemente vom Stapel und mache den letzten nehmen als rechtes Kind des aktuellen Nehmens.
3. Mache schließlich das n-te Nehmen zum linken Kind des Knoten 'p'.