The PSG system: from formal language definitions to interactive programming environments

ABSTRACT

The PSG programming system generator developed at the Technical University of Darmstadt produces interactive, language-specific programming environments from formal language definitions. All language-dependent parts of the environment are generated from an entirely nonprocedural specification of the language's syntax, context conditions, and dynamic semantics. The generated environment consists of a language-based editor, supporting systematic program development by named program fragments, an interpreter, and a fragment library system. The major component of the environment is a full-screen editor, which allows both structure and text editing. In structure mode the editor guarantees prevention of both syntactic and semantic errors, whereas in textual mode it guarantees their immediate recognition. PSG editors employ a novel algorithm for incremental semantic analysis which is based on unification. The algorithm will immediately detect semantic errors even in incomplete program fragments. The dynamic semantics of the language are defined in denotational style using a functional language based on the lambda calculus. Program fragments are compiled to terms of the functional language which are executed by an interpreter. The PSG generator has been used to produce environments for Pascal, ALGOL 60, MODULA-2, and the formal language definition language itself.

REFERENCES

• 1: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 2: Hassan Aït-Kaci , Roger Nasr, Logic and inheritance, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.219-228, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512664]
• 3: AMBRIOLA, V., AND MONTANGERO, C. Automatic generation of execution tools in a GANDALF environment. J. Syst. Softw. 5, 2 (May 1985), 155-171.
• 4: BAHLKE, R., ANO LETSCHERT, T. The BLKS system: Towards the generation of programming environments. In Proceedings 3. Gl-Fachgesprach Compiler-Compiler (Munich, Mar. 1982), W. Henhapl, Ed., 153-173.
• 5: BAHLKE, R., AND SNELTING, G. Programmiersystemgenerator--Arbeitsbericht 1984, Rep. PU2R2/84, TH Darmstadt, Feb. 1984.
• 6: BAHLKE, R, AND LETSCHERT, T. Ausf~ihrbare Denotationale Semantik. In Proceedings 4. GI-Fachgespr~ch Implementierung yon Programmiersprachen (Zurich, Mar. 1984), H. Ganzinger, Ed., 3-19.
• 7: Rolf Bahlke , Gregor Snelting, The PSG - Programming System Generator, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.28-33, June 25-28, 1985, Seattle, Washington, United States
• 8: Rolf Bahlke , Gregor Snelting, Context-sensitive editing with PSG environments, An international workshop on Advanced programming environments, p.26-38, January 1986, Trondheim, Norway
• 9: The Vienna Development Method: The Meta-Language, January 1978
• 10: BJORNER, D., AND JONES, C.B. Formal Specification and Software Development. Prentice-Hall, Englewood Cliffs, N.J., 1982.
• 11: Chris Clack , Simon L. Peyton Jones, Strictness analysis—a practical approach, Proc. of a conference on Functional programming languages and computer architecture, p.35-49, January 1985, Nancy, France
• 12: DESPEYROUX, T. Executable specification of static semantics. In Lecture Notes in Computer Science, 173. Springer Verlag, New York, 1984, 215-233.
• 13: V. Donzeau-Gouge , G. Kahn , B. Lang , B. Mélèse, Document structure and modularity in mentor, ACM SIGPLAN Notices, v.19 n.5, p.141-148, May 1984
• 14: ELLISON, R. J., AND STAUDT, B.J. The evolution of the GANDALF system. J. Syst. Softw. 5, 2 (May 1985), 107-119.
• 15: GILOI, W. K., AND M(~HLENBEIN, H. Rationale and concepts for the SUPRENUM supercomputer architecture. Internal Rep., Gesellschaft ~r Mathematik und Datenverarbeitung, 1985.
• 16: GOGUEN, J. A. Order-sorted algebras: Exception and error sorts, coercions and overloaded operators. Semantics and Theory of Computation Rep. 14, UCLA, 1978.
• 17: HENHAPL, W. Von der Compiler-Generierung zu der Programmiersystemgenerierung. In Proceedings 1. GI-Fachgespr~ch Compiler-Compiler (Berlin, Sept. 1978), 160-169.
• 18: HENHAPL, W., AND LETSCHERT, T. VDM in research, development, and education: Local experiences. In Formal Models in Programming. North-Holland, Amsterdam, 1985, 157-180.
• 19: Paul Hudak , Jonathan Young, Higher-order strictness analysis in untyped lambda calculus, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-109, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512653]
• 20: Gregory F. Johnson , C. N. Fischer, A meta-language and system for nonlocal incremental attribute evaluation in language-based editors, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.141-151, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318627]
• 21: JOHNSON, S.C. YACC: Yet another compiler-compiler. In UNIX Programmer's Manual Vol. 2B, Bell Labs., July 1978.
• 22: KAHN, G., LANG, B., Mi~LI~SE, B., AND MORCOS, E. METAL: A formalism to specify formalisms. Sci. Comput. Program. 3 (1983), 151-188.
• 23: LANDIN, P.J. The mechanical evaluation of expressions. Comput. J. 6, 4 (1964), 308-320.
• 24: Raul I. Medina-Mora, Syntax-directed editing: towards integrated programming environments, 1982
• 25: MEDINA-MORA, R., NOTKIN, D. S., AND ELLISON, g.J. ALOE user's and implementor's guide. Carnegie-Mellon Univ., May 1982.
• 26: Lambert Meertens, Incremental polymorphic type checking in B, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.265-275, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567092]
• 27: MILNER, R. A theory of type polymorphism in programming. J. Comput. Syst. Sci. 17, 3 (1978), 348-375.
• 28: MOSSES, P. SIS--Semantics Implementation System, reference manual and user guide. Rep. DAIMI MD-30, Aarhus Univ., Aug. 1979.
• 29: PLOTKIN, G. Building in equational theories. Mach. InteU. 7 (1972), 73-90.
• 30: Steven P. Reiss, An approach to incremental compilation, ACM SIGPLAN Notices, v.19 n.6, p.144-156, June 1984
• 31: Thomas Reps, Generating Language-Based Environments, Cornell University, Ithaca, NY, 1982
• 32: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 33: Thomas Reps , Tim Teitelbaum, The synthesizer generator, ACM SIGPLAN Notices, v.19 n.5, p.42-48, May 1984
• 34: Thomas W. Reps , Tim Teitelbaum, The synthesizer generator reference manual (3rd ed.), Springer-Verlag New York, Inc., New York, NY, 1989
• 35: REPS, T., AND SNELTING, G. Context relations implemented with attribute grammars. Cornell Univ., Jan. 1986.
• 36: Pierre Rety , Claude Kirchner , Hélène Kirchner , Pierre Lescanne, NARROWER: a new algorithm for unification and its application to logic programming, Proc. of the first international conference on Rewriting techniques and applications, p.141-157, December 1985, Dijon, France
• 37: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 38: Jörg H. Siekmann, Universal Unification, Proceedings of the 7th International Conference on Automated Deduction, p.1-42, May 14-16, 1984
• 39: Gregor Snelting , Wolfgang Henhapl, Unification in many-sorted algebras as a device for incremental semantic analysis, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.229-235, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512665]
• 40: SNELTING, G. Inkrementelle semantische Analyse in unvollst~indigen Programmfragmenten mit Kontextrelationen. Doctoral thesis, TH Darmstadt, Mar. 1986.
• 41: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 42: R. D. Tennent, The denotational semantics of programming languages, Communications of the ACM, v.19 n.8, p.437-453, Aug. 1976 [doi>10.1145/360303.360308]
• 43: VUILLEMIN, J. Correct and optimal implementations of recursion in a simple programming language. J. Comput. Syst. Sci. 9 (1974), 332-354.

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Pretty printers; Program editors
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax; Semantics
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive); Parsing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)

General Terms:
Algorithms, Design, Documentation, Languages, Theory, Verification