Thanks to two handy references from Autrijus (http://www.cs.uu.nl/wiki/Center/AttributeGrammarSystem> and ), I finally learned what an attribute grammar was, and why Allison seems so obsessed with them. They do kick a good deal of butt.
In my excitement, I implemented Language::AttributeGrammar-0.01 (and 0.02 and 0.03 :-) which is now on CPAN. I hardly knew anything about what an attribute grammar was good for when I wrote it, but I understood enough to know how it could be implemented. It is a little crude, in that it doesn't have type checking or automatic attribute generation (the latter of those coming soon), but it does everything UUAG does modulo some convenience features, and its base language is Perl instead of Haskell.
The cool thing about my implementation is that it can work on sparse, loosely-connected data structures. The module's algorithm assumes nothing about the connection of a parent to its child, so it could be "go look a url up from a database and fetch it from the web". The syntax prefers either method calls or hash access, however.
It is implemented lazily and demand-driven. The good side of that is that it doesn't compute more than it needs to (and it can be a tidy O(mn) for m the number of attributes and n the number of nodes). The bad side of that is that you can't dive into the data structure later on and find out what an attribute of a particular node was, because the lazy algorithm may not have found a path to it yet. That means you have to generate a new data structure with the information you want and return it. There is a way to remedy this ("semi-lazy"), and it requires much the same structure as automatic attribute generation (that is, telling the module what your data structure looks like), so I think those two features will come together.
Anyway, the module's pretty cool, and I was quite impressed in how simple it was to implement. Check it out.
A simpler reference and a question
n1vux on 2005-09-27T19:54:32
This sounds like the start of something useful.
If someone not a Haskell afficionado wishes to answer "What is a Attribute Grammar", the article at is of course quite concise and neutral. Although Luke's POD is a pretty good tutorial as is.
Question. Do I understand that your AG class implements the synthetic and inherited Attributes for a data-structure already parsed and created by Parse::RecDescent or whatever? In which case -- pending a marriage of the two modules -- a pre-processor to extract P:RD grammars and AG grammars from a superset language may be needed.
Re:A simpler reference and a question
luqui on 2005-09-28T04:18:53
Thank you for the POD compliment, though I do think I need to rewrite it. I was in a coding mood, not a writing mood, when I wrote it.
The AG modle works on any blessed data structure, actually, so yes, presumably P::RD already created it. I can see such a preprocessor coming in useful when I add structure specification, but at the moment, I don't think it would buy you anything. There is no redundant information there. A very simple preprocessor that would allow you to interleave an AG and a BNF may be mildly beneficial, though.
Luke
