Parse Table Composition: Separate Compilation and Binary Extensibility of Grammars

Parse Table Composition: Separate Compilation and Binary Extensibility of Grammars

Bravenboer, M.
Visser, E.

Electrical Engineering, Mathematics and Computer Science

Software Computer Technology

2008-12-31

Preprint of paper published in: Software Language Engineering, Lecture Notes in Computer Science 5452, 2009; doi:10.1007/978-3-642-00434-6_6 Module systems, separate compilation, deployment of binary components, and dynamic linking have enjoyed wide acceptance in programming languages and systems. In contrast, the syntax of languages is usually defined in a non-modular way, cannot be compiled separately, cannot easily be combined with the syntax of other languages, and cannot be deployed as a component for later composition. Grammar formalisms that do support modules use whole program compilation. Current extensible compilers focus on source-level extensibility, which requires users to compile the compiler with a specific configuration of extensions. A compound parser needs to be generated for every combination of extensions. The generation of parse tables is expensive, which is a particular problem when the composition configuration is not fixed to enable users to choose language extensions. In this paper we introduce an algorithm for parse table composition to support separate compilation of grammars to parse table components. Parse table components can be composed (linked) efficiently at runtime, i.e. just before parsing. While the worst-case time complexity of parse table composition is exponential (like the complexity of parse table generation itself), for realistic language combination scenarios involving grammars for real languages, our parse table composition algorithm is an order of magnitude faster than computation of the parse table for the combined grammars.

http://resolver.tudelft.nl/uuid:0701814b-a0f1-4b47-9336-559b4a042971

Delft University of Technology, Software Engineering Research Group

1872-5392

Technical Report Series TUD-SERG-2008-043

Institutional Repository

lecture notes

(c) 2008 The Author(s)
Springer