Nanopass Attribute GrammarsResearch Paper
Compilers for feature-rich languages are complex; they perform various analyses, optimizations, and often lower syntactic sugar and complex language constructs into simpler ones in the language. The nanopass compiler architecture manages this complexity by specifying the compiler as a sequence of many small transformations, over slightly different, clearly identified, versions of the language, that each perform a single well-defined action. This avoids errors that arise from attempting to solve multiple problems at once and allows for testing at each step. Attribute grammars are, unfortunately, ill-suited for this architecture, primarily because one cannot identify the many versions of the language used in the different passes in a non-verbose and type-safe way. We present a formulation of attribute grammars that addresses these concerns, called nanopass attribute grammars, by (i) identifying a collection of all language constructs and analyses (as attributes) to be used, (ii) concisely constructing specific (sub) languages from this set and transformations between them, and (iii) specifying compositions of transformations to form nanopass compilers. The collection of all features can be statically typed and individual languages can be checked for equation completeness, well-definedness, and circularity. This is done individually for each language since different productions will induce different dependencies on attributes. We evaluate the approach by implementing a significant subset of the Go programming language in a prototype nanopass attribute grammar system.
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 |