Minnesota Extensible Language Tools
Persistent link for this communityhttps://hdl.handle.net/11299/206558
About the MELT research group
Our main research interests are in declarative specifications for programming language syntax, semantics, and optimizing transformations. We are specifically interested in techniques that lead to a high degree of modularity in the composition of language specifications. We have designed a few unique tools that automatically compose and implement such specifications to create pre-processors, compilers and optimizers for the newly specified languages.
Visit the MELT research group webpage: http://melt.cs.umn.edu/
There may be newer, unarchived versions of this software at http://melt.cs.umn.edu.
Browse
Browsing Minnesota Extensible Language Tools by Issue Date
Now showing 1 - 13 of 13
- Results Per Page
- Sort Options
Item Context-aware scanning and determinism-preserving grammar composition, in theory and practice(2010-07) Schwerdfeger, AugustThis thesis documents several new developments in the theory of parsing, and also the practical value of their implementation in the Copper parser generator. The most widely-used apparatus for syntactic analysis of programming languages consists of a scanner based on deterministic finite automata, built from a set of regular expressions called the lexical syntax, and a separate parser, operating on the output of this scanner, built from a context-free grammar and utilizing the LALR(1) algorithm. While the LALR(1) algorithm has the advantage of guaranteeing a non-ambiguous parse, and the approach of keeping the scanner and parser separate make the compilation process more clean and modular, it is also a brittle approach. The class of grammars that can be parsed with an LALR(1) parser is not closed under grammar composition, and small changes to an LALR(1) grammar can remove the grammar from the LALR(1) class. Also, the separation of scanner and parser prevent the use, in any organized way of parser context to resolve ambiguities in the lexical syntax. One area in which both of these drawbacks pose a particular problem is that of parsing embedded and extensible languages. In particular, it forms one of the last major impediments to the development of an extensible compiler in which language extensions are imported and composed by the end user (programmer) in an analogous manner to the way libraries are presently imported. This is due not only to the problem of the LALR(1) grammar class not being closed under composition, but to the very real possibility that the lexical syntax of two different extensions will clash, making it impossible to construct a scanner without extensive manual resolution of ambiguities, if at all. This thesis presents three innovations that are a large step towards eliminating parsing as an Achilles’ heel in this application. Firstly, it describes a new algorithm of scanning called context-aware scanning, in which the scanner at each scan is made aware of what sorts of tokens are recognized as valid by the parser at that point. By allowing the use of parser context in the scanner to disambiguate, context-aware scanning makes the specification of embedded languages much simpler — instead of specifying a scanner that must explicitly switch “modes” to scan on the different embedded languages, one simply compiles a context-aware scanner from a single lexical specification, which has implicit “modes” to scan properly on each embedded language. Similarly, in an extensible language, this puts a degree of separation between the lexical syntax of different language extensions, so that any clashes of this sort will not be an issue. Secondly, the thesis describes an analysis that operates on grammar extensions of a certain form, and can recognize their membership in a class of extensions that can be composed with each other and still produce a deterministic parser—enabling end-users to compose extensions written by different language developers with this guarantee of determinism. The analysis is made practical by context-aware scanning, which ensures a lack of lexical issues to go along with the lack of syntactic nondeterminism. It is this analysis — the first of its kind — that is the largest step toward realizing the sort of extensible compiler described above, as the writer of each extension can test it independently using the analysis and thus resolve any lexical or syntactic issues with the extension before the end user ever sees it. Thirdly, the thesis describes a corollary of this analysis, which allows extensions that have passed the analysis to be distributed in parse table form and then composed on-the-fly by the end users, with the same guarantee of determinism. Besides expediting the operation of composition, this also enables the use of the analysis in situations where the writer of a language or language extension does not want to release its grammar to the public. Finally, the thesis discusses how these approaches have been implemented and made practical in Copper, including runtime tests, implementations and analyses of real-world grammars and extensions.Item Composable semantics using higher-order attribute grammars(2012-11) Manjacheri, Lijesh KrishnanIdeally, 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.Item A Modular Specification of Oberon0 Using the Silver Attribute Grammar System(2015-10-13) Kaminski, Ted; Van Wyk, Eric; evw@umn.edu; Van Wyk, EricThis repository contains the implementation of Oberon0 using the Silver attribute grammar system for the Tool Challenge at the 2011 International Workshop on Language Descriptions, Tools, and Applications. Silver was developed to study how independently-developed language extension specifications can be imported into a host language specification to define a new custom extended language. Thus it contains many features useful in modular language specification, such as forwarding, higher-order attributes, reference/remote attributes, and a simplified form of collection attributes. These are discussed in the context of the Oberon0 specification presented here. This is the specification accompanying the paper "A modular specification of Oberon0 using the Silver attribute grammar system" by Ted Kaminski and Eric Van Wyk.Item Reliably composable language extensions(2017-05) Kaminski, TedMany programming tasks are dramatically simpler when an appropriate domain-specific language can be used to accomplish them. These languages offer a variety of potential advantages, including programming at a higher level of abstraction, custom analyses specific to the problem domain, and the ability to generate very efficient code. But they also suffer many disadvantages as a result of their implementation techniques. Fully separate languages (such as YACC, or SQL) are quite flexible, but these are distinct monolithic entities and thus we are unable to draw on the features of several in combination to accomplish a single task. That is, we cannot compose their domain-specific features. "Embedded" DSLs (such as parsing combinators) accomplish something like a different language, but are actually implemented simply as libraries within a flexible host language. This approach allows different libraries to be imported and used together, enabling composition, but it is limited in analysis and translation capabilities by the host language they are embedded within. A promising combination of these two approaches is to allow a host language to be directly extended with new features (syntactic and semantic.) However, while there are plausible ways to attempt to compose language extensions, they can easily fail, making this approach unreliable. Previous methods of assuring reliable composition impose onerous restrictions, such as throwing out entirely the ability to introduce new analysis. This thesis introduces reliably composable language extensions as a technique for the implementation of DSLs. This technique preserves most of the advantages of both separate and "embedded" DSLs. Unlike many prior approaches to language extension, this technique ensures composition of multiple language extensions will succeed, and preserves strong properties about the behavior of the resulting composed compiler. We define an analysis on language extensions that guarantees the composition of several extensions will be well-defined, and we further define a set of testable properties that ensure the resulting compiler will behave as expected, along with a principle that assigns "blame" for bugs that may ultimately appear as a result of composition. Finally, to concretely compare our approach to our original goals for reliably composable language extension, we use these techniques to develop an extensible C compiler front-end, together with several example composable language extensions.Item Silver: an Attribute Grammar System(2017-08-24) Kaminski, Ted; Kramer, Lucas; Michaelson, Dawn; Van Wyk, Eric; evw@umn.edu; Van Wyk, Eric; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools GroupSilver is an attribute grammar system which supports higher-order, reference, and collection attributes. It also supports forwarding and provides a modular well-definedness analysis to ensure composability of language extensions. There may be newer, unarchived versions of this software at http://melt.cs.umn.edu.Item ableC: Extensible Specification of C Using the Silver Attribute Grammar System(2017-08-24) Kaminski, Ted; Kramer, Lucas; Carlson, Travis; Van Wyk, Eric; evw@umn.edu; Van Wyk, Eric; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools GroupThis is the Silver specification of ableC: a specification of C at the ISO C11 standard. There may be newer, unarchived versions of this software at http://melt.cs.umn.edu.Item Silver-ableC: a Silver extension for writing ableC specifications(2019-09-05) Kramer, Lucas; Van Wyk, Eric; evw@umn.edu; Van Wyk, Eric; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools GroupSilver-ableC is an extension to the Silver attribute grammar system for writing ableC language specifications. It allows language developers to specify C language constructs using the concrete syntax of C instead of the more verbose and inconvenient abstract syntax.Item A Silver implementation of a subset of MetaOCaml(2019-09-06) Kramer, Lucas; Van Wyk, Eric; evw@umn.edu; Van Wyk, Eric; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools GroupThis is an implementation of a subset of MetaOCaml in Silver. It makes use of reflection in Silver in the MetaOCaml interpreter.Item Parallel nondeterministic programming as a language extension in ableC(2019-09-11) Kramer, Lucas; Van Wyk, Eric; evw@umn.edu; Van Wyk, Eric; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools GroupThis is an ableC language extension for parallel nondeterministic programming. It includes the Silver sources of the extension and a number of applications build using it. There may be newer, unarchived versions of this software at http://melt.cs.umn.edu.Item An implementation of the lambda calculus in Silver(2020-04-06) Kramer, Lucas; Van Wyk, Eric; evw@umn.edu; Van Wyk, Eric; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools GroupThis repository contains an implementation of the lambda calculus that uses the reflection-based term-rewriting extension to Silver. There may be newer, unarchived versions of this software at http://melt.cs.umn.edu.Item A Silver implementation of Caml Light(2020-10) Michaelson, Dawn; Van Wyk, Eric; evw@umn.edu; Eric Van Wyk; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools GroupItem Software Artifact for Nanopass Attribute Grammars(2023-09-06) Ringo, Nathan; Kramer, Lucas; Van Wyk, Eric; evw@umn.edu; Van Wyk, Eric; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools (MELT) GroupThis repository contains the software artifact accompanying the paper "Nanopass Attribute Grammars" included in the October 2023 ACM SIGPLAN Conference on Software Language Engineering.Item Software Artifact for Reimagining Forwarding in Attribute Grammars(2023-09-06) Kramer, Lucas; Van Wyk, Eric; evw@umn.edu; Van Wyk, Eric; University of Minnesota, Department of Computer Science and Engineering, Minnesota Extensible Language Tools (MELT) GroupThis repository contains the software artifact accompanying the paper "Sharing Trees and Contextual Information: Re-imagining Forwarding in Attribute Grammars" included in the October 2023 ACM SIGPLAN Conference on Software Language Engineering.