Re: AST transformations

[jvb@uwyo.edu]

  If I am right, I think that we need to design some refinement  before you jump
  to your code editor and start coding it;-)

Etienne. You're on the right track and I absolutely agree that the ideas
need to be refined.

  One problem is that you do not know for sure that the number of "id"s in the
  id* list is equal to the number of "num"s in the num* list. 

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

Rule: bad mult_assign1
mult_assign((),assign,(first_num, rest_num*),semicolon)
->
block(some kind of error indicator)

(Of course grammars would have to be extended with error tokens and the like.)

Rule: bad mult_assign2

mult_assign((first_id,rest_id*),assign,(),semicolon)
->
block(another error indicator)

  But this is unfortunate:  we are creating nested block statements, instead of
  a single one (with many single_assign sub statements)!

This occurred to me as well, although I didn't mention it in my
previous message. My idea for a solution is pretty much along the
lines you present.
  
  (The tool should also reject any ambiguous specification).

Not sure I agree with this since in this case it does not matter that
the specification is ambiguous.

Rule: In statement

  block({!block}head_statement*,{block}block_stmt(stmt*),tail_statement*)
  ->
  block(head_statement*,stmt*,tail_statement*)

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?

I like your idea to try to convert the LL(1) expression grammar. I'll try
to do this when I have a chance.

  If you want to go for a "rule based" system, it should also have a
  predictable output.  This means that either: 
  (1) the order in which rules are applied is of no importance, as the
  final AST would be the same, or 

This property of a rewrite system is called Church-Rosser and it is
undecidable in general, so I had in mind we'd stay away from this
approach.

  (2) [this is usually the case] the order of rules is important.  In
  which case, the behavior of the transformtation engine should be
  clearly defined so that transformations can be expressed
  deterministically.

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

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.

Once again, thanks for your insightful comments and I'll get back to
you with the results of my attempt at your suggested exercise.

Jeff
----