MELT pages

Research:

Our main research interests are in the declarative specification of programming languages semantics and transformations for optimization. We are specifically interested in techniques that lead to a high degree of modularity in the composition of language specifications. This is so that specifications for language features can be easily combined to create specifications for new languages. We are thus interested in tools that automatically compose and implement such specifications to create pre-processors, compilers and optimizers for the newly specified languages.

Motivation:

Software development is a time-consuming and error-prone process that often results in unreliable and insecure software. At least part of the reason for these undesirable results is that large semantic gap between the programmer's high-level understanding of the problem and the relatively low-level programming language in which the problem solutions are encoded. Thus, programmers cannot "say what they mean" but must encode their ideas as programming idioms at a lower level of abstraction. This wastes time and is the source of many errors.

A long range goal is to improve the software development process and the quality of the resulting software artifacts by reducing the semantic gap. Extensible languages provide a promising way to achieve this goal. An extensible language can easily be extended with the unique combination of domain-specific language features that raises the level of abstraction to that of the task at hand. The extended language provides the programmer with language constructs, optimizations, and static program analyses to significantly simplify the software development process.

Tools and Applications:

In these efforts we have developed tools for specifying the semantics and optimizing transformations of extensible languages and used them to develop a number of extensible language specifications.

  • Silver is an attribute grammar specification language (and its supporting tools) that allow for the highly-modular specification of languages. Silver has higher-order,reference, and production-valued attributes. It also supports forwarding (see the paper "Forwarding in Attribute Grammars for Modular Language Design") and collections. These features, especially forwarding, provide a high-level declarative means for modularly specifying languages and language extensions.

    More information about Silver, including papers, a Silver compiler, and Silver documentation, can be found here.

  • Copper is an integrated parser and context-aware scanner generator. It was developed to address the challenges in modularly specifying the concrete syntax of extensible languages and language extensions.

    • Scanning: In cases where different extensions want to associate the same lexeme with different tokens or specify different precedence and associativity rules for binary operators we cannot rely on traditional tools such as Lex. We have developed a scanning technique that uses the parser context to disambiguate different terminals that match the same lexeme and to treat binary operators differently in different embedded languages; for example, if an extension has operators "*" and "+" but assigns them different precedences and associativities than are assigned them in the extension's imperative host language.
    • Parsing: Traditional tools such as Yacc that rely on the construction of LR parsing tables are often quite brittle in that it is easy to introduce new concrete syntax rules (grammar productions) that cause conflicts in the generated parser tables. This brittleness is significantly mitigated by the context aware scanning described above.

    From language specifications based, as expected, on context-free grammars and regular expressions Copper generates an LR-parser and integrated context-aware scanner. Details of this approach can be found in our paper "Context-Aware Scanning for Parsing Extensible Languages".

    More information on Copper can be found here.

    • We have used Silver and the associated tools described above to implement a number of extensible languages in several projects.

    • Language extensions for data-intensive applications: In this collaborative project we are developing language extensions to simpify the development of efficient, scalable data-intensive applications. An extensible specification of ANSI C, ableC, is being developed as the host language for this effort.

    • Silver: As mentioned above, Silver itself is implemented in Silver.

    • ableJ: We previously worked on an extensible specification of Java 1.4 in Silver. This work was described in our ECOOP 2007 paper "Attribute Grammar-based Language Extensions for Java".

    Acknowledgements:

    We are very grateful to the National Science Foundation, the McKnight Foundation, the University of Minnesota, and IBM for funding different aspects of our research.