Re: AST transformations

["Etienne M. Gagnon" <egagnon@j-meg.com>]

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/
----------------------------------------------------------------------