One obstacle to the implementation of modular extensions to programming languages lies in the problem of parsing extended languages. Specifically, the parse tables at the heart of traditional LALR(1) parsers are so monolithic and tightly constructed that, in the general case, it is impossible to extend them without regenerating them from the source grammar. Current extensible frameworks employ a variety of solutions, ranging from a full regeneration to using pluggable binary modules for each different extension.

There is an increasing interest in domain-specific and extensible languages, and frameworks for developing extensions to them. One challenge is to develop tools that allow non-expert programmers to add an eclectic set of language extensions to a host language. In this paper we describe mechanisms for composing and analyzing syntactic specifications of a host language and extensions. These specifications consist of context-free grammars with each terminal symbol mapped to a regular expression, from which a slightly-modified LR parser and context-aware scanner are generated.

This paper introduces new parsing and context-aware scanning algorithms in which the scanner uses contextual information to disambiguate lexical syntax. The parser utilizes a slightly modified LR-style algorithm that passes to the scanner the set of valid symbols which the scanner may return at that point in parsing. This set is the terminal symbols that are valid for the current state, i.e., those whose entry in the parse table are shift, reduce, or accept, but not error. The scanner then only returns tokens in this set.