[antlr-interest] Re: trees with payloads??

lgcraymer lgc at mail1.jpl.nasa.gov
Fri Nov 12 18:50:14 PST 2004



--- In antlr-interest at yahoogroups.com, "John D. Mitchell"
<johnm-antlr at n...> wrote:
> >>>>> "lgcraymer" == lgcraymer  <lgc at m...> writes:
> >>>>>> <johnm-antlr at n...> wrote:
> [...]
> 
> [...dynamically scope attributes...]
> 
> > As have I, which is why I am in the believers camp.  However, it could
> > still be a feature which is only occasionally useful; until we try it
> > out, we won't know otherwise.
> 
> Um, er, doing symbol tables is a pretty fundamental need in doing
> non-trivial translators.  The dynamically scoped attribute support
is, at
> the very least, the building block of symbol table management.
> 
> Um, er, variations of symbol table management such as def-use chaining
> abound in non-trivial translation tasks.

That is certainly true, but it is also clear that you assume that
dictionaries/hash tables are fundamental to providing dynamic
attribute support.  I don't; in fact I think that that approach would
lead to poor performance in the hands of typical developers and should
be avoided for that reason.  From my perspective, symbol table support
is almost orthogonal to the dynamically scoped attributes.

> As a personal data point that's completely current... In my current gig,
> I'm doing a lot of tree mutation that involves splitting and
splicing the
> existing tree parts along with completely new parts.  All of the
bookeeping
> to make that work is, alas, all manually implemented dynamic attributes
> (various incestuous combinations of inherited attributes, rule return
> values, and propagated standard and manual tree construction).  The
> "natural" solution to every single one of the non-trivial transformation
> tasks came to mind using dynamically scoped attributes -- then I had to
> make it work in the current Antlr.

Been there; done that; I remember the pain.

> 
> >> As I noted for the notes from the workshop, the dynamically scoped
> >> attributes need to support cabilities for things like LIFO & FIFO
> >> access; specification of things like at most one/n, exactly one/n, at
> >> least one/n; pushing/popping bundles of attributes; search
current scope
> >> for attribute, search up stack for attribute; etc.
> 
> > This is an area where implementation is likely to have significant
impact
> > on performance.  Yes, we should probably support multi-valued
attributes
> > directly as well as the dynamic scoping, but "capability first!"
is the
> > wrong mantra.
> 
> Capability and Simplicity are the two driving forces in Antlr v3.
> Sometimes they coincide and sometimes they are in direct opposition and
> usually the reality is somewhere in the middle.

You have left out Performance; that was the driver that got Ter
started on DFAs for lexers and from there to the LL(*) model.
"Capability" has differing interpretations:  the real goal is fast
turnaround of language processors, not to try to incorporate all
features which might be useful.  Simplicity actually just sort of
crept in; I would say that it is present "only" as a matter of good
design practice.

> An underlying question that I keep hearing in your posts is the
question of
> where do we draw the line as to what goes into the Antlr core and
what is
> left to add-ons, libraries, the whim of the code generators and
runtimes,
> etc.  I think that's the question that we need to be ruthless in always
> asking and ruthlessly honest in pursuing the answers.

There are too many custom classes in ANTLR 2--lists, bit arrays,
etc.--that could be done away with.  There are also features like AST
class generation which could be easily supported but are not. 
Incorporating these would significantly improve usability.

I would definitely quibble with the idea that things are left up to
the whim of the code generators.  ANTLR 2 proved that code generation
was very much at the mercy of the implementation model.  I don't
really think that ANTLR 3 will be much different, and that is
especially true for attribute support.

> > We also need to look at what disciplines are necessary when using
> > dynamically scoped attributes for understandability and
maintainability.
> > There are issues of data typing for generated code, context (which
scopes
> > should be searched?)  management, and grammar maintainability (what
> > scopes might apply) that need to be considered in the design. 
Otherwise,
> > dynamically scoped attributes can have as much negative impact as
> > templates have for C++ as well as having equivalent positive
impact.  "I
> > can do everything" can translate to "I can maintain nothing": the
range
> > of implementation models allowed can have a great deal of impact.
> > Debugging usage of dynamically scoped attributes could be a nightmare.
> 
> I hear ya.
> 
> I'm less paranoid because the pervasive backbone provided by the
grammars
> themselves makes dynamically scoped attributes in Antlr qualitatively
> constrained as compared to dynamically scoped variables in general
purpose
> programming languages.

I've seen too many cases of "if it can be abused, it will be abused
whole-heartedly; FUBAR is a way of life".  You should be very paranoid.

--Loring

> Take care,
> 	John





 
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/
 





More information about the antlr-interest mailing list