Re: concrete vs. abstract syntax trees

Chris F Clark <cfc@shell01.TheWorld.com> 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
automate.


Still more opinions,
-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

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