Attraversare un dump ad albero (grafico) simile a uno schema usando C

Question

Ho una struttura grafo ad albero simile a Scheme.Voglio analizzarlo usando C in una rappresentazione in memoria e passarci sopra.

C'è qualche libreria o front-end del parser per farlo?

MODIFICA:

Ho analizzato la seguente espressione

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

in seguito (questo è il mio tree dump simile a uno schema)

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

Che voglio attraversare usando C (devo darlo a qualcun altro che lavora solo con C).PROG è un'etichetta;AndExp, OrExp ecc. Sono token per &&, ||ecc ..

Answer 1

Sembra che questa sia una forma di S-Expression .Forse questo S-Expression Parser può essere modificato in base alle tue esigenze.

Answer 2

Penso di aver compreso le tue esigenze, ma non ne sono del tutto sicuro.

Hai le espressioni nella notazione del prefisso, quindi questo fondamentalmente sta caricando l'espressione del prefisso che hai nel tuo file di dump nell'albero binario.

Ecco uno pseudocodice che descrive il processo per caricare le espressioni in un albero.

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;
}

• richiamo 1 ricorsivo con (AndExp TVal(OrExp FValTVal))

  tok1= AndExp crea un nuovo node1

  tok2= TVal

  tok3= (OrExp FValTVal)

• chiamata 2 ricorsiva con TVal restituisce node2 a call 1 che la collega con il puntatore sinistro di node1.

• chiamata 3 ricorsiva con (OrExp FValTVal) dalla chiamata 1.

  tok1= ORExp crea un nuovo node3

  tok2= FVal

  tok3= TVal

• richiamo 3 ricorsivo con FVal e richiamo 4 con TVal restituisce rispettivamente node4 e node5 con i valori dell'operando, che sono collegati ai collegamenti sinistro e destro di il node3 dalla chiamata 3.

Non più sottoespressione da considerare, la ricorsione torna al punto di partenza. Hai la radice dell'albero.

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

Se sono presenti più di due operandi, l'elaborazione può essere eseguita in modo simile aggiungendo ulteriori collegamenti ai nodi dell'albero.

Per ogni espressione nel file di dump, che sono separate da virgole avranno alberi separati, che dopo la creazione possono essere attraversati.