Chapter 4. Attribute Grammars

Table of Contents

4.1. Introduction
4.2. Attribute Grammars in Happy
4.2.1. Declaring Attributes
4.2.2. Semantic Rules
4.3. Limits of Happy Attribute Grammars
4.4. Example Attribute Grammars

4.1. Introduction

Attribute grammars are a formalism for expressing syntax directed translation of a context-free grammar. An introduction to attribute grammars may be found here. There is also an article in the Monad Reader about attribute grammars and a different approach to attribute grammars using Haskell here.

The main practical difficulty that has prevented attribute grammars from gaining widespread use involves evaluating the attributes. Attribute grammars generate non-trivial data dependency graphs that are difficult to evaluate using mainstream languages and techniques. The solutions generally involve restricting the form of the grammars or using big hammers like topological sorts. However, a language which supports lazy evaluation, such as Haskell, has no problem forming complex data dependency graphs and evaluating them. The primary intellectual barrier to attribute grammar adoption seems to stem from the fact that most programmers have difficulty with the declarative nature of the specification. Haskell programmers, on the other hand, have already embraced a purely functional language. In short, the Haskell language and community seem like a perfect place to experiment with attribute grammars.

Embedding attribute grammars in Happy is easy because because Haskell supports three important features: higher order functions, labeled records, and lazy evaluation. Attributes are encoded as fields in a labeled record. The parse result of each non-terminal in the grammar is a function which takes a record of inherited attributes and returns a record of synthesized attributes. In each production, the attributes of various non-terminals are bound together using let. Finally, at the end of the parse, a distinguished attribute is evaluated to be the final result. Lazy evaluation takes care of evaluating each attribute in the correct order, resulting in an attribute grammar system that is capable of evaluating a fairly large class of attribute grammars.

Attribute grammars in Happy do not use any language extensions, so the parsers are Haskell 98 (assuming you don't use the GHC specific -g option). Currently, attribute grammars cannot be generated for GLR parsers (It's not exactly clear how these features should interact...)