Skip to content

An SDF3 Bibliography

SDF31 is the third generation in the SDF family of syntax definition formalisms, which were developed in the context of the ASF+SDF2, Stratego/XT3, and Spoofax4 language workbenches.

Kats et al. decribe the motivation for declarative syntax definition5.

SDF

The first SDF6 supported modular composition of syntax definition, a direct correspondence between concrete and abstract syntax, and parsing with the full class of context-free grammars enabled by the Generalized-LR (GLR) parsing algorithm7 8. Its programming environment, as part of the ASF+SDF MetaEnvironment9, focused on live development of syntax definitions through incremental and modular scanner and parser generation10 11 12 in order to provide fast turnaround times during language development.

SDF2

The second generation, SDF2 encompassed a redesign of the internals of SDF without changing the surface syntax. The front-end of the implementation consisted of a transformation pipeline from the rich surface syntax to a minimal core (kernel) language13 that served as input for parser generation. The key change of SDF2 was its integration of lexical and context-free syntax, supported by Scannerless GLR (SGLR) parsing14 15, enabling composition of languages with different lexical syntax16 17.

SDF3

SDF3 is the latest member of the family and inherits many features of its predecessors. The most recognizable change is to the syntax of productions that should make it more familiar to users of other grammar formalisms. Further, it introduces new features in order to support multi-purpose interpretations of syntax definitions. The goals of the design of SDF3 are (1) to support the definition of the concrete and abstract syntax of formal languages (with an emphasis on programming languages), (2) to support declarative syntax definition so that there is no need to understand parsing algorithms in order to understand definitions 5, (3) to make syntax definitions readable and understandable so that they can be used as reference documentation, and (4) to support execution of syntax definitions as parsers, but also for other syntactic operations, i.e to support multi-purpose interpretation based on a single source. The focus on multipurpose interpretation is driven by the role of SDF3 in the Spoofax language workbench 4.

Key features of SDF3 include

  • Template productions18
  • Error recovery19
  • Layout constraints for layout-sensitive syntax20 21
  • Safe and complete disambiguation of expression grammars22
  • Placeholders and syntactic code completion23

Future Work

Parse table composition24, while implemented in a prototype, hasn't made into the production implementation yet.

