Dynamic \(\text{LL} (k)\) parsing (Q1920233)

A new class of context-free grammars, called dynamic context-free grammars, is introduced. These grammars have the ability to change the set of production rules dynamically during the derivation of some terminal string. The notion of \(\text{LL} (k)\) parsing is adapted to this grammar model. We show that dynamic \(\text{LL} (k)\) parsers are as powerful as \(\text{LR} (k)\) parsers, i.e. that they are capable to analyze every deterministic context-free language while using only one symbol of lookahead.