Simple, Functional Attribute Grammars

(Updated: 24-Oct--1999)

Click here to return to the main page.


Table of Contents


Why these Combinators?

Have you always been intrigued by Attribute Grammars because they allow you to:

but you do not like:

then why not use my simple attribute grammar system?

The UU_AG system is a very simple program that reads a set of files containing an attribute grammar, in which semantic functions are described through Haskell expressions. Out of this description catamorphisms and data type definitions are generated.

I hope this software is useful to you. If you have any comments do not hesitate to contact me.

Doaitse Swierstra

(back to table of contents)


Change Log

If you want to stay informed about changes and corrections you should send me an email.

(back to table of contents)


Where to get software

You need the following file:

Furthermore you may be interested in the additional files, that are imported by the system:

(back to table of contents)


Conditions for use

I have been asked about any copyright associated with these files. Since I do not want to get too deeply involved in all kinds of legalese I have included a slightly adapted version of the artistic license that came with my version of Hugs. It seems to capture nicely what is my intent with this package. 

I would be happy it you would let me know:

(back to table of contents)


The Attribute Grammar Language

Before looking at the grammar you might want to first look at the example session.

The Main Structure of the Input

We start with providing the full grammar of the accepted input, as expressed by the parsing part of the UU_AG file:

parser      = parse pAG

The input consists of a list of separate textual elements, each representing a small contribution to the complete grammar. Such grammar fragments may even be distributed over several files, according to the conventions stemming from the use of the standard UU scanning library

pAG         =     foldl sem_Elems_One_Elem sem_Elems_No_Elem 
              <$> pList pElem

Each element in this list:

pElem =

either represents:

             sem_Elem_Data     <$  pKey "DATA"   
                               <*> pConid  <*> pAttrs 
                               <*> pAlts sem_Alt
        <|>  sem_Elem_AttrsDef <$  pKey "ATTR"   
                               <*> pList pConid   <*> pAttrs 
        <|>  sem_Elem_Rules    <$  pKey "SEM"    
                               <*> pConid         <*> pAttrs 
                               <*> pAltRules
        <|>  sem_Elem_Data     <$  pKey "EXT"    
                               <*> pConid         <*> pAttrs 
                               <*> pAlts sem_Alt'
        <|>  sem_Elem_Pre      <$  pKey "PRE"    <*> pVarid
        <|>  sem_Elem_Txt      <$> pTextnm       <*> pList pTextln

Defining Grammar Rules

pAlts  sem  =   applyall <$> pListPrefixed (pSpec '|') (sem <$> pConid <*>  pFields)

Defining Attributes

pAttrs      
 =  pBracks ((,,) <$>              pAttrNames 
                  <* pSpec '|' <*> pAttrNames 
                  <* pSpec '|' <*> pAttrNames 
            ) `opt` ([], [], [])

pAttrNames  
=  concat <$> pList (
      sem_Attrs   <$>  pCommas  pNameDef 
                  <*> (( (,) <$ pKey "USE" <*> pString <*> pString) `opt` ("","")) 
                  <*> ( pKey ":" *> pConid)
                    ) 

Defining Semantic Functions

pFields     =   applyall <$> pList pField 

pField      =           sem_Field                  <$> pCommas pVarid <* pKey ":" <*> pConid
             <|> (\s -> sem_Field [(mklower s)] s) <$>                                pConid
  
pAltRules   = pFoldrPrefixed compose_alg  (pSpec  '|') pAltRule 
pAltRule    = sem_AltRule        <$>  pConid   <*> pFieldRules

pFieldRules 
  = pFoldr compose_alg 
       (   sem_FieldRule    <$>  (pVarid  
                            <|>  pKey "LHS") <*> pAttrRules (Ident <$> pVarid)
       <|> sem_FieldRule    <$>  pKey "LOC"  <*> pAttrRules pNameDef 
       )
                                         
pAttrRules pname = pFoldrPrefixed compose_alg (pSpec '.') (pAttrRule pname) 

pAttrRule  pname = sem_AttrRule <$> pname <*> (pKey "=" <|> pKey ":=")  <*> pAttrExpr

pAttrExpr = (((\s-> "("++s++")") <$> pString) <|> pVarid <|> pConid)


pNameDef    =     LocalDef <$> pVarid      <*> ( pSpec '@' *> pPattern `opt` NoPat ) 
              <|> LocalDef <$> pSucceed "" <*>                pPattern 
                             

pPattern =  Product  <$> pParens (pListSep (pSpec ',') pSimplePattern)
pSimplePattern =       Var        <$>  pVarid
                  <|>  Constr     <$>  pConid <*> pList pSimplePattern
                  <|>                  pPattern
                  <|>  Underscore <$   pSpec '_'

Extending Productions

Defining Prefixes

Adding Text to the Generated System

(back to table of contents)


An Example Session.

As a first example we take the well known RepMin problem. The input of the program is a binary tree, and it produces a binary tree of the same shape. In the new tree however all values in the leaves are equal to the minimum of the values in the leafs in the original tree. We will show two versions: the full version in which all semantic functions made explicit, and one in which many shorthand notation is used.

The Full Version

The full code of this example is given in RepMin1.ag. We start by defining the structure of the tree. One might look at this both as a piece of abstract grammar, with two nonterminals, or as two data type definitions. The difference with a Haskell data type definition is that the fields are associated with a name, and not only by position.

