Re: [Q] How Is AST structured for entire program??

Chris F Clark <>
Thu, 18 Oct 2007 09:12:38 -0400

          From comp.compilers

Related articles
[Q] How Is AST structured for entire program?? (2007-10-16)
Re: [Q] How Is AST structured for entire program?? (George Neuner) (2007-10-17)
Re: [Q] How Is AST structured for entire program?? (Hans-Peter Diettrich) (2007-10-17)
Re: [Q] How Is AST structured for entire program?? (Chris F Clark) (2007-10-18)
Re: [Q] How Is AST structured for entire program?? (Paul B Mann) (2007-10-24)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: Thu, 18 Oct 2007 09:12:38 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 07-10-051 07-10-056
Keywords: parse, AST, analysis
Posted-Date: 18 Oct 2007 15:19:23 EDT

There is much good in George Neuner's response. I just want to
amplify some points he made.

1) An AST is usually abstract (throwing away unimportant details), but
      a parse tree is also an AST (where the set of details thrown away
      is empty).

2) A branch of tree is a tree. Thus, a tree can be constructed of the
      entire program. Worth noting is that many modern tools (Yacc++,
      JJTree, JTB, ANTLR, Cocktail, LALR, etc.) wiil [semi-]automatically
      create an AST builder from a grammar. Even many relatively simple
      modern tools can be told to create a parse tree from a grammar.
      Thus, if you want your entire input in AST format, that is
      relatively trivial to get.

3) An AST is not the only form of IR. Even if one keeps an AST form,
      it is often abandoned close to the root, as a tree is not the
      usually the most convenient form at that level. At the very top
      level, the structure often looks like a dictionary, with one entry
      per function or other globally visible name. Each function may be
      represented as an AST as many languages have fairly tree structured
      rules for composing expressions and statements. However, linked
      lists of statements (rather than lines) are also popular, as are
      control flow graphs. And, if you are serious about compilers, you
      should learn SSA form (and perhaps triples and quadruples).

Which brings me to the last point I wanted to make, if I recall
correctly, one can learn most of this from Appel's compiler
construction book, (aka the Tiger book) which wasn't on my shelf for
quuting the exact title--must be loaned out. After reading that, read
Bob Morgan's compiler construction book and then Steve Muchnik's if you
want the "full treatment".

Hope this helps,

Chris Clark Internet :
Compiler Resources, Inc. Web Site :
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.