Attribute Grammars: Composable and Modular Language Specifications

Eric Van Wyk

Date: Mon, June 17, 2019
Time: 10:30
Room: Colloquiumzaal 0.E420

Attribute grammars were invented in 1968 by Donald Knuth as a formalism for specifying the semantics of context free languages. Attributes decorate syntax tree nodes to indicate, for example, the type of an expression or the environment for looking up identifier types or values. Equations over attributes determine these values. Since then the formalism’s popularity had waxed and waned but has been continually extended with new features to become an expressive paradigm for specifying many kinds of analyses and translations of programming languages. This talk will cover several of these extensions; including higher-order attributes, in which attributes can themselves be syntax trees, reference attributes, in which attributes are references to other nodes in the decorated tree, and forwarding, a mechanism that supports the composition of language extension specifications.

This talk will demonstrate several of these features as they are realized in the Silver attribute grammar system. Examples are drawn from ableC, an extensible specification of C written in Silver, and several language extensions that add new syntax and static semantics to the C host language. These include extensions for parallel programming inspired the by Cilk, Halide, and Taco systems, ML-style algebraic data types with pattern matching, regular expression literals and matching, and others. Silver was designed to support the automatic composition of independently-developed language extensions such as these. This allows programmers to import new features into their compilers with the same ease as which they import libraries into their programs. Static analyses and constructs in Silver that support this style of modular language design are a focus of the demonstrations.

Previous: |
Next: Eric Van Wyk |