\BC   -- we start each piece of attribute grammar code with \BC since the system works in literate mode
DATA Tree
  | Leaf int: Int
  | Bin  left, right: Tree
  
DATA Root | Root  tree: Tree

We split the computation to be performed into three different aspects:

For the computation of the minimal value we introduce one synthesised attribute m:

ATTR Tree [   |  | m: Int ]

That this is an synthesised attribute follows from the fact that the attribute specification is located after the second vertical bar |. Next we specify the computation of the minimum value by providing semantic rules. Such rules may be grouped by non-terminal and by production. In the next two rules we see the non-terminal that applies (Tree), the alternative for which the rule is defined (Leaf or Bin), the element of the alternative to which the attribute that is being defined is associated (in this case the left hand side of the production that is always called LHS), the attribute that is being defined (m), and the Haskell expression that describes the computation . This Haskell expression is either a complicated expression, in which case we represent is as a string ("left_m `min` right_m"), or a simple identifier (int).

SEM Tree
  | Leaf LHS  .m      = int
  | Bin  LHS  .m      = "left_m `min` right_m"

Next we introduce an inherited attribute (minval) that describes how the computed minimal value is passed from the root of the tree to the leaves. That this is an inherited attribute stems from the fact that its definition occurs before the first vertical bar. In the Haskell expression we may refer to other accessible attributes by mean's of the identifier <element name>_<attribute name>. In order to refer to the inherited attributes of the right hand side we prefix the name of the attribute by lhs_.

ATTR Tree [ minval: Int ||]
SEM Tree
  | Bin  left .minval = lhs_minval
         right.minval = lhs_minval

The third step concerns the computation of the resulting tree, which follows the computation of the minimum value:

ATTR Tree [ | | res: Tree ]
SEM Tree
  | Leaf LHS  .res    = "Tree_Leaf lhs_minval"
  | Bin  LHS  .res    = "Tree_Bin  left_res right_res"

Finally we have to tie the knot at the root of the problem: the value that is computed as the minimum value is the value that should be passed down the tree, and as a result we are only interested in the constructed tree, and not in that minimum value.

ATTR Root [|| res: Tree ]
SEM Root
  | Root tree .minval = tree_m
         LHS  .res    = tree_res
\EC  -- we end each piece of attribute grammar code with \EC since the system works in literate mode

This input can be compiled as in the following session:

UU_AG> compile "Repmin1" allc
Repmin1.hs generated
(159277 reductions, 321908 cells)
UU_AG> 

The value allc has been defined as:

 

allc = "mdcs"

in which the meaning of the characters is:

The code generated by the attribute grammar system, with all options enabled is:

-- The module header : RepMin1 ----------------------------
module RepMin1 where
-- The data type definition: Tree -------------------------
data Tree = Tree_Leaf Int| Tree_Bin Tree Tree
          deriving Show
-- The signatures for the semantic functions --------------
type T_Tree =  Int ->(Tree,Int)
-- The semantic functions (which are always generated) ----
sem_Tree_Leaf ::Int -> T_Tree
sem_Tree_Leaf int lhs_minval =  ( (Tree_Leaf lhs_minval), int ) 
sem_Tree_Bin :: T_Tree -> T_Tree -> T_Tree
sem_Tree_Bin left right lhs_minval 
   = let{ ( left_res, left_m )  = left lhs_minval
        ; ( right_res, right_m )  = right lhs_minval
        }
     in  ( (Tree_Bin left_res right_res), (left_m `min` right_m) ) 
-- The data type definition: Root -------------------------
data Root = Root_Root Tree
          deriving Show
-- The signatures for the semantic functions --------------
type T_Root =  Tree
-- The semantic functions (which are always generated) ----
sem_Root_Root :: T_Tree -> T_Root
sem_Root_Root tree = let{ ( tree_res, tree_m )  = tree tree_m}in  tree_res

Shorthand Notation

The shorthand version of the above program is:

\BC
DATA Tree 
  | Leaf Int
  | Bin  left, right: Tree
  
SEM Tree [ minval: Int || m: Int  res: Tree ]
  | Leaf LHS.m   = int
            .res = "Tree_Leaf lhs_minval"
  | Bin  LHS.m   = "left_m `min` righth_m"
            .res = "Tree_Bin left_res right_res"

DATA Root [|| res: Tree ]
  | Root Tree
SEM  Root                 
  | Root tree.minval = tree_m
\EC

In this completely equivalent program we can notice the following abbreviations:


Copy Rule Generation

In case no definition was given for a specific atribute the system will try the following strategy in generating a definition:

  1. If there exists a local attribute, or an elememnt in the pattern of a local attribute that has the same name as the attribute for which the definition is missing, a rule is geneated through which that elemnet is referred.
  2. If the previous rule does not solve the problem, and there exists a filed in the production for which no attributes have been specified, and this field has the same name as the attribute for which the definition is missing, this filed is taken as the value to be usedfor thi attribute.
  3.  


An Example Language

We have developed a compiler for a small language in a stepwise fashion. You can find the description of the language and the associated files at the Implementation of Programming Languages course. 


Errors

The error messages are generated in a rather generic way. We hope they are self-explaining. Some further work needs to be done on making the system continue once an error was reported.

(back to table of contents)


Tips

(back to table of contents)


Still to do

(back to table of contents)