Building Abstract Syntax Tree

0
votes

I have my parse tree with me, now I have traversed in order on the parse tree and a Symbol table is generated too. But how do I build the AST for this?

Here is what I have gathered (some unreliable resources):

  • In your parse tree you go inOrder I.e Take the leftmost child, The parent then, and then the list of other children.
  • If you come across anything like SEMICOL, Parenthesis, do not add it to AST, if there is only one child to a node, remove that node, and use child instead.

Is this all I need to do?

1
cabstract-syntax-tree
It is impressive your symbol table is generated since you can't know scope at this point. – Hogan
@Hogan I have the parse tree, what will stop me from knowing the scope? – Kraken
Your system should not have any semantic information at this point. You have just parsed it. – Hogan
@Kraken - how do your parse tree and AST differ? They can be pretty much the same thing. Personally, I've always treated the parse tree as if it was the AST, though I'm no expert - I've only written a few unreleased domain-specific languages. That said, translating from one tree form to another is really just a combination of traversing the old and creating the new - if you can create a parse tree while parsing, you shouldn't have too much trouble generating a new tree while traversing the old one. You even get to choose the traversal order and limits to suit what you're generating. – Steve314
@Hogan from my parse tree, after traversing it, i looked at all the declared IDs and added their info to the table. – Kraken

1 Answers

0
votes

Update based on comment

In your example the parse tree might contain a statement node like this

(int) -> (ageArray) -> ([) -> (30) -> (]) -> (;)

The professor expects something like

(intArray) -> (ageArray) -> (30)

I guess.

You are making the solution to simple. It is not simply a matter of traversing your tree and throwing some stuff out. ASTs represent the constructs of the program language. In order to build an AST you first have to design what the AST is going to look like.

For example, an "IF" node might be designed as having a boolean equation element (this in itself is probably a tree too), a true statement tree and a false statement tree.

You have to design what all the elements are going to look like based on the language you are compiling. Once you have that design then often a lexer is used on the parse tree to generate the AST.