Constructing LR parsers for regular right part grammars

Summary Regular right part (RRP) grammars differ from context free (CF) grammars by virtue of the fact that the production right parts are nondeterministic finite automatons (FAs). LR(k) parsers for RRP grammars are linear time parsers which can determine the right end of each handle by considering at most k terminal symbols to its right and the left end (after the right end has been found) by considering at most one parse stack state to its left. This paper is concerned with the construction of a class of LR(k) parsers for RRP grammars which makes use of FAs for determining both the right and left ends of the handle.This work has been supported by a Carleton University grant and National Research Council of Canada grant no. A3585