Sharing Trees and Contextual Information: Re-imagining Forwarding in Attribute GrammarsResearch Paper
It is not uncommon to design a full-featured programming language around a smaller core language so that other features may explicitly define some semantic analyses or tasks but delegate others to their translation into the core. Semantic analyses typically require contextual information, such as a typing environment. When this context is the same for a term appearing under a new feature and the translation then the term’s tree, and the computations over it, can be shared with context provided by the translation to avoid redundant, and sometimes exponential computations. Forwarding is a technique in attribute grammars that makes the delegation of semantic tasks automatic, permitting independent language extensions to work together. Here we describe mechanisms that allow forwarding to share trees and specifications of contextual information (as inherited attributes) between a feature and its core translation. We evaluate these techniques by applying them to language features in the ableC extensible C compiler and find that they replace around 80% of the instances in which sharing of trees was achieved by a crude mechanism that prevented sharing the specification of context and limited language extensibility. This avoided all instances in which this mechanism was used to avoid exponential computations. The techniques also allowed the removal of many, now not needed, inherited attribute equations.
Mon 23 OctDisplayed time zone: Lisbon change
14:00 - 15:30 | Grammars and parsingSLE at Room II Chair(s): Luis Eduardo de Souza Amorim Australian National University, Australia | ||
14:00 30mTalk | A reference GLL implementationResearch Paper SLE Adrian Johnstone Royal Holloway University of London, UK DOI | ||
14:30 30mTalk | Sharing Trees and Contextual Information: Re-imagining Forwarding in Attribute GrammarsResearch Paper SLE Lucas Kramer University of Minnesota, Eric Van Wyk Department of Computer Science and Engineering, University of Minnesota, USA DOI Pre-print | ||
15:00 30mTalk | Nanopass Attribute GrammarsResearch Paper SLE Nathan Ringo University of Minnesota, Lucas Kramer University of Minnesota, Eric Van Wyk Department of Computer Science and Engineering, University of Minnesota, USA DOI Pre-print |