zbMATH — the first resource for mathematics

Formal translation directed by \(LR\) parsing. (English) Zbl 0746.68056
Summary: The notion of the syntax-directed translation was a highly influential idea in theory of the formal translation. Models for the description of a formal translation are syntax-directed translation schemes. The special case of syntax-directed translation schemes are simple syntax-directed translation schemes, which can be written in the form of translation grammars. It is possible for an arbitrary translation described by a translation grammar with \(LL(k)\) input grammar to create one-pass translation algorithm by a simple extension of the algorithm of a syntax analysis for \(LL(k)\) grammars. Similar approach for an \(LR(k)\) grammar led to the result that it is possible to perform an one-pass formal translation during \(LR(k)\) analysis only in that case when the translation grammar has a postfix property. The construction of the algorithm is studied, which can, for a particular class of translation grammars (called \(LR(k)\;R\)-translation grammars), perform one pass formal translation. The basic idea is the following: It is possible to make an extension of the algorithm of the syntax analysis for \(LR(k)\) grammars in such a way, that the output of output symbols can be performed not only as a part of the operation reduction but also as a part of the operation shift.

68N20 Theory of compilers and interpreters
68Q42 Grammars and rewriting systems
Full Text: Link EuDML
[1] A.V. Aho, J.D. Ullman: Properties of syntax directed translations. J. Comput. System Sci. 3 (1969), 3, 319 - 334. · Zbl 0174.02802 · doi:10.1016/S0022-0000(69)80018-8
[2] A. V. Aho, J. D. Ullman: Translation on a context-free grammar. Inform, and Control 19 (1971), 5, 439 - 475. · Zbl 0244.68035
[3] A.V. Aho, J.D. Ullman: The Theory of Parsing, Translation and Compiling. Vol. 1. Parsing, Vol. 2. Compiling. Prentice-Hall, New York 1971, 1972.
[4] K. Čulík: Well-translatable grammars and Algol-like languages. Formal Language Description Languages for Computer Programming (T. B. Steel, North-Holland, Amsterdam 1966, pp. 76 - 85.
[5] E.T. Irons: A syntax directed compiler for Algol 60. Comm. ACM 4 (1961), 1, 51 - 55. · Zbl 0103.34904 · doi:10.1145/366062.366083
[6] E. T. Irons: The structure and use of the syntax-directed compiler. Annual Review in Automatic Programming 3 (R. Goodman, Pergamon Press, New York - London 1963, pp. 207 - 227.
[7] J. Krai, J. Demner: Parsing as a subtask of compiling. Mathematical Foundation of Computer Science 1975 (J. Becvaf, Lecture Notes in Computer Science 32), Springer-Verlag, Berlin - Heidelberg - New York 1975. · Zbl 0328.68022
[8] P. M. Lewis, R. E. Stearns: Syntax directed transduction. J. Assoc. Comput. Mach. 15 (1968), 3, 465 - 488. · Zbl 0164.32102 · doi:10.1145/321466.321477
[9] P. M. Lewis D. J. Rozenkrantz, R. E. Stearns: Compiler Design Theory. Addison-Wesley, London 1976.
[10] L. Petrone: Syntactic mappings of context-free languages. Proc. IFIP Congress 1965, Part 2, pp. 590 - 591.
[11] P. Purdom, C. A. Brown: Semantic routines and \(LR(k)\) parsers. Acta Inform. 14 (1980), 4, 229 - 315. · Zbl 0424.68052 · doi:10.1007/BF00286489
[12] S. Vere: Translation equation. Comm. ACM 13 (1970), 2, 83 - 89. · Zbl 0208.20001 · doi:10.1145/362007.362031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.