Generating LR(1) parsers of small size

Abstract

Classic LR(1) parsing methods have the problem of producing too large parsing tables for programming language grammars. An alternative is to build an automaton that combines the lookahead symbol with reading the parsing stack from its top, to determine the next parsing action. The building procedure for such a parser and its use for parsing are presented through an example grammar. Results from an experimental implementation of the parser generator show important reductions in automaton size in comparison with standard LR methods. Some discussion is presented, suggesting that the theoretical drawbacks of the method are of relatively little practical importance.