Ramachandran Krishnaswamy
Abstract
The correctness of semantic-syntax-directed translators (SSDTs) is examined. SSDTs are a generalization of syntax-directed translators in which semantic information is employed to partially direct the translator. Sufficient conditions for an SSDT to be “semantic-preserving,” or “correct,” are presented. A further result shows that unless certain conditions are met, it is undecidable, in general, whether an SSDT is semantic-preserving.
- 1 AHO, A V, AND ULLMAN, J D.Properties of syntax-directed translations J Comptr Syst Sct 3, 3 (1969), 319-334Google Scholar
- 2 BENSON, D Semantic-preserving translations Math Syst. Theory 8, 2 (1974), 105-126Google Scholar
- 3 BUTTELMANN, H W Semanuc-dlrected translation Amer ~ of Computational Lmgmstics 2, Microfiche 7 (Nov 1974)Google Scholar
- 4 CHOMSKY, N.SyntacUc Structures Mouton, The Hague, Netherlands, 1957Google Scholar
- 5 DIJKSTR^, E W A D~sclphne of Programming Prentice-Hall, Englewood Cliffs, N J, 1976Google Scholar
- 6 FLOYD, R W Assigning meanings to programs Proc Symp Applied Math 19, Providence, R I, 1967, pp 19-32Google Scholar
- 7 HoAR~., C A R Consistent and complementary formal theories of the semantics of programming languages Acta lnformatzca 3 (1974), 135-163Google Scholar
- 8 HOPCROFT, J E, AND ULLMAN, j.D Formal Languages and Thew Relatton to Automata. Addision-Wesley, Reading, Mass, 1969 Google Scholar
- 9 JAZAYERI, M, OGDEN, W F, AND ROUNDS, W C The mtrmslcally exponential complexity of the circularity problem for attnbute grammars Comm ACM 18, 12 (Dec 1975), 697-706 Google Scholar
- 10 KING, J.C Proving programs to be correct IEEE Trans Comptr C-20, 11 (Nov 1971), 1331-1336Google Scholar
- 11 KNUTH, D.E. Semantics of context-free languages. Math. Syst. Theory 2, 2 (1968).Google Scholar
- 12 KNUTH, D E Examples of formal semantics Lecture Notes m Math 188 (197 I)Google Scholar
- 13 KRISHNASWAMY, R AND BUTTELMANN, H W Formal methodology of translation Inform and Control 39, 3 (Dec 1978), Pt, I, 247-271, Pt. II, 272-293Google Scholar
- 14 LUCAS, P, LAUER, P, AND STIGLEITNER, H Method and notton for the formal definition of programming languages Tech Rep TR25 087, IBM Vienna Laboratory, Vienna, Austria, 1968Google Scholar
- 15 PYSTER, A B, AND BUTTELMANN, H W Semantic-syntax-directed translation inform and Control 36, 3 (Mar 1978), 320--361.Google Scholar
- 16 SCOTT, D, AND STRACHEY, C Towards a mathematical semantics for computer languages Tech Rep PRG-6, Programming Research Group, Oxford U, Oxford, England, 1971Google Scholar
- 17 WEGBREIT, B. The synthesis of loop predicates. Comm A CM 17, 2 (Feb 1974), 102-112 Google Scholar
Index Terms
- On the Correctness of Semantic-Syntax-Directed Translations
Recommendations
Properties of syntax directed translations
Translations that can be expressed as generalizations of context free grammars and pushdown automata are defined. The types of translations defined are ordered according to power. For each type, certain necessary conditions that a translation be of that ...
Syntax-Directed Pretty Printing A First Step Towards a Syntax-Directed Editor
A language-independent syntax-directed pretty printer has been implemented as the first step towards building a language-independent syntax-directed editor. The syntax-directed pretty printer works in two phases: the grammar processing phase and the ...
Syntax-Directed Machine Translation of Natural Language: Effect of Garden Path Phenomenon on Sentence Structure
ISDEA '10: Proceedings of the 2010 International Conference on Intelligent System Design and Engineering Application - Volume 02The potential of current machine translation (MT) of natural languages is discussed by comparing the output of embedded structure sentence, ambiguous sentence and garden path sentence. The syntax-oriented MT is a kind of literal translation which may be ...
Comments