[antlr-interest] TreeDL (was: AST specification and processing)

[Tiller, Michael (M.M.)]

Alexey,

As a general comment, this sounds quite interesting to me but I need a
lot more concrete examples.

For example, could you create an example for expression manipulation
that shows how you could transform an expression AST into its derivative
(e.g. automatic differentiation).  Show how the tree is built from
within ANTLR, show how you can explore it, walk it, visit it, etc.  Then
show how you can transform it (e.g. differentiate it).  That would help
me understand what you are after.  Ideally, it would be good if you
could show how you could exploit the attribute information.  For
example, a generic "binary op" node type but with an attribute that
indicates the specific operator (+,-,*,/) or a "function call" node type
with a required function name and then an optional set of argument.

Personally, I've always had a preference for heterogenous tree
structures and TreeDL seems to be a step toward a formal tree structure
specification (and utilities to operate on them?).  Is that correct?

Any comments on XML representations (reading and writing XML versions),
performance issues while traversing, etc?

--
Mike

> -----Original Message-----
> From: Alexey Demakov [mailto:demakov at ispras.ru]
> Sent: Friday, October 15, 2004 5:51 AM
> To: antlr-interest at yahoogroups.com
> Subject: Re: [antlr-interest] TreeDL (was: AST specification and
> processing)
> 
> 
> Hi John,
> 
> Thank you for attention to my long message :)
> 
> > > How to split translator into subsystems, how to specify interfaces
> > > between them?  Natural decomposition of translator is around
internal
> > > representation of input data, i.e. around AST: Parser checks
syntax
> and
> > > builds AST, semantics checker verifies static semantics and adds
> > > additional information to AST.  After that AST can be transformed,
> > > processed in other way, output code can be generated.  All of
these
> > > subsystems depends on AST format only, they are (theoretically)
> > > independent of each other.
> >
> > But they aren't, a priori, independent of each other.
Transformations,
> > even while preserving the basic structure of the tree (i.e.,
adhering to
> > the same grammar) are often order dependent.  Also, many tree
> > walkings/manipulations accumulate and/or modify information stored
> outside
> > the trees.
> 
> O'key, I mean implementations of transformations are independent.
> Pre- and post-conditions for each transformation can be formulated
> in terms of tree state - possible node types, required additional
> information
> (for example, reference-definition links). Information stored outside
tree
> can be considered
> as attribute of tree in whole, and can be referenced, for example,
from
> root node,
> so it is not a problem.
> 
> To specify a contract for each action over tree it is enough to
describe
> tree structure
> and state of attributes.
> 
> > > If there is separate AST specification (not in ANTLR parser), all
of
> > > these subsystems (including parser) can be developed independently
and
> at
> > > the same time. AST specification can be used as a contract between
> > > developers of different subsystems. According to my experience, it
> speeds
> > > up development and reduces number of errors.
> >
> > Sure (modulo taking the points I made above into account).
> >
> > > I propose the notation called TreeDL to describe tree-like
structures,
> > > open-source tool that checks consistence of tree description and
> > > translates tree description to a set of classes (now in Java, C#
will
> be
> > > added in near future). The TreeDL tool also can generate HTML
> > > cross-referenced version of tree description to be used as
> documentation.
> > > Tree nodes can be decorated by dynamic attributes to store
additional
> > > information.  There is powerful template engine to generate code
from
> > > tree.  Also there is framework for rapid tool development -
library
> for
> > > error reporting, functionality extention by plugins - TreeDL tool
> itself
> > > uses tree description in TreeDL, mentioned template engine and
> framework,
> > > so source code can be used as an example.
> >
> > So, are you saying that TreeDL is e.g., a replacement for Antlr tree
> > handling?  Basically, what's the real point of TreeDL?  I.e., what
> doesn't
> > Antlr's tree handling do that you want?
> 
> As far as I know, in ANTLR there is no way to sepatate tree definition
> from parser.
> It is harder for developers of tree processing than if they have clear
and
> full description of tree structure.
> 
> So, the main point of TreeDL is to provide the notation for
specification
> of tree structure.
> For example, most of our developers are not familiar with ANTLR and
they
> can't understand
> a structure of tree that ANTLR builds - it is required to read all
parser
> definition.
> But it is unnesesary, because the only thing they should know - what
kinds
> of nodes are used,
> what children and attributes are defined for each node.
> 
> Moreover, TreeDL tree can be constructed even without parser. In one
of
> our projects
> we build TreeDL tree from GUI and use the same codegeneration library.
> May be I am "tree fan" as Terence is "grammar fan" :)
> As my colleague speaks: "Not because I have no other ideas, but
because
> this is the one I like most".
> (Hm, not very easy to translate to English...)
> 
> > > Additional docs and downloads are at http://treedl.sourceforge.net
> > > Example tree description
> > >
>
http://treedl.sourceforge.net/treedl/treedl/com/unitesk/atp/treedl/TreeD
L.
> tdl-xref/index.html
> > > TreeDL BNF grammar
> > > http://treedl.sourceforge.net/treedl/bnf/TreeDL.bnf/index.html
> > > TreeDL language description
> http://treedl.sourceforge.net/treedl/treedl_en.html
> > > TreeDL tool description
> > > http://treedl.sourceforge.net/treedl/treedl_tool_en.html
> > > Template engine usage example
> > >
>
http://treedl.sourceforge.net/treedl/xref/com/unitesk/atp/treedl/JavaNod
eG
> enerator.html
> >
> > Am I reading the docs correctly... Are you really using the visitor
> pattern
> > rather than generating a recursive descent parser?
> 
> TreeDL notation itself doesn't define what is generated from tree
> description. TreeDL tool provides
> default implementation but it is easy to modify translation scheme, to
> change what should be generated or
> generate additional information you need.
> 
> Historically codegeneration library use visitor pattern, but it is not
> required for all TreeDL users to use it also.
> It is not clear for me, what task requires recursive descent parser?
Do
> you mean tree walker?
> (Plugin that generate tree walker can be written in several hours.)
> TreeDL tool doesn't do ANTLR job - ANTLR is used for parsing. Actions
that
> create TreeDL tree nodes
> should be inserted in ANTLR parser rules. Of course, this code is
longer
> than the use of ANTLR tree building,
> but easy to write, understand and maintain (You see, there are rather
many
> questions in this list about problems
> with ANTLR tree building). And tree description guarantees that
correct
> tree will be built - node constructor checks
> that all required children and attributes are provided, and additional
> checks of its values can be defined.
> 
> I plan to write small examples on how to write formal text processing
tool
> using ANTLR and TreeDL,
> are members of this list interested to read them?
> 
> Another tool that we've developed is caled BNF tool. It takes grammar
in
> BNF form, check correctness
> (well, it is simple - all used rules should be defined and reachable
from
> start rule) and generates positive/negative tests,
> i.e. sentences that a priory satisfy/unsatisfy grammar. Test can be
> generated from any context-free grammar definition.
> It is useful when source grammar should be adapted to be suitable for
> ANTLR - we need some checking that
> source and modified grammars are describing the same language.
> 
> Also HTML version of grammar with cross-references can be generated.
This
> is example:
> http://treedl.sourceforge.net/treedl/bnf/TreeDL.bnf/index.html
> 
> Now BNF tool is not public available, but in the future it is
possible.
> 
> Thanks,
> Alexey
> -----
> TreeDL: Tree Description Language: http://treedl.sourceforge.net
> RedVerst Group: http://www.unitesk.com
> 
> 
> 
> 
> 
> Yahoo! Groups Links
> 
> 
> 
> 
> 
> 



 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
    antlr-interest-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/