Parsing Transformative LR(1) Languages

The authors consider, as a means of making programming languages more flexible and powerful, a parsing algorithm in which the parser may freely modify the grammar while parsing. They are particularly interested in a modification of the canonical LR(1) parsing algorithm in which, after the reduction of certain productions, they examine the source sentence seen so far to determine the grammar to use to continue parsing. A naive modification of the canonical LR(1) parsing algorithm along these lines cannot be guaranteed to halt; as a result, they develop a test which examines the grammar as it changes, stopping the parse if the grammar changes in a way that would invalidate earlier assumptions made by the parser.