Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Journal of luqui (5770)

Wednesday September 28, 2005
09:22 PM

More Attribute Grammars

[ #26926 ]

Okay, so after having applied attribute grammars to one or two things now, I think this is one of the Great Tree Transformation Tools the design team has been looking for. Of course, Allison has known this for a long time, but I guess she failed to convince me.

Anyway, I went to have a chat with Prof. William Waite here at the University of Colorado. He's done extensive research on compiler tools in general and attribute grammars in particular. I told him about my implementation in Language::AttributeGrammar, and he told me that that's about the worst way to do it. Sure, the time complexity is no worse than that of any other algorithm, but the memory complexity is horrific. Both are O(na), for n the number of nodes in the tree and a the number of attributes. A serious implementation in terms of attribute grammars is going to have hundreds of attributes, so linear space in the number of attributes is unacceptable.

He pointed me to some literature, in particular "Lecture Notes in Computer Science #545". I read up, and it turns out that the algorithms for preprocessing the grammar statically to remove laziness (resulting in a linear speed boost) and deallocate attributes when you're done with them (resulting in potentially massive space boosts) are not terribly difficult to implement. A little graph theory here, a little lifetime analysis there.

So I'm going to rewrite my module to incorporate static analysis. Also, as you saw in the design meeting notes, Patrick and chromatic want it for Parrot. So I'm going to design it pluggably (syntactically and code-generatively), but I personally dislike programming in assembly (even if it is high-level parrot assembly), so I'll let them do the dirty work.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
More | Login | Reply
Loading... please wait.