TWEAST: a simple and effective technique to implement concrete-syntax AST rewriting using partial parsing

ABSTRACT

Abstract Syntax Trees (ASTs) are commonly used to represent an input/output program in compilers and language processing tools. Many of the tasks of these tools consist in generating and rewriting ASTs. Such an approach can become tedious and hard to maintain for complex operations, namely program transformation, optimization, instrumentation, etc. On the other hand, concrete syntax provides a natural and simpler representation of programs, but it is not usually available as a direct feature of the aforementioned tools. We propose a simple technique to implement AST generation and rewriting in general purpose languages using concrete syntax. Our approach relies on extensions made in the scanner and the parser and the use of objects supporting partial parsing called Texts With Embedded Abstract Syntax Trees (TWEASTs). A compiler for a simple language (Tiger) written in C++ serves as an example, featuring transformations in concrete syntax: syntactic desugaring, optimization, code instrumentation such as bounds-checking, etc. Extensions of this technique to provide a full-fledged concrete-syntax rewriting framework are presented as well.

REFERENCES

• 1: Andrew W. Appel, Modern Compiler Implementation: In ML, Cambridge University Press, New York, NY, 1998
• 2: E. Balland, P. Brauner, R. Kopetz, P.-E. Moreau, and A. Reilles. Tom: Piggybacking rewriting on Java. In Proceedings of the 18th Conference on Rewriting Techniques and Applications, Lecture Notes in Computer Science. Springer-Verlag, 2007.
• 3: Martin Bravenboer , Karl Trygve Kalleberg , Rob Vermaas , Eelco Visser, Stratego/XT 0.16: components for transformation systems, Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 09-10, 2006, Charleston, South Carolina [doi>10.1145/1111542.1111558]
• 4: R. Corbett, R. Stallman, and P. Hilfinger. Bison: GNU LALR(1) and GLR parser generator, 2003. http://www.gnu.org/software/bison/bison.html.
• 5: Akim Demaille, Making compiler construction projects relevant to core curriculums, Proceedings of the 10th annual SIGCSE conference on Innovation and technology in computer science education, June 27-29, 2005, Caparica, Portugal
• 6: A. Demaille. The Tiger Compiler Reference Manual. EPITA Research and Development Laboratory (LRDE), 14--16 rue Voltaire, FR-94270 Le Kremlin-Bicêtre, France, 2007. http://www.lrde.epita.fr/~akim/ccmp/tiger.pdf.
• 7: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 8: Tobias Kuipers , Joost Visser, Object-oriented tree traversal with J. J. Forester, Science of Computer Programming, v.47 n.1, p.59-87, April 2003 [doi>10.1016/S0167-6423(02)00108-9]
• 9: A. Leung. Prop: A C++-based pattern matching language. Technical report, Courant Institute of Mathematical Sciences, 1996.
• 10: 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]
• 11: V. Paxson, W. Estes, and J. Millaway. The Flex Manual. The Flex Project, September 2007. http://flex.sourceforge.net/manual/index.html.
• 12: E. Visser. A family of syntax definition formalisms. In M. G. J. van den Brand et al., editors, ASF+SDF'95. A Workshop on Generating Tools from Algebraic Specifications, pages 89--126. Technical Report P9504, Programming Research Group, University of Amsterdam, May 1995.
• 13: E. Visser. Scannerless generalized-LR parsing. Technical Report P9707, Programming Research Group, University of Amsterdam, July 1997.
• 14: Eelco Visser, Meta-programming with Concrete Object Syntax, Proceedings of the 1st ACM SIGPLAN/SIGSOFT conference on Generative Programming and Component Engineering, p.299-315, October 06-08, 2002
• 15: E. Visser. Program transformation with Stratego/XT: Rules, strategies, tools, and systems in StrategoXT-0.9. In C. Lengauer et al., editors, Domain-Specific Program Generation, volume 3016 of Lecture Notes in Computer Science, pages 216--238. Springer-Verlag, June 2004.
• 16: R. Weatherley. Treecc, the Tree Compiler-Compiler. http://www.southern-storm.com.au/treecc.html, 2002.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing; Translator writing systems and compiler generators

General Terms:
Design, Languages

Keywords:
C++, compiler design, concrete syntax, parsing, program transformation, rewrite rules