Stories
Slash Boxes
Comments
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)

Monday September 26, 2005
11:23 PM

Attribute Grammars

[ #26894 ]

Thanks to two handy references from Autrijus (http://www.cs.uu.nl/wiki/Center/AttributeGrammarSystem and http://www.haskell.org/tmrwiki/WhyAttributeGrammarsMatter), 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.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • 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 [wikipedia.org] is of course quite concise and neutral. Although Luke's POD [cpan.org] 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

    --
    Bill
    # I had a sig when sigs were cool
    use Sig;
    • 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