References

  1. Luis Eduardo de Souza Amorim and Eelco Visser. Multi-purpose syntax definition with SDF3. In Frank S. de Boer and Antonio Cerone, editors, Software Engineering and Formal Methods - 18th International Conference, SEFM 2020, Amsterdam, The Netherlands, September 14-18, 2020, Proceedings, volume 12310 of Lecture Notes in Computer Science, 1–23. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-58768-0_1, doi:10.1007/978-3-030-58768-0_1. ↩

  2. Mark G. J. van den Brand, Arie van Deursen, Jan Heering, H. A. de Jong, Merijn de Jonge, Tobias Kuipers, Paul Klint, Leon Moonen, Pieter A. Olivier, Jeroen Scheerder, Jurgen J. Vinju, Eelco Visser, and Joost Visser. The ASF+SDF meta-environment: a component-based language development environment. In Reinhard Wilhelm, editor, Compiler Construction, 10th International Conference, CC 2001 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2001 Genova, Italy, April 2-6, 2001, Proceedings, volume 2027 of Lecture Notes in Computer Science, 365–370. Springer, 2001. URL: https://doi.org/10.1016/S1571-0661(04)80917-4, doi:10.1016/S1571-0661(04)80917-4. ↩

  3. Martin Bravenboer, Karl Trygve Kalleberg, Rob Vermaas, and Eelco Visser. Stratego/XT 0.17. A language and toolset for program transformation. Science of Computer Programming, 72(1-2):52–70, 2008. URL: http://dx.doi.org/10.1016/j.scico.2007.11.003, doi:10.1016/j.scico.2007.11.003. ↩

  4. Lennart C. L. Kats and Eelco Visser. The Spoofax language workbench: rules for declarative specification of languages and IDEs. In William R. Cook, Siobhán Clarke, and Martin C. Rinard, editors, Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2010, 444–463. Reno/Tahoe, Nevada, 2010. ACM. URL: https://doi.org/10.1145/1869459.1869497, doi:10.1145/1869459.1869497. ↩↩

  5. Lennart C. L. Kats, Eelco Visser, and Guido Wachsmuth. Pure and declarative syntax definition: paradise lost and regained. In William R. Cook, Siobhán Clarke, and Martin C. Rinard, editors, Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2010, 918–932. Reno/Tahoe, Nevada, 2010. ACM. URL: http://doi.acm.org/10.1145/1869459.1869535, doi:10.1145/1869459.1869535. ↩↩

  6. Jan Heering, P. R. H. Hendriks, Paul Klint, and Jan Rekers. The syntax definition formalism SDF - reference manual. SIGPLAN Notices, 24(11):43–75, 1989. doi:10.1145/71605.71607. ↩

  7. Masaru Tomita. An efficient context-free parsing algorithm for natural languages. In IJCAI, 756–764. 1985. ↩

  8. Jan Rekers. Parser Generation for Interactive Environments. PhD thesis, University of Amsterdam, Amsterdam, The Netherlands, January 1992. ↩

  9. Paul Klint. A meta-environment for generating programming environments. ACM Transactions on Software Engineering Methodology, 2(2):176–201, 1993. doi:10.1145/151257.151260. ↩

  10. Jan Heering, Paul Klint, and Jan Rekers. Incremental generation of lexical scanners. ACM Transactions on Programming Languages and Systems, 14(4):490–520, 1992. doi:10.1145/133233.133240. ↩

  11. Jan Heering, Paul Klint, and Jan Rekers. Incremental generation of parsers. IEEE Trans. Software Eng., 16(12):1344–1351, 1990. ↩

  12. Jan Heering, Paul Klint, and Jan Rekers. Lazy and incremental program generation. ACM Transactions on Programming Languages and Systems, 16(3):1010–1023, 1994. doi:10.1145/177492.177750. ↩

  13. Eelco Visser. A family of syntax definition formalisms. In Mark G. J. van den Brand and Vania Vieira Estrela, editors, ASF+SDF 1995. A Workshop on Generating Tools from Algebraic Specifications. Technical Report P9504, Programming Research Group, University of Amsterdam, May 1995. ↩

  14. Eelco Visser. Syntax Definition for Language Prototyping. PhD thesis, University of Amsterdam, September 1997. ↩

  15. Eelco Visser. Scannerless generalized-LR parsing. Technical Report P9707, Programming Research Group, University of Amsterdam, July 1997. ↩

  16. Eelco Visser. Meta-programming with concrete object syntax. In Don S. Batory, Charles Consel, and Walid Taha, editors, Generative Programming and Component Engineering, ACM SIGPLAN/SIGSOFT Conference, GPCE 2002, Pittsburgh, PA, USA, October 6-8, 2002, Proceedings, volume 2487 of Lecture Notes in Computer Science, 299–315. Springer, 2002. URL: https://doi.org/10.1007/3-540-45821-2_19, doi:10.1007/3-540-45821-2_19. ↩

  17. Martin Bravenboer and Eelco Visser. Concrete syntax for objects: domain-specific language embedding and assimilation without restrictions. In John M. Vlissides and Douglas C. Schmidt, editors, Proceedings of the 19th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2004, 365–383. Vancouver, BC, Canada, 2004. ACM. URL: http://doi.acm.org/10.1145/1028976.1029007, doi:10.1145/1028976.1029007. ↩

  18. Tobi Vollebregt, Lennart C. L. Kats, and Eelco Visser. Declarative specification of template-based textual editors. In Anthony Sloane and Suzana Andova, editors, International Workshop on Language Descriptions, Tools, and Applications, LDTA '12, Tallinn, Estonia, March 31 - April 1, 2012, 1–7. ACM, 2012. URL: http://doi.acm.org/10.1145/2427048.2427056, doi:10.1145/2427048.2427056. ↩

  19. Maartje de Jonge, Lennart C. L. Kats, Eelco Visser, and Emma Söderberg. Natural and flexible error recovery for generated modular language environments. ACM Transactions on Programming Languages and Systems, 34(4):15, 2012. URL: http://doi.acm.org/10.1145/2400676.2400678, doi:10.1145/2400676.2400678. ↩

  20. Sebastian Erdweg, Tillmann Rendel, Christian Kästner, and Klaus Ostermann. Layout-sensitive generalized parsing. In Krzysztof Czarnecki and Görel Hedin, editors, Software Language Engineering, 5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers, volume 7745 of Lecture Notes in Computer Science, 244–263. Springer, 2012. doi:10.1007/978-3-642-36089-3\_14. ↩

  21. Luis Eduardo de Souza Amorim, Michael J. Steindorfer, Sebastian Erdweg, and Eelco Visser. Declarative specification of indentation rules: a tooling perspective on parsing and pretty-printing layout-sensitive languages. In David Pearce 0005, Tanja Mayerhofer, and Friedrich Steimann, editors, Proceedings of the 11th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2018, Boston, MA, USA, November 05-06, 2018, 3–15. ACM, 2018. URL: https://doi.org/10.1145/3276604.3276607, doi:10.1145/3276604.3276607. ↩

  22. Luis Eduardo de Souza Amorim. Declarative Syntax Definition for Modern Language Workbenches. PhD thesis, Delft University of Technology, Netherlands, 2019. base-search.net (fttudelft:oai:tudelft.nl:uuid:43d7992a-7077-47ba-b38f-113f5011d07f). URL: https://www.base-search.net/Record/261b6c9463c1d4fe309e3c6104cd4d80fbc9d3cc8fbc66006f34130f481b506f. ↩

  23. Luis Eduardo de Souza Amorim, Sebastian Erdweg, Guido Wachsmuth, and Eelco Visser. Principled syntactic code completion using placeholders. In Tijs van der Storm, Emilie Balland, and Dániel Varró, editors, Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering, Amsterdam, The Netherlands, October 31 - November 1, 2016, 163–175. ACM, 2016. URL: http://dx.doi.org/10.1145/2997364.2997374, doi:10.1145/2997364.2997374. ↩

  24. Martin Bravenboer and Eelco Visser. Parse table composition. In Dragan Gasevic, Ralf Lämmel, and Eric Van Wyk, editors, Software Language Engineering, First International Conference, SLE 2008, Toulouse, France, September 29-30, 2008. Revised Selected Papers, volume 5452 of Lecture Notes in Computer Science, 74–94. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-00434-6_6, doi:10.1007/978-3-642-00434-6_6. ↩

Last update: April 12, 2024
Created: April 12, 2024