Regular Right Part Grammars and Their Parsers This paper in troduces an alternative to context-free grammars called regular right part (RRP) grammars, which resemble PASCAL syntax diagrams. Formally, RRP grammars have production right parts, which are nondeterministic finite state machines (FSMs), and, as a special case, regular expressions, since these can be converted to FSMs. RRP grammars describe the syntax of programming languages more concisely and more understandably than is possible with CF grammars. Also in troduced is a class of parsers, RRP LR(m, k) parsers, which includes the CF LR(k) parsers and provides the same advantages. Informally, an RRP LR(m, k) parser can determine the right end of each handle by considering at most k symbols to the right of the handle and the left end, after the right end has been found, by considering at most m symbols to the left of the handle. A mechanism for determining the left end is required because there is no bound on the length of the handle. CACM October, 1977 LaLonde, W. R. finite state machines (automata), regular expressions, syntax diagrams,LR(k) grammars, parser construction, parsing, programming languages, language generation, formal definition, compilers, translators, scanners 4.2 5.21 5.23 CA771005 JB December 27, 1977 11:01 AM 1989 4 2921 2060 4 2921 2179 4 2921 2581 4 2921 2698 4 2921 2739 4 2921 2795 4 2921 2921 4 2921 2921 4 2921 3087 4 2921 3154 4 2921 1989 5 2921 2110 5 2921 2921 5 2921 2921 5 2921 2921 5 2921