Regular right part grammars and their parsers

ABSTRACT

This paper introduces 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 expression, 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 introduced 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.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: DeRemer, F.L., and LaLonde, W.R. A proposal to develop and implement an advanced translator writing system. U. of California, Santa Cruz, Calif., 1971-75.
• 3: DeRemer, F.L. Extended LR(k) grammars and their parsers, U. of California, Santa Cruz, Calif., 1970.
• 4: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 5: Floyd, R. A grammatical description of AlgolW. In Sites, R.L., Tech. Rept. STAN-CS-71-230, Comptr. Sci. Dept., Stanford U., Stanford, Calif., 1972, pp. 128-139.
• 6: David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
• 7: Kathleen Jensen , Niklaus Wirth, Pascal-User Manual and Report, Springer-Verlag New York, Inc., Secaucus, NJ, 1975
• 8: Knuth, D.E. On the translation of languages from left to right. Inform. Contr. 8 (Oct. 1965), 607-639.
• 9: Wilf Roger Lalonde, Practical lr analysis of regular right part grammars., 1975
• 10: W. A. Woods, Transition network grammars for natural language analysis, Communications of the ACM, v.13 n.10, p.591-606, Oct. 1970 [doi>10.1145/355598.362773]

INDEX TERMS

Keywords:
LR(k) grammars, compilers, finite state machines (automata), formal definition, language generation, parser construction, parsing, programming languages, regular expressions, scanners, syntax diagrams, translators