Attribute Grammars and Their Applications

Introduction

• Attribute grammars are a framework for defining semantics of programming languages in a syntax-directed fashion. In this chapter, we define attribute grammars, and then illustrate their use for language definition, compiler generation, definite clause grammars, design and specification of algorithms, and so forth. Our goal is to emphasize its role as a tool for design, formal specification and implementation of practical systems, so our presentation is example rich.

Background

The lexical structure and syntax of a language is normally defined using regular expressions and context-free grammars respectively (Aho, Lam, Sethi & Ullman et al., 2007,). Knuth (1968) introduced attribute grammars to specify static and dynamic semantics of a programming language in a syntax-directed way.

Let G = (N, T, P, S) be a context-free grammar for a language L (Aho et al., 2007). N is the set of non-terminals. T is the set of terminals. P is the set of productions. Each production is of the form A::= α, where A ∈ N and α ∈ (N U T)*. S ∈ N is the start symbol. An attribute grammar AG is a triple (G, A, AR), where G is a context-free grammar for the language, A associates each grammar symbol X ∈ N U T with a set of attributes, and AR associates each production R ∈ P with a set of attribute computation rules (Paakki, 1995). A(X), where X ∈ (N U T), can be further partitioned into two sets: synthesized attributes S(X) and inherited attributes I(X). AR(R), where R ∈ P, contains rules for computing inherited and synthesized attributes associated with the symbols in the production R.

Consider the following attribute grammar that maps bit strings to numbers. CFG = ({N},{0,1},P,N), where P is the left column of productions shown below. The number semantics is formalized by associating a synthesized attribute val with N, and providing rules for computing the value of the attribute val associated with the left-hand side N (denoted N_l) in terms of the value of the attribute val associated with the right-hand side N (denoted N_r), and the terminal.

N::= 0 N.val = 0
N::= 1 N.val = 1
N::= N0 Nl.val = 2 * Nr.val
N::= N1 Nl.val = 2 * Nr.val + 1

An attribute grammar involving only synthesized attributes is called an S-attributed grammar. It is straightforward to parse a binary string using this grammar and then compute the value of the string using a simple top-down left-to-right traversal of the abstract syntax tree.

The above attribute grammar is not unique. One can construct a different S-attributed grammar for the same language and the same semantics as follows.

N::= 0 N.val = 0, N.len = 1
N::= 1 N.val = 1, N.len = 1
N::= 0N Nl.val = Nr.val;
Nl.len = Nr.len +1
N::= 1N Nl.val = 2^ Nr.len + Nr.val;
Nl.len = Nr.len +1

Attribute grammars can be devised to specify different semantics associated with the same language. For instance, the bit string can be interpreted as a fraction by associating an inherited attribute pow to capture the left context—the length of the bit string between left of a non-terminal and the binary point, to determine the local value or the weight of the bit.

F::= . N F.val = N.val, N.pow = 1
N::= 0 N.val = 0
N::= 1 N.val = (1 / 2^ N.pow)
N::= 0N Nl.val = Nr.val;
Nr.pow = Nl.pow +1
N::= 1N Nl.val = (1 / 2^ N.pow) + Nr.val;
Nr.pow = Nl.pow +1