Attributed translations(Extended Abstract)

ABSTRACT

Attributed translations are a means of specifying the input-output relation of a language processing device, such as for example the lexical or syntax box of a compiler. Considered as a mathematical object, an attributed translation is a mapping of certain strings of attributed “input symbols” into strings of attributed “action symbols”. Under the interpretation that action symbols represent the act of emitting an attributed output or the performing of some other “semantic actions”, and the attributes represent “semantic” information associated with the symbols, the model can be applied in depth to practical compiling problems. Theorems are proved giving conditions under which an attributed translation can be performed by an augmented pushdown machine while it is parsing top down or bottom up. Attributed translations are based on the ideas of attributed grammars [1] and syntax directed translations [2,3]. Other relevant concepts are property grammars and table machines [4], and attributed grammars with relations [5].

REFERENCES

• 1: Kunth, D.E., "Semantics of Context Free Languages", Math Systems Theory, 2, 2, (June 1968), pp. 127-145.
• 2: 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]
• 3: P. M. Lewis, II , R. E. Stearns, Syntax-Directed Transduction, Journal of the ACM (JACM), v.15 n.3, p.465-488, July 1968 [doi>10.1145/321466.321477]
• 4: Stearns, R.E., and Lewis, P.M., "Property Grammars and Table Machines", Information and Control, 14, 6, (June 1969), pp. 524-549.
• 5: Culik, K., "Attributed Grammars and Languages", Departement d'Informatique, Universite de Montreal, May 1969.
• 6: Rosenkrantz, D.J., and Stearns, R.E., "Properties of Deterministic Top-Down Grammars", Information and Control, 17, 3, (October 1970), pp. 226-256.
• 7: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 8: Knuth, D.E., "On the Translation of Languages from Left to Right", Information and Control, 8, 6, (December 1965), pp. 607-639.
• 9: Harrison, M.A., and Havel, I.M., Strict Deterministic Grammars. University of California at Berkeley.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

General Terms:
Languages, Theory