Traversing a scheme-like tree (graph) dump using C

Question

I have a Scheme-like tree graph structure. I want to parse it using C into some in-memory representation and walk over it.

It there any library or front-end of parser to do this?

EDIT:

I have parsed the following expression

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

into following (This is my scheme-like tree dump)

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

Which I want to traverse using C ( I have to give it to someone else who only works with C). PROG is a label; AndExp, OrExp etc are tokens for &&, || etc ..

Answer 1

It seems like this is a form of S-Expression. Perhaps This S-Expression Parser can be modified for your needs.

Answer 2

I think i have understood your requirement, but not quite sure.

You have the expressions in prefix notation, therefore this is basically loading the prefix expression you have in your dump file in binary tree.

Here is a pseudocode which described the process to load the expressions into a tree.

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

• Recursive call 1 with (AndExp TVal(OrExp FValTVal))

  tok1 = AndExp makes a new node1

  tok2 = TVal

  tok3 = (OrExp FValTVal)

• Recursive call 2 with TVal returns node2 to call 1 which links it with the left pointer of node1.

• Recursive call 3 with (OrExp FValTVal) from call 1.

  tok1 = ORExp makes a new node3

  tok2 = FVal

  tok3 = TVal

• Recursive call 3 with FVal and call 4 with TVal respectively returns node4 and node5 with the operand values, which are linked to the left and right links of the node3 from call 3.

No more subexpression to be considered, recursion returns back to starting point. You have the root of the tree.

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

If there are more than two operands , processing can be done similarly by adding additional links to the tree nodes.

For each expression in your dump file, which are separated by commas will have separate trees, which after creation can be traversed.