Converting Parse Tree Into AST (Abstract Syntax Tree) C++

Question

I have a parse tree that parses out a stack of a stack of char (stack<stack<char>>). This gets the characters into a parse tree. My question is how would I convert this parse tree into a AST in order to evaluate it?

I have the evaluator working for a AST I just need to convert the tree into the syntax in order to evaluate it.

Any help would be appreciated.

Here is a picture of what I am trying to accomplish

If the string was originally 5+6 - (4*6) + 5 the stack of stack of chars would be [[5] [+] [6] [-] [(] [4] [*] [6] [)] [+] [5]] That is turned into a parse tree — Dfranc3373
– Dfranc3373, Commented May 5, 2012 at 19:17
How is this stack of stacks different from any plain old stack? Do any inner stack have more than one item, ever? Also, where's the stack? I see a sequence of characters that repeats the input sequence verbatim. What is the transformation here? — n. m. could be an AI
– n. m. could be an AI, Commented May 5, 2012 at 19:57
The stack of characters is not what is important, the important thing is that I have a tree that has the characters in it as well as nodes for the + minus parenthesis and so on. I need to convert that tree into a ast so it will have a full node. Here is a picture of what I am trying to accomplish, I will edit the question — Dfranc3373
– Dfranc3373, Commented May 5, 2012 at 20:21

Dfranc3373 · Accepted Answer · 2012-05-11 18:09:32Z

3

I was able to convert them using a Tree Traversal Algorithm

Using Pre Order Traversal

preorder(node)
  if node == null then return
  print node.value
  preorder(node.left) 
  preorder(node.right)

Using a stack to store the leaf nodes I added the values onto them and was able to transverse the stack and change into lea nodes.

A example for 10 + 4

the parse tree leafs using preorder would give me a stack of [+ 10 4]

Using a helper function I could convert this into a

Make_Plus(Make_Int(10), Make_Int(4)) by using recursion

answered May 11, 2012 at 18:09

Dfranc3373

2,1775 gold badges31 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Converting Parse Tree Into AST (Abstract Syntax Tree) C++

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related