The Construction of Stack-Controlling LR Parsers for Regular Right Part Grammars

Abstract

Although determinisitic pushdown automata and LR(k) parsers are formally equivalent, the latter (unlike the former) stack one symbol for each input symbol read.By relaxing this requirement, we obtain a class of LR parsers that can perform finite state recognition locally without associated stack manipulations.The definition and construction of such stack-controlling LR parsers is examined in detail along with some potential application areas.