Macros for context-free grammars

ABSTRACT

Current parser generators are based on context-free grammars. Because such grammars lack abstraction facilities, the resulting specifications are often not easy to read. Fischer's macro grammars extend context-free grammars with macro-like productions thus providing the equivalent of procedural abstraction. However, their use is hampered by the lack of an efficient, off-the-shelf parsing technology for macro grammars.

We define specialization for macro grammars to enable reuse of parsing technology for context-free grammars while facilitating the specification of a language with a macro grammar. This specialization yields context-free rules, but it does not always terminate.

We present a sound and complete static analysis that applies to any macro grammar and decides whether specialization terminates for it and thus yields a (finite) context-free grammar. The analysis is based on an intuitive notion of self-embedding nonterminals, which is easy to check by hand.

We have implemented the analysis as part of a preprocessing tool that transforms a Yacc grammar extended with macro productions to a standard Yacc grammar.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Arthur I. Baars , Andres Löh , S. Doaitse Swierstra, Parsing permutation phrases, Journal of Functional Programming, v.14 n.6, p.635-646, November 2004 [doi>10.1017/S0956796804005143]
• 3: Robert D. Cameron, Extending context-free grammars with permutation phrases, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.85-94, March–Dec. 1993 [doi>10.1145/176454.176490]
• 4: N P. Chapman, LALR(1, 1) parser generation for regular right part grammars, Acta Informatica, v.21 n.1, p.29-45, May 1984 [doi>10.1007/BF00289138]
• 5: Nigel P. Chapman, LR parsing: theory and practice, Cambridge University Press, New York, NY, 1988
• 6: Compiler Resources, Inc. Yacc++ and the language objects library. http://world.std.com/~compres/, July 2004.
• 7: K. Culik and R. Cohen. LR-regular grammars¿an extension of LR(k) grammars. J. Comput. Syst. Sci., 7:66--96, 1973.
• 8: W. Damm. The IO- and OI-hierarchies. Theoretical Computer Science, 20(2):95--207, May 1982.
• 9: C. Donnelly and R. Stallman. Bison¿The YACC-compatible Parser Generator. Free Software Foundation, Boston, MA, Nov. 1995. Part of the Bison distribution.
• 10: ECMAScript Language Specification. http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-262.pdf, Dec. 1999. ECMA International, ECMA-262, 3rd edition.
• 11: M. J. Fischer. Grammars with macro-like productions. In IEEE Conference Record of 9th Annual Symposium on Switching and Automata Theory, pages 131--142, 1968.
• 12: A. Gill and S. Marlow. Happy Manual. University of Glasgow, Department of Computing Science, 1995. Available via http://www.dcs.gla.ac.uk/fp/software/happy.html.
• 13: Arne John Glenstrup , Neil D. Jones, Termination analysis and specialization-point insertion in offline partial evaluation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1147-1215, November 2005 [doi>10.1145/1108970.1108973]
• 14: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 15: The GrammarForge. build parsing applications with confidence. http://www.thothic.com/downloads/MetaSFactSheet.pdf, 2005.
• 16: Robert W. Gray , Steven P. Levi , Vincent P. Heuring , Anthony M. Sloane , William M. Waite, Eli: a complete, flexible compiler construction system, Communications of the ACM, v.35 n.2, p.121-130, Feb. 1992 [doi>10.1145/129630.129637]
• 17: John Hatcliff, An Introduction to Online and Offline Partial Evaluation using a Simple Flowchart Language, Partial Evaluation - Practice and Theory, DIKU 1998 International Summer School, p.20-82, June 29-July 10, 1998
• 18: S. Heilbrunner. On the definition of ELR(k) and ELL(k) grammars. Acta Informatica, 11:169--176, 1979.
• 19: Graham Hutton , Erik Meijer, Monadic parsing in Haskell, Journal of Functional Programming, v.8 n.4, p.437-444, July 1998 [doi>10.1017/S0956796898003050]
• 20: JavaCC the java parser generator. https://javacc.dev.java.net/.
• 21: S. C. Johnson. Yacc¿yet another compiler compiler. Technical Report 32, AT&T Bell Laboratories, Murray Hill, NJ, 1975.
• 22: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 23: Wilf R. LaLonde, Regular right part grammars and their parsers, Communications of the ACM, v.20 n.10, p.731-741, Oct. 1977 [doi>10.1145/359842.359853]
• 24: Bernard Lang, Deterministic Techniques for Efficient Non-Deterministic Parsers, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.255-269, July 29-August 02, 1974
• 25: Chin Soon Lee , Neil D. Jones , Amir M. Ben-Amram, The size-change principle for program termination, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.81-92, January 2001, London, United Kingdom
• 26: Gyung-Ok Lee , Do-Hyung Kim, Characterization of extended LR (K) grammars, Information Processing Letters, v.64 n.2, p.75-82, Oct. 28, 1997 [doi>10.1016/S0020-0190(97)00152-X]
• 27: T. J. Parr , R. W. Quong, ANTLR: a predicated-LL(k) parser generator, Software—Practice & Experience, v.25 n.7, p.789-810, July 1995 [doi>10.1002/spe.4380250705]
• 28: S. Peyton Jones, editor. Haskell 98 Language and Libraries, The Revised Report. Cambridge University Press, 2003.
• 29: F. Pottier and Y. Régis-Gianas. Menhir reference manual. http://pauillac.inria.fr/~fpottier/menhir/manual.pdf, July 2007.
• 30: J. Rekers. Parser Generation for Interactive Environments. PhD thesis, University of Amsterdam, 1992.
• 31: S. D. Swierstra. Fast, error repairing parsing combinators. http://www.cs.uu.nl/groups/ST/Software/UU Parsing/, Aug. 2003.
• 32: S. Doaitse Swierstra , Luc Duponcheel, Deterministic, Error-Correcting Combinator Parsers, Advanced Functional Programming, Second International School-Tutorial Text, p.184-207, August 26-30, 1996
• 33: P. Thiemann and M. Neubauer. Parameterized LR parsing. In G. Hedin and E. van Wyk, editors, Fourth Workshop on Language Descriptions, Tools and Applications, LDTA 2004, volume 110 of ENTCS, pages 115--132, Barcelona, Spain, Apr. 2004. Elsevier Science.
• 34: Masaru Tomita, Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, Kluwer Academic Publishers, Norwell, MA, 1985
• 35: M. van den Brand and P. Klint. ASF+SDF meta-environment user manual. http://www.cwi.nl/projects/MetaEnv/meta/doc/manual/user-manual.html, July 2002.
• 36: A. van Wijngaarden, Report on the algorithmic language ALGOL 68, Printing by the Mathematisch Centrum, 1969
• 37: Eelco Visser, Polymorphic syntax definition, Theoretical Computer Science, v.199 n.1-2, p.57-86, June 15, 1998
• 38: Parsing with Sandstone's Visual Parse++. http://www.sand-stone.com/pwvp.ZIP, 2001.
• 39: Renhard Wilhelm , Dieter Maurer, Compiler Design, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

General Terms:
Languages, Theory