WG211/M7VanWyk
Verifiable Composition of Grammars
August Schwerdfeger and Eric Van Wyk
Abstract:
One challenge in extensible languages arises in the composition of the concrete syntax specifications for a host language and a collection of (domain-specific) language extensions. For this talk, these specifications consist, as is to be expected, of context-free grammars with each terminal symbol mapped to a regular expression, from which a slightly-modified LALR(1) parser and context-aware scanner are generated. Traditionally, conflicts are detected in the parse-table of the composed grammar when it is constructed, but this comes too late as it may be a non-expert programmer that directs the language tools to compose an eclectic set of language extensions chosen by the programmer for a particular task.
In this talk we discuss a modular analysis that is performed independently by each extension designer on her extension (composed alone with the host language). If each extension passes this modular analysis, then the language composed later by the non-expert programmer will compile with no conflicts or lexical ambiguities. Thus, extension writers can verify that their extension will safely compose with others and, if not, fix the specification so that it will. This is possible due to the context-aware scanner's lexical disambiguation and a set of reasonable restrictions limiting the sort of constructs that can be introduced by a language extension. The restrictions ensure that the states in the parse table can be partitioned so that each state can be attributed to the host language or a single language extension.
- vanwyk-wg09.pdf : Slides
