Re: AST transformations

[Angelo Schneider <angelo.schneider@xcc.de>]

Hi all,

there exists a system called TXL done at a canadian university,
now a commercial tool.
TXL: Tree transformation language.
see: www.queensu.ca

They do somthing similar like you want to do, applying rules
on ASTs yielding transfomred AST subsets.

Also ANTLR supports TREE Grammars and match/replace operations on
trees.  (www.antlr.org)

Propably you find some hints there.

Regards,
	Angelo

"Etienne M. Gagnon" wrote:
> 
> jvb@uwyo.edu wrote:
> > Yes. That's a problem, but its no different from any other error that cannot
> > be caught at parse time is it? We could extend the syntax to check lengths, but
> > instead I think I'd add two other rules
> > ...
> 
> Agreed.
> 
> > Here I'm confused about the meaning of your syntax, but is your idea to
> > ensure that none of the statements in head_statements* is a block?
> 
> Exactly.  I was using the {...} syntax to match a specific alternative of a
> production (block statement).  The {!...} meant any alternative except this
> one.
> 
> > This is what I had in mind. Here my thinking had only gotten as far as
> > that one could apply sets of rules using different Adaptors (your
> > word).  For example, one could apply a rule set depth first, or
> > exhaustively depth first. Something like that...
> 
> I see where you are heading.  Quite interesting.
> 
> (BTW: It's not "my" word... I picked it up from Sun's API documentation.  e.g.
> java.awt.event.WindowAdapter).
> 
> > You correctly point out that to reason about the behavior of the
> > transformation system, one needs to know what will happen when more
> > than one rule from a set can be applied at a node and also what will
> > happen if we allow ambiguity like in your example with nested
> > blocks. What I was thinking of here is that we could simply make some
> > arbitrary choices such as the first rule in a rule set that matches
> > will be chosen and for ambiguities, the left most disambiguation will
> > always be chosen.
> 
> This seems quite reasonible.  At least it would be fairly simple to make a
> mental picture the AST transformer's behavior.
> 
> Here I trust your insight on the potential side effects of ambiguity in this
> context.  In the context of parsers, grammar ambiguity plays a role not only
> on the shape of the resulting AST (e.g. many possible ASTs), but also on the
> time complexity of parsing.  Because we usually want parsers to be fast, we
> need the parser to make "early" decisions.  Making an arbitrary decision
> (shift, or reduce to the earliest matching alternative) causes
> impredictability for a user's point of view  (the early decision might be the
> wrong one, and lead to a parse error, instead of accepting the program using
> another but correct decision).  An ambiguous grammar also means that it is
> difficult to express semantics of a specific program (each possible parse
> having different semantics). Grammar ambiguity detection is also undecidable,
> but we usually stick to the "fast" subset of unambiguous grammars (LR(K)
> grammar).
> 
> I guess that in the context of AST transformation, ambiguity is not that much
> of a problem anymore.  If each transformation yeilds an AST with equivalent
> semantics, then we don't care, as long as we (hopefully) reach a fixed point
> where the AST tranformation engine stops and no matching rule is left.  [So,
> we know all LL constructs have all been removed from the AST, in the LL
> expression grammar example]. Hmmm... Does the theory also tell us that it is
> difficult (impossible) to enforce "terminating" AST transformations (e.g. no
> infinite looping on rule transformation)? ... Probably, as usual;-)
> 
> > Once again, thanks for your insightful comments and I'll get back to
> > you with the results of my attempt at your suggested exercise.
> 
> Thanks to you for your contribution to SableCC.
> 
> Etienne
> --
> ----------------------------------------------------------------------
> Etienne M. Gagnon, M.Sc.                     e-mail: egagnon@j-meg.com
> Author of SableCC:                 http://www.sable.mcgill.ca/sablecc/
> ----------------------------------------------------------------------

-- 
---------------------------------------------------------------------
Angelo Schneider           OOAD/UML           Angelo.Schneider@xcc.de
Putlitzstr. 24         Patterns/FrameWorks       Fon: +49 721 9812465
76137 Karlsruhe             C++/JAVA             Fax: +49 721 9812467