Composable semantics using higher-order attribute grammars
2012-11
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Composable semantics using higher-order attribute grammars
Authors
Published Date
2012-11
Publisher
Type
Thesis or Dissertation
Abstract
Ideally, programmers could make use of domain-specific knowledge and program using constructs that implement abstractions in their problem domains, and obtain domain-appropriate feedback. Further, new functionality could be added to existing languages incrementally, so that programmers could choose features appropriate to their problem domains, retrieve their specifications, and compose them automatically with an existing host language to generate a compiler for an extended version of the language. The library model of language extensibility separates out the stages of host language specification, extension development, and extension composition, to make the process of language extension modular. The model is targeted at writing composable semantic specifications, and emphasizes the importance of static analyses performed at extension development time to flag potential conflicts between extensions during composition.
Silver is a general-purpose, high-level framework that implements the library model of extension development. The declarative Silver specification language can be used to specify the host language concrete syntax and semantics, and independently, the extension syntax and semantics, the latter often in terms of the host language's semantics. The problem of brittle concrete syntax specifications is handled by the associated Copper tool that uses context-aware scanning to generate a parser for the extended language. The problem of specifying host language and extension semantics (such as error checking and source-level transformations) is handled via the evaluation on syntax tree nodes of functions written in the higher-order attribute grammar formalism. There are challenges to designing language semantics (such as types, environment and error-reporting) for a non-trivial host language to allow extension writers to write useful extensions that compose with other independently written extensions. An issue when generating sound and terminating generated compilers in a higher-order attribute grammar framework such as Silver is the potential for improper termination of attribute evaluation during the execution of the generated compiler.
This dissertation makes two contributions toward writing composable specifications for programming language semantics. It first looks at how a declarative, attribute grammar-based tool (extended with features such as forwarding, aspect productions and collection attributes) can be used to write host language specifications whose type systems and environments can be conveniently accessed and modified by extensions. To this end, it describes ableJ, an extensible host language specification for Java 1.4 that generates front-end translators from extended code to valid Java 1.4 code. Second, it presents a static analysis on higher-order attribute grammars that detects non-terminating tree creation during attribute evaluation. Combined with the higher-order circularity test, this analysis provides extension writers and programmers with a guarantee that the generated compiler will not fail to terminate on account of improper attribute evaluation. We have run the analysis on the ableJ host language and its extension specifications to demonstrate that the analysis is powerful enough to show termination of non-trivial grammars.
Description
University of Minnesota Ph.D. dissertation. November 2012. Major: Computer science. Advisor: Eric Van Wyk. 1 computer file (PDF); xi, 192 pages, appendices A-C.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
https://doi.org/10.24926/2012.144010
Previously Published Citation
Suggested citation
Manjacheri, Lijesh Krishnan. (2012). Composable semantics using higher-order attribute grammars. Retrieved from the University Digital Conservancy, https://doi.org/10.24926/2012.144010.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.