LALR(1, 1) parser generation for regular right part grammars

Summary Commonly used extensions to BNF can be modelled by the formalism of regular right part grammars. A method for building LR parsers for such grammars is given, which works by first constructing an LR(0) automaton and then augmenting it with readback machines constructed to recognize the reverse of the state sequences leading to a reduction. The state sequences which will be accepted by such readback machines are also the sequences which link reductions to their lookback states (states in which the parser may be re-started after the reduction), which are needed in order to compute LALR(1) lookahead sets using the algorithm devised recently by DeRemer and Pennello.An algorithm is presented which computes these lookback states using the structure of the LR(0) automaton, and it is shown how this can easily be extended to build readback machines at the same time.