Generation and recognition of formal languages by modifiable grammars
Boris Burshteyn · ACM SIGPLAN Notices · 1990
In this article the formal definitions of modifiable grammars are presented, and the equivalence between classes of modifiable grammars and Turing machines is proved. Some criteria for reducing modifiable grammars to context-free grammars are provided. A lazy LR(1) algorithm for context-free grammars and an algorithm for constructing a LR(1) parser for modifiable grammars are discussed.