Re: concrete vs. abstract syntax trees

Chris F Clark <>
Sat, 14 Feb 2009 19:58:45 -0500

          From comp.compilers

Related articles
concrete vs. abstract syntax trees (eliben) (2009-02-13)
Re: concrete vs. abstract syntax trees (Hans Aberg) (2009-02-14)
Re: concrete vs. abstract syntax trees (Ira Baxter) (2009-02-14)
Re: concrete vs. abstract syntax trees (Chris F Clark) (2009-02-14)
Re: concrete vs. abstract syntax trees (Chris F Clark) (2009-02-14)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: Sat, 14 Feb 2009 19:58:45 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 09-02-050 09-02-067
Keywords: AST
Posted-Date: 15 Feb 2009 18:35:07 EST

Chris F Clark <> writes:

> Concrete systax trees tend to over-promote certain artifacts of the
> grammar in the shape of the tree. If the grammar is left-recursive,
> the trees tower one way. A right recrusive grammar (for the same
> language) would have trees that tower in the opposite direction. An
> ELR grammar, using regular expressions, might not have a tree at all
> but rather a flat list.

That said, parser generators often make it easy to generate CSTs.
With a parser generator, the simplest and safest course is to create a
CST. Optimizations to transform it more into an AST can easily be
applied. If one is using a generator and because of that is working
with a CST (that was easy to get from the tool), no shame should be
inferred. As Ira said, certain traversals over CSTs are not that
inefficient compared to ASTs, and if you've save some programmer time,
then it may balance out.

If you are starting from scratch, either find a tool that helps you
construct a tree (whether CST or AST), or write a layer over your tool
to do so. If you have to create a hand-written strcture becausze the
tree your tool creates won't make that shape, no shame in that either.
However, don't waste time creating a hand-written structure that
exactly matches the grammar. That kind of structure is too easy to

Still more opinions,

Chris Clark Internet:
Compiler Resources, Inc. or:
23 Bailey Rd Web Site:
Berlin, MA 01503 voice: (508) 435-5016
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.