Parse Table Composition
Stratego -- Strategies for Program Transformation
Introduction
Extensible Compilers. Many extensible compilers and programming languages allow the syntax of a base language to be extended to introduce new syntactic abstractions. For example, the extensible compilers ableJ (based on Silver), the JastAdd extensible Java compiler, Polyglot, and MetaBorg support the development of language extensions. The focus of these tools is on optimizing the work of the compiler developer through source-level extensibility; that is, to create an implementation of an extended compiler by touching as little as possible the code of the base compiler. To some extent, some of the existing extensible compilers also support the combination of implementations of language extensions such that multiple, independent, extensions can be used in the same source program (a form of independent extensibility). Binary Extensibility. However, each extension (or combination of extensions) results in a different compiler. If the user of the compiler needs a new combination of extensions, then he needs to build a new compiler. In these tools, syntactic extensibility is mostly monolithic, i.e. the syntax extensions are compiled together with the syntax of the base language into a single parse table. Not only does this complicate the independent evolution of the extensions and the base language, but it also make it difficult to let the user of the compiler select a number of (third party) extensions that he wants to use in a program. To support scenarios which require more dynamic configurations of language combinations, it is desirable to support binary extensibility. That is, extensibility that does not require rebuilding the compiler. This would make it possible to deploy a single version of the compiler, which users can then extend by plugging in separately deployed language components, where potentially each compilation unit uses a different combination of extensions. Parse Table Composition. o solve the syntactic aspect of this goal, we developed parse table composition, a mechanism for combining parse tables, rather than grammars. At generation-time, grammars are compiled separately into parse table components. At run-time of a compiler, the parse table for the base language is combined with a series of parse tables based on a user-selection of the desired extensions. Online parse table composition results in a single parse table that is used by the parser to parse a source program Composing a series of parse table components can be performed very efficiently, making the user of the compiler unaware of the parse table composition. Soon, the user will be familiar with the idea of a parser that parses a source file according to a series of parse table components, rather than a single one. After the parser generator has been applied to the individual components, linking the components typically just requires a minimal reconstruction of the parse table. This is a classical partial evaluation argument: as opposed to applying the full parser generation to all the involved grammars, the parser generation has already been partially applied. The parse table composition algorithm is based on partial reapplication of subset construction, which converts an NFA to a DFA. Subset construction is the essence of the LR parse table generation algorithm, hence the method is easy to understand and relate to basic, monolithic, parse table generation algorithm. Prototype. The prototype you can download from this page targets a scannerless, generalized-LR parser (SGLR) and takes (possibly incomplete) SDF grammars as input. The source code is available under the MIT license.Documentation
A paper on the parse table composition algorithm has been submitted for publication. An updated and extended version of the paper is available:- Martin Bravenboer and Eelco Visser. Parse Table Composition: Separate Compilation and Binary Extensibility of Grammars (pdf).
Unfortunately, this extended version also fixes several typos that slipped into the algorithms of the original submission.
Download
Releases
Distributions of the head revision are created continuously:Subversion
The distributions contain the latest of the latest developments, but if you really want to, the latest sources can be checked out using:$ svn checkout https://svn.cs.uu.nl:12443/repos/StrategoXT/parse-table-composition/trunkBefore you can configure the package as described below you have to run the
./bootstrap script. Also, pass --enable-bootstrap to the configure script.
Installation
The parse-table-composition package is a prototype built on top of Stratego/XT. The release page of the parse-table-composition lists a number of source packages that you need to install first:- aterm
- sdf2-bundle
- strategoxt
- strategoxt-utils
$ ./configure --prefix=/where/you/want/to/install/the/packages $ make $ make installSee the Installation Chapter if you experience any problems with this. You might need to set your
PKG_CONFIG_PATH if you did not install the dependencies in a standard location. Configure will tell you to do this if it cannot find aterm, sdf, strategoxt or strategoxt-utils.