The syntax definition formalism SDF—reference manual—

ABSTRACT

SDF is a formalism for the definition of syntax which is comparable to BNF in some respects, but has a wider scope in that it also covers the definition of lexical and abstract syntax. Its design and implementation are tailored towards the language designer who wants to develop new languages as well as implement existing ones in a highly interactive manner. It emphasizes compactness of syntax definitions by offering (a) a standard interface between lexical and context-free syntax; (b) a standard correspondence between context-free and abstract syntax; (c) powerful disambiguation and list constructs; and (d) an efficient incremental implementation which accepts arbitrary context-free syntax definitions. SDF can be combined with a variety of programming and specification languages. In this way these obtain fully general user-definable syntax.

REFERENCES

• 1: A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Communications of the ACM, v.18 n.8, p.441-452, Aug. 1975 [doi>10.1145/360933.360969]
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: J. A. Bergstra , Jan Heering , Paul Klint, Algebraic specification, ACM, New York, NY, 1989
• 4: Rolf Bahlke , Gregor Snelting, The PSG system: from formal language definitions to interactive programming environments, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.547-576, Oct. 1986 [doi>10.1145/6465.20890]
• 5: [DK89a] M.H.H. van Dijk & J.W.C. Koorn, "Implementation of a generic syntax-directed editor", Fourth Annual Report ESPRIT Project GIPE, 1989.
• 6: [DK89b] M.H.H. van Dijk & J.W.C. Koorn, "GSE User's manual", User's Manual of the Centaur System, Version 0.9, 1989.
• 7: Nachum Dershowitz , Zohar Manna, Proving termination with multiset orderings, Communications of the ACM, v.22 n.8, p.465-476, Aug. 1979 [doi>10.1145/359138.359142]
• 8: [Des84] T. Despeyroux, "Executable specification of semantics", in Semantics of Data Types, G. Kahn, D.B. MacQueen & G. Plotkin (eds.), Lecture Notes in Computer Science, Vol. 173, Springer-Verlag, 1984, pp. 215-233.
• 9: Kokichi Futatsugi , Joseph A. Goguen , Jean-Pierre Jouannaud , José Meseguer, Principles of OBJ2, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.52-66, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318610]
• 10: [HK89a] J. Heering & P. Klint, "The syntax definition formalism SDF", in [BHK89, Chapter 6]. Also in ESPRIT "86: Results and Achievements, North-Holland, 1987, pp. 619-630.
• 11: Commission of the European Communitie, Esprit '88: Putting the Technology to Use, Elsevier Science Inc., New York, NY, 1988
• 12: [HKKL85] J. Heering, G. Kahn, P. Klint & B. Lang, "Generation of interactive programming environments", in ESPRIT '85: Status Report of Continuing Work, Part I, North-Holland, 1986, pp. 467-477.
• 13: [HKR87a] J. Heering, P. Klint & J. Rekers, "Principles of lazy and incremental program generation", Report CS-R8749, Centre for Mathematics and Computer Science, Amsterdam, 1987.
• 14: [HKR87b] J. Heering, P. Klint & J. Rekers, "Incremental generation of lexical scanners", Report CS-R8761, Centre for Mathematics and Computer Science, Amsterdam, 1987.
• 15: [HKR88] J. Heering, P. Klint & J. Rekers, "Incremental generation of parsers", CS-R8822, Centre for Mathematics and Computer Science, Amsterdam, 1988.
• 16: [Hen89] P.R.H. Hendriks, "Type-checking Mini-ML", in [BHK89, Chapter 7]. Abbreviated version in Proceedings of CSN87: Computing Science in the Netherlands, SION, 1987, pp. 21-38.
• 17: Edgar T. Irons, A syntax directed compiler for ALGOL 60, Communications of the ACM, v.4 n.1, p.51-55, Jan. 1961 [doi>10.1145/366062.366083]
• 18: Edgar T. Irons, Experience with an extensible language, Communications of the ACM, v.13 n.1, p.31-40, Jan. 1970 [doi>10.1145/361953.361966]
• 19: [JGHMK86] W. N. Joy, S. L. Graham, Ch. B. Haley, M. K. McKusick & P. B. Kessler, "Berkeley Pascal User's Manual-Version 3.1, April 1986", 4.3 Berkeley Software Distribution, Computer Systems Research Group, University of California, Berkeley, 1986.
• 20: [JL82] J.-P. Jouannaud & P. Lescanne, "On multiset orderings", Information Processing Letters, Vol. 15, No. 2, 1982, pp. 57-63.
• 21: [Joh79] S. C. Johnson, "YACC - yet another compiler-compiler", in UNIX Programmer's Manual, Vol, 2B, Bell Laboratories, 1979.
• 22: [KLMM83] G. Kahn, B. Lang, B. Mélèse & E. Morcos, "METAL: a formalism to specify formalisms", Science of Computer Programming, Vol. 3, 1983, pp. 151-188.
• 23: Gilles Kahn, Natural Semantics, Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, p.22-39, February 19-21, 1987
• 24: [Kli89] P. Klint, "Scanner generation for modular regular grammars", in Liber Amicorum, J. W. de Bakker, 25 jaar Semantiek, Centre for Mathematics and Computer Science, Amsterdam, 1989, pp. 291-305.
• 25: [LS79] M. E. Lesk & E. Schmidt, "LEX -- A lexical analyzer generator", in UNIX Programmer's Manual, Vol. 2B, Bell Laboratories, 1979.
• 26: [Log88] M. Logger, "An integrated text and syntax-directed editor", Report CS-R8820, Centre for Mathematics and Computer Science, Amsterdam, 1988.
• 27: [vdM88] E. A. van der Meulen, "Algebraic specification of a compiler for a language with pointers", Report CS-R8848, Centre for Mathematics and Computer Science, Amsterdam, 1988.
• 28: Michael J. O'Donnell, Equational logic as a programming language, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 29: Thomas W. Reps , Tim Teitelbaum, The synthesizer generator: a system for constructing language-based editors, Springer-Verlag New York, Inc., New York, NY, 1989
• 30: [Rek89] J. Rekers, "Modular parser generation", Report, Centre for Mathematics and Computer Science, Amsterdam, to appear, 1989.
• 31: Thomas W. Reps, Generating language-based environments, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 32: David Sandberg, Lithe: a language combining a flexible syntax and classes, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.142-145, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582169]
• 33: Thomas A. Standish, Extensibility in programming language design, ACM SIGPLAN Notices, v.10 n.7, July 1975 [doi>10.1145/987305.987310]
• 34: F Voisin, CIGALE: A tool for interactive grammar construction and expression parsing, Science of Computer Programming, v.7 n.1, p.61-86, July 1986
• 35: [Weg70] B. Wegbreit, Studies in Extensible Programming Languages, Dissertation, Harvard, 1970, Reprinted by Garland Publishing, 1980.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax

General Terms:
Algorithms, Design, Languages, Standardization