Van Wyk et al. (2010) — Silver: An Extensible Attribute Grammar System

The paper

E. Van Wyk, D. Bodin, J. Gao, and L. Krishnan, “Silver: An extensible attribute grammar system,” Science of Computer Programming, vol. 75, no. 1-2, pp. 39–54, 2010.

doi:10.1016/j.scico.2009.07.004 · read the paper

A summary of the paper and how gen uses it.

Paper Summary

Van Wyk, Bodin, Gao, and Krishnan present Silver, an attribute grammar specification language designed to be extensible — both as a tool for specifying extensible programming languages and as an extensible language itself. The central problem is that attribute grammar systems, while offering high-level declarative specifications for language analysis and translation, suffer from a perceived lack of both domain-specific and general-purpose features needed to address the full breadth of real language engineering tasks. Users encounter an uncomfortable “split personality” when the AG system lacks pattern matching, polymorphic lists, or domain-specific constructs and must drop into an implementation language.

Silver’s solution is to treat the AG specification language itself as an extensible language. A minimal core AG language (core Silver) supports nonterminals, productions, synthesized and inherited attributes, higher-order attributes (Vogt et al. 1989), reference/decorated attributes (Hedin 2000), forwarding (Van Wyk et al. 2002), aspect productions, and a module system. This core is then extended through modular language extensions — themselves specified as AG fragments — to produce the full-featured Silver used in practice. Through bootstrapping, Silver is implemented as a Silver attribute grammar.

The paper’s primary technical contributions are:

Forwarding as an extensibility mechanism. A production may define a forwards to clause specifying a semantically equivalent tree in the host language. Queries for attributes not explicitly defined on the production are delegated to this forwarded-to tree. This enables local transformations: extension constructs translate to host-language constructs, gaining default semantics for all attributes. Crucially, forwarding allows both implicit (via the forwarded-to tree) and explicit (via attribute definitions on the extension production) specification of attribute values — a capability that purely rewrite-based systems like JastAdd cannot provide simultaneously.

Collection attributes with fold operators. Collection attributes aggregate contributions from multiple aspect productions using an associative binary operator. A collection attribute declared with collect with op receives an initial value via := and additional contributions via <- from aspect productions. The final value is v_init op v_1 op v_2 op ... op v_n. Because the operator need not be commutative but the contribution order is unspecified, the operator must in practice be used with operations (like list concatenation) where order does not affect the final result. Collection attributes enable additive global transformations — extensions can contribute new attribute definitions, error messages, or declarations without modifying existing productions.

Composable local and additive global transformations. Local transformations are implemented via forwarding. Global transformations use collection attributes on key productions (like prodDcl in the Silver grammar itself) to collect contributions from extensions. The collecting production forwards to an expanded production containing both original and contributed definitions. This two-production pattern (collector + expanded) creates extension points that independent extensions can use without knowledge of each other. The paper demonstrates this concretely with pattern matching, where prodName and childList attribute definitions are added to every production in the object grammar via aspect contributions to the moreStmts collection on prodDcl.

Composability guarantees for concrete syntax. Silver integrates with Copper, a context-aware scanner/parser generator where the parser passes valid lookahead sets to the scanner. When extensions satisfy a set of restrictions on their concrete syntax, the composed grammar is guaranteed conflict-free (Schwerdfeger & Van Wyk 2009).

The paper demonstrates these mechanisms through: (1) the SimpleC imperative language specification with forwarding for for-loops and logical-or; (2) the with-clause convenience extension; (3) pattern matching as a local+global transformation; (4) concise concrete syntax as Yacc-style sugar; (5) data-flow analysis via CTL model checking over control flow graphs constructed from AST attributes. The composition of core Silver and all extensions into silver:full via import ... with syntax demonstrates the modularity claim.

Key Concepts

• Forwarding — A production defines a distinguished tree providing default values for unspecified synthesized attributes. Queries for attributes without explicit definitions are delegated to the forwarded-to tree. Enables local translation of extension constructs to host-language equivalents while retaining the ability to override specific attribute values explicitly.

• Collection attributes — Multi-contributor attribute aggregation. Declared with collect with <op>, assigned initial values with :=, extended with contributions via <- in aspect productions. The fold operation combines initial value and all contributions using the specified associative operator. Enables additive (non-destructive) extension of existing productions.

• Aspect productions — Allow new attribute definitions to be added to existing productions from separate grammar modules. The mechanism for extensions to define attribute values on host-language productions without modifying the original specification.

• Higher-order attributes — Attributes whose values are (undecorated) syntax trees. Essential for Turing completeness and for constructing intermediate representations like type representations (TRep), symbol tables, or optimized program trees.

• The collector/expanded pattern — A concrete production collects extension contributions via a collection attribute, then forwards to an abstract production that includes both original and collected definitions. This pair creates an extension point. Demonstrated with prodDcl (collector) and prodDcl_expanded (expanded) in Silver’s own grammar.

• Additive global transformations — Global transformations where extensions add new constructs (declarations, definitions) without reorganizing existing program structure. Two requirements: the transformation is strictly additive, and additions from different extensions do not conflict. Enabled by collection attributes on key productions.

• Context-aware scanning — Parser passes valid lookahead sets to the scanner, which only returns tokens in this set. Reduces parse table conflicts when composing grammars and enables verifiable composition guarantees.

• Module system — Grammar modules with unique Internet-domain-style names. import ... with syntax composes both semantic and concrete syntax specifications. hiding excludes specific items for type safety.

• Data-flow analysis via model checking — Domain-specific extension adding cfg nodes, cfg attributes, and CTL formula constructs. CFGs are constructed from AST attributes (entry, succ), labeled with data-flow attributes (def, uses), and model-checked via NuSMV. Results are available as attribute values in the AG.

How gen uses this

gen-scope: collection attributes

Silver’s collection attributes with fold operators correspond to gen-scope’s collectionAttr. In Silver, synthesized attribute errors :: [String] collect with ++ declares a collection that aggregates error lists across aspect contributions using list concatenation. In gen-scope, collectionAttr { traverse; extract; combine; } is the corresponding construct: traverse selects which nodes contribute (as Silver selects the aspect productions that contribute), extract pulls the value from each contributor (the <- contribution), and combine folds the contributions (Silver’s collect with operator). The collection is declared once, and contributions come from anywhere in the graph. gen-scope’s traverse modes ("imports", "children", "siblings", "ancestors", "neron", "label:<name>", or a function) generalize Silver’s “all aspect productions on this production” contribution model to traversals over a scope graph.

gen-scope: inherited defaults and forwarding

Silver’s forwarding, where a production delegates attribute queries to a semantically equivalent tree, parallels how gen-scope finds default attribute values. The inherit' combinator walks the parent chain until resolve returns a non-null result: when a node does not define an attribute, the query goes up the tree. gen-scope delegates to the parent chain rather than to a forwarded tree, but both give implicit attribute definitions through structural delegation, with explicit definitions taking priority.

gen-schema: collections

A gen-schema kind declares methods and user-defined collection fields. Collections are extracted from the kind’s definitions before the module merge and exposed on the merged result, and computed fields are derived from them afterwards. Like Silver’s collection attributes, a collection is declared once on the kind and several sources (kind definitions, extensions, mixins) contribute to it.

gen-aspects: key classification

gen-aspects classifies each aspect key by its category in cnf.keySemantics: a class key holds content for an output such as NixOS (like Silver’s translation attributes), a channel key carries a value through unchanged, a facet key mounts its own option or module, and any other key is a nested aspect (like Silver’s nested productions). Routing each kind of content through its own processing path mirrors Silver’s separation of abstract and concrete productions, with forwarding translating between them.

Further directions

Unexploited Ideas

Context-aware scanning / verifiable composition (Section 2.1.2, 4; Schwerdfeger & Van Wyk 2009). Silver’s integration with Copper enables guaranteed conflict-free composition of independently developed grammar extensions. The gen ecosystem has no analogue for verifiable composition — there is no static analysis that guarantees two independently developed aspects or rules will not conflict when composed. The closest mechanism is gen-dispatch’s conflict resolution (overrides, priority, exclusive mode), which resolves conflicts at dispatch time rather than preventing them at composition time.

Data-flow analysis via model checking (Section 3.4). Silver’s extension for specifying data-flow analyses as temporal logic formulas model-checked on control flow graphs is entirely unexploited. While gen-scope constructs scope graphs, not control flow graphs, the methodology of integrating external analysis tools via attribute grammar extensions is applicable. Configuration validation could be expressed as properties over the scope graph structure.

Autocopy inherited attributes (Section 2.2, Fig. 3). Silver’s autocopy attribute modifier automatically copies inherited attribute values from parent to children when no explicit definition is given. gen-scope’s inherit' combinator provides on-demand parent-chain walks, but there is no mechanism for declaring that an attribute should be automatically propagated downward through all child nodes without explicit per-node definitions. In large scope graphs with many inherited attributes, this could reduce boilerplate.

Production modifiers and visibility (Section 3.2, Fig. 8). The production attribute modifier in Silver makes a local attribute visible on all aspect productions of a given production. gen-scope’s attribute model does not distinguish between attributes visible to aspect-like extensions and those that are purely local to a node’s attribute computation.

Research Directions

Extension point discovery. Silver’s collector/expanded pattern requires the host language designer to explicitly create extension points. gen’s rules create implicit extension points: any scope can be extended by any rule. Whether explicit extension point declaration (as in Silver) produces more predictable composition than implicit extension points is an open question with practical implications for rule design.

Circular attributes in collection contexts. Silver explicitly notes that circular attributes are difficult to add as a language extension because they change the fixpoint operation of the evaluator (Section 5). gen-scope supports both circular (fixpoint iteration) and collectionAttr (traversal aggregation) independently, but their interaction — a circular attribute whose iteration depends on collection attribute values that themselves change across iterations — is not well-characterized. Silver’s observation suggests this interaction may require careful design rather than ad-hoc composition.