ABSTRACT
Language-specific editors for typed programming languages must contain a subsystem for semantic analysis in order to guarantee correctness of programs with respect to the context conditions of the language. As programs are usually incomplete during development, the semantic analysis must be able to cope with missing context information, e. g. incomplete variable declarations or calls to procedures imported from still missing modules. In this paper we present an algorithm for incremental semantic analysis, which guarantees immediate detection of semantic errors even in arbitrary incomplete program fragments. The algorithm is generated from the language's context conditions, which are described by inference rules. During editing, these rules are evaluated using a unification algorithm for many-sorted algebras with semi-lattice ordered subsorts and non-empty equational theories. The method has been implemented as part of the PSG system, which generates interactive programming environments from formal language definitions, and has been successfully used to generate an incremental semantic analysis for PASCAL and MODULA-2.
- /AhoB73/ Aho, A. V., Beeri, C., Ullman, J. D: The theory of joins in relational databases. ACM TODS 4 (1979), 3, pp. 297--314 Google ScholarDigital Library
- /Aust83/ Austermühl, B.: Ein relationaler Ansatz zur Beschreibung der statischen Semantik von Programmiersprachen. PhD thesis, Technische Hochschule Darmstadt 1983Google Scholar
- /BaSn85/ Bahlke, R. Snelting, G.: The PSG - Programming System Generator. Proc. ACM SIGPLAN 85, Language issues in programming environments. SIGPLAN notices 20 (1985), 7, pp. 28--33 Google ScholarDigital Library
- /JoFi82/ Johnson, G. F. Fisher, C. N.: Non-syntactic attribute flow in language-based editors. Proc. 9th ACM symposium on principles of programming languages, 1982, pp. 196--206 Google ScholarDigital Library
- /Hab82/ Habermann, N. et al: The second compendium of Gandalf documentation. Dept. of Computer science, Carnegie Mellon University 1982Google Scholar
- /HeSn84/ Henhapl, W., Snelting, G.: Context relations: a concept for incremental context analysis in program fragments. Proc. GI Fachtagung Programmiersprachen und Programmentwicklung, Springer Verlag 1984, Informatik Fachberichte 77, pp. 128--143 Google ScholarDigital Library
- /HuSc83/ Hunkel, M., Schmitt, H.: Ein System zur Bezeichneridentifikation und dessen Integration in ein strukturorientiertes Ediersystem. Diploma thesis, Technische Hochschule Darmstadt 1983.Google Scholar
- /Miln78/ Milner, R.: A theory of type polymorphism in programming. J. Computer and system sciences 17 (1978), pp. 348--375Google Scholar
- /PSG85/ Bahlke, R., Hunkel,M., Klung, M., Snelting, G.: Language definers guide to PSG. Report PU2R3/85, Technische Hochschule Darmstadt, 1985.Google Scholar
- /Plo72/ Plotkin, G.: Building in equational theories. Machine intelligence 7 (1972), pp. 73--90Google Scholar
- /Reps83/ Reps. T., Teitelbaum, T., Demers, A.: Incremental context-dependent analysis for language-based editors. ACM TOPLAS 5 (1983), 3, pp. 449--477 Google ScholarDigital Library
- /Robi65/ Robinson, J. A.: A machine oriented logic based on the resolution principle. JACM 12 (1965), 1, pp. 23--41. Google ScholarDigital Library
- /Siek84/ Siekmann, J.: Universal unification. Proc. 7th international conference on automated deduction, Springer Verlag, LNCS 170, pp. 1--42 Google ScholarDigital Library
- /Snel85/ Snelting, G.: Inkrementelle semantische Analyse in unvollstandigen Programmfragmenten mit Kontextrelationen. PhD thesis. Technische Hochschule Darmstadt 1985.Google Scholar
- Unification in many-sorted algebras as a device for incremental semantic analysis
Recommendations
Many-sorted unification
Many-sorted unification is considered; that is, unification in the many-sorted free algebras of terms, where variables, as well as the domains and ranges of functions, are restricted to certain subsets of the universe, given as a potentially infinite ...
Initial algebras and terminal coalgebras in many-sorted sets
We prove that the iterative construction of initial algebras converges for endofunctors F of many-sorted sets whenever F has an initial algebra. In the case of one-sorted sets, the convergence takes n steps where n is either an infinite regular cardinal ...
Commutative pseudo-equality algebras
Pseudo-equality algebras were initially introduced by Jenei and Kóródi as a possible algebraic semantic for fuzzy-type theory, and they have been revised by Dvureăźenskij and Zahiri under the name of JK-algebras. In this paper, we define and study the ...
Comments