Generalized Type-Based Disambiguation of Meta Programs with Concrete Object Syntax

  • Martin Bravenboer
  • Rob Vermaas
  • Jurgen Vinju
  • Eelco Visser
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3676)


In meta programming with concrete object syntax, object-level programs are composed from fragments written in concrete syntax. The use of small program fragments in such quotations and the use of meta-level expressions within these fragments (anti-quotation) often leads to ambiguities. This problem is usually solved through explicit disambiguation, resulting in considerable syntactic overhead. A few systems manage to reduce this overhead by using type information during parsing. Since this is hard to achieve with traditional parsing technology, these systems provide specific combinations of meta and object languages, and their implementations are difficult to reuse. In this paper, we generalize these approaches and present a language independent method for introducing concrete object syntax without explicit disambiguation. The method uses scannerless generalized-LR parsing to parse meta programs with embedded object-level fragments, which produces a forest of all possible parses. This forest is reduced to a tree by a disambiguating type checker for the meta language. To validate our method we have developed embeddings of several object languages in Java, including AspectJ and Java itself.


Object Language Abstract Syntax Concrete Syntax Type Checker Method Invocation 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Aasa, A., Petersson, K., Synek, D.: Concrete syntax for data objects in functional languages. In: Proceedings of the 1988 ACM conference on LISP and functional programming, pp. 96–105. ACM Press, New York (1988)CrossRefGoogle Scholar
  2. 2.
    Bachrach, J., Playford, K.: The Java syntactic extender (JSE). In: Proceedings of the 16th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2001), pp. 31–42. ACM Press, New York (2001)CrossRefGoogle Scholar
  3. 3.
    Baker, J., Hsieh, W.C.: Maya: multiple-dispatch syntax extension in java. In: PLDI 2002: Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, pp. 270–281. ACM Press, New York (2002)CrossRefGoogle Scholar
  4. 4.
    Batory, D., Lofaso, B., Smaragdakis, Y.: JTS: tools for implementing domain-specific languages. In: Proceedings Fifth International Conference on Software Reuse (ICSR 1998), pp. 143–153. IEEE Computer Society Press, Los Alamitos (1998)CrossRefGoogle Scholar
  5. 5.
    Baxter, I.D., Pidgeon, C., Mehlich, M.: DMS®: Program transformations for practical scalable software evolution. In: ICSE 2004: Proceedings of the 26th International Conference on Software Engineering, pp. 625–634. IEEE Computer Society, Los Alamitos (2004)CrossRefGoogle Scholar
  6. 6.
    Brabrand, C., Schwartzbach, M.I.: Growing languages with metamorphic syntax macros. In: Proceedings of the 2002 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation (PEPM 2002), pp. 31–40. ACM Press, New York (2002)CrossRefGoogle Scholar
  7. 7.
    van den Brand, M.G.J., Klusener, S., Moonen, L., Vinju, J.J.: Generalized Parsing and Term Rewriting - Semantics Directed Disambiguation. In: Bryant, B., Saraiva, J. (eds.) LDTA 2003. ENTCS, vol. 82. Elsevier, Amsterdam (2003)Google Scholar
  8. 8.
    van den Brand, M.G.J., Moreau, P.E., Vinju, J.J.: A generator of efficient strongly typed abstract syntax trees in Java. IEE Proceedings - Software (May 2005)Google Scholar
  9. 9.
    van den Brand, M.G.J., Ringeissen, C.: ASF+SDF parsing tools applied to ELAN. In: Third International Workshop on Rewriting Logic and Applications. ENTCS (2000)Google Scholar
  10. 10.
    van den Brand, M.G.J., Scheerder, J., Vinju, J.J., Visser, E.: Disambiguation filters for scannerless generalized LR parsers. In: Horspool, R.N. (ed.) CC 2002. LNCS, vol. 2304, pp. 143–158. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  11. 11.
    Bravenboer, M., Visser, E.: Concrete syntax for objects. Domain-specific language embedding and assimilation without restrictions. In: Schmidt, D.C. (ed.) Proceedings of the 19th ACM SIGPLAN Conference on Object-Oriented Programing, Systems, Languages, and Applications (OOPSLA 2004), pp. 365–383. ACM Press, New York (2004)CrossRefGoogle Scholar
  12. 12.
    Cordy, J.R., Halpern-Hamu, C.D., Promislow, E.: TXL: A rapid prototyping system for programming language dialects. Computer Languages 16(1), 97–107 (1991)CrossRefGoogle Scholar
  13. 13.
    de Rauglaudre, D.: Camlp4 reference manual, INRIA (September 2003)Google Scholar
  14. 14.
    van Deursen, A., Heering, J., Klint, P. (eds.): Language Prototyping. AMAST Series in Computing, vol. 5. World Scientific, Singapore (1996)zbMATHGoogle Scholar
  15. 15.
    Eclipse Java Development Tools (JDT), website:
  16. 16.
    Klint, P., Visser, E.: Using filters for the disambiguation of context-free grammars. In: Pighizzini, G., San Pietro, P. eds, Proc. ASMICS Workshop on Parsing Theory, Tech. Rep. 126, Università di Milano, pp. 1–20 (1994)Google Scholar
  17. 17.
    Leavenworth, B.M.: Syntax macros and extended translation. Commun. ACM 9(11), 790–793 (1966)zbMATHCrossRefGoogle Scholar
  18. 18.
    Vinju, J.J.: A type driven approach to concrete meta programming. Technical Report SEN-E0507, Centrum voor Wiskunde en Informatica (2005)Google Scholar
  19. 19.
    Visser, E.: Syntax Definition for Language Prototyping. PhD thesis, University of Amsterdam (September 1997)Google Scholar
  20. 20.
    Visser, E.: Meta-programming with concrete object syntax. In: Batory, D., Consel, C., Taha, W. (eds.) GPCE 2002. LNCS, vol. 2487, pp. 299–315. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  21. 21.
    Visser, E.: Program transformation with Stratego/XT: Rules, strategies, tools, and systems in StrategoXT-0.9. In: Lengauer, C., Batory, D., Consel, C., Odersky, M. (eds.) Domain-Specific Program Generation. LNCS, vol. 3016, pp. 216–238. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  22. 22.
    Zook, D., Huang, S.S., Smaragdakis, Y.: Generating AspectJ programs with Meta-AspectJ. In: Karsai, G., Visser, E. (eds.) GPCE 2004. LNCS, vol. 3286, pp. 1–19. Springer, Heidelberg (2004)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Martin Bravenboer
    • 1
  • Rob Vermaas
    • 1
  • Jurgen Vinju
    • 2
  • Eelco Visser
    • 1
  1. 1.Department of Information and Computing SciencesUniversiteit UtrechtUtrechtThe Netherlands
  2. 2.Centrum voor Wiskunde en Informatica (CWI)AmsterdamThe Netherlands

Personalised recommendations