Durchlaufen eines schemaähnlichen Baumspeicherauszugs (Diagrammdumps) mit C.

Question

Ich habe eine schemaartige Baumstruktur graph .Ich möchte es mit C in eine In-Memory-Darstellung analysieren und darüber gehen.

Gibt es eine Bibliothek oder ein Front-End des Parsers, um dies zu tun?

BEARBEITEN:

Ich habe den folgenden Ausdruck analysiert

true && (false || true) ;
true ;
false || false 

in folgendes (Dies ist mein schemaähnlicher Baumspeicherauszug)

(PROG [(AndExp TVal(OrExp FValTVal)), TVal, (OrExp FValFVal)])

Was ich mit C durchqueren möchte (ich muss es jemand anderem geben, der nur mit C arbeitet).PROG ist ein Label;AndExp, OrExp usw. sind Token für &&, ||etc ..

Answer 1

Es scheint, dass dies eine Form von S-Expression ist.Möglicherweise kann Dieser S-Expression-Parser an Ihre Bedürfnisse angepasst werden.

Answer 2

Ich glaube, ich habe Ihre Anforderung verstanden, bin mir aber nicht ganz sicher.

Sie haben die Ausdrücke in Präfixnotation, daher wird der Präfixausdruck, den Sie in Ihrer Dump-Datei haben, im Binärbaum geladen.

Hier ist ein Pseudocode, der den Prozess zum Laden der Ausdrücke in einen Baum beschreibt.

tree_node make_tree (string dump)
{
  tok1 = get_tok (dump);
  tok2 = get_tok (dump);
  tok3 = get_tok (dump);

  if (tok1 == operand)
  {
    node = make_new_node_with (tok1);
    return node;
  }

  node = make_new_node_with (tok1);
  node->left = make_tree (tok2);
  node->right = make_tree (tok3);
  return node;
}

• Rekursiver Aufruf 1 mit (AndExp TVal(OrExp FValTVal))

  tok1= AndExp erstellt einen neuen Knoten1

  tok2= TVal

  tok3= (OrExp FValTVal)

• Rekursiver Aufruf 2 mit TVal gibt Knoten2 an Aufruf 1 zurück, der ihn mit dem linken Zeiger von Knoten1 verknüpft.

• Rekursiver Aufruf 3 mit (OrExp FValTVal) aus Aufruf 1.

  tok1= ORExp erstellt einen neuen Knoten3

  tok2= FVal

  tok3= TVal

• Rekursiver Aufruf 3 mit FVal und Aufruf 4 mit TVal geben Knoten4 und Knoten5 mit den Operandenwerten zurück, die mit den linken und rechten Verknüpfungen von verknüpft sind der Knoten3 von Aufruf 3.

  Kein Unterausdruck mehr zu berücksichtigen, die Rekursion kehrt zum Ausgangspunkt zurück. Sie haben die Wurzel des Baumes.

                           ( node1 )
                           |AndExp |
                           +---+---+
                               |
                  +------------+------------+
                  |                         |
              ( node2 )                ( node3 )
              | TVal  |                | ORExp |
              +---+---+                +---+---+
                                           |
                               +-----------+-----------+
                               |                       |
                           ( node4 )               ( node5 )
                           |  FVal |               |  TVal |
                           +---+---+               +---+---+ 
  

  Wenn mehr als zwei Operanden vorhanden sind, kann die Verarbeitung auf ähnliche Weise erfolgen, indem zusätzliche Verknüpfungen zu den Baumknoten hinzugefügt werden.

  Für jeden Ausdruck in Ihrer Dump-Datei, die durch Kommas getrennt sind, gibt es separate Bäume, die nach der Erstellung durchlaufen werden können.