/ 
Language-AttributeGrammar-0.01
River stage zero No dependents
/ Language::AttributeGrammar

NAME

Language::AttributeGrammar - Attribute grammars for executable syntax trees and other stuff.

SYNOPSIS

my $grammar = new Language::AttributeGrammar <<'END_GRAMMAR';
# find the minimum of a tree from the leaves up
Leaf:   min($$) = { $.value }
Branch: min($$) = { List::Util::min(min($.left), min($.right)) }

# find the global minimum and propagate it back down the tree
Root:   gmin($.tree)  = { min($.tree) }
Branch: gmin($.left)  = { gmin($$) }
      | gmin($.right) = { gmin($$) }

# reconstruct the tree with every leaf replaced with the minimum value
Leaf:   result($$)    = { Leaf->new(gmin($$)) }
Branch: result($$)    = { Branch->new(result($.left), result($.right)) }
Root:   result($$)    = { result($.tree) }
END_GRAMMAR

# This grammar expects that you define these classes:
#                Root   (with a ->tree attribute)
#                Branch (with a ->left and ->right attribute)
#                Leaf   (with a ->value attribute)

# Use the grammar
my $tree = Root->new( Branch->new( Leaf->new(1), 
                                   Branch->new( Leaf->new(2), Leaf->new(3))));
                                   
# Apply the attribute grammar to the data structure
my $atree = $grammar->apply($tree);

# Fetch synthesized attributes of the root node:
my $result = $atree->result;   # gives Branch(Leaf(1), Branch(Leaf(1), Leaf(1)));

DESCRIPTION

This module implements simple (for now) Attribute Grammar support for Perl data structures. An attribute grammar is a way to specify computation over a predefined data structure, say, as generated by Parse::RecDescent. This is done by associating attributes with the nodes of the data structure.

There are two types of attributes: synthesized and inherited. Synthesized attributes propagate bottom-up, that is, they use information from the children of a node to infer the attribute's value on that node. Inherited attributes are the exact opposite: they use information from a node in the structure to infer attributes on its chilren.

In the example above in the synopsis, the min attribute is synthesized, since it takes the values at the leaves and infers the minimum at a branch. The gmin (global minimum) attribute is inherited, since it uses gmin that was computed at the root node and propagates it downward to the leaves.

Syntax

Some special variables are used in throughout the definitions:

  • $$

    The current node.

  • $.foo

    The child node named foo of the current node.

The grammar definition is composed of a series of semantics definitions. An example semantic definition is:

Foo, Bar: baz($$)       = { baz($.child) }
        | quux($.child) = { quux($$) }

This specifies the implementations of the synthesized attribute baz and the inherited attribute quux for nodes of type Foo and Bar. That is, you can find the baz attribute of the current node by looking at the baz attribute of its child, and you can find the quux attribute of any node's child by looking at the quux attribute of the node itself.

The $.child notation is defined to pretty much do the right thing. But, in the name of predictability, here are the semantics:

If $$ has a method named child (for the attribute $.child), then that method is called with no arguments to fetch the attribute. Otherwise, if $$ is a blessed hash, then the module snoops inside the hash and pulls out the key named "child". If the hash has no such key, or the object is not a blessed hash (eg. a blessed array), then we give up.

If your tree has a different convention for extracting child nodes, you can always use $$ explicitly:

Cons:  sum($$) = { $$->get_child('head') + sum($$->get_child('tail')) }
Nil:   sum($$) = { 0 }

Cons:  gsum($$->get_child('head')) = { gsum($$) }

In the future I may provide a callback that allows the user to define the meaning of $.child.

Usage

After you have a grammar specification in a string, create a new grammar object:

my $grammar = Language::AttributeGrammar->new($grammar_string);

This contains a minimal data structure of the semantics definitions. In order to use it on a data structure, apply it to the data structure:

my $attr_data = $grammar->apply($data);

This is not the data structure in any form, really. It's just an object on which you can call methods to fetch attributes on the top node of $data. To get the "min" attribute on $data, call:

my $min = $attr_data->min;

In order to find attributes on nodes that are lower in the structure, you must concoct your attribute grammar to propagate that information up the tree somehow. Usually this is done using a synthesized attribute that mirrors the given data structure.

This module is designed to be used functionally, that is, you shouldn't change the data structure or any global state within the definitions. Instead, return a new data structure with the information you need embedded in it.

AUTHOR

Luke Palmer <lrpalmer gmail com>