Attributed Translations | SpringerLink
Skip to main content
Springer Nature Link
Log in

Attributed Translations

  • Chapter
Fundamental Problems in Computing

Abstract

Attributed translation grammars are introduced as a means of specifying a translation from strings of input symbols to strings of output symbols. Each of these symbols can have a finite set of attributes, each of which can take on a value from a possibly infinite set. Attributed translation grammars can be applied in depth to practical compiling problems.

Certain augmented pushdown machines are defined and characterizations are given of the attributed translations they can perform both deterministically and nondeterministically. Classes of attributed translation grammars are defined whose translation can be performed deterministically while parsing top down or bottom up.

A preliminary version of this paper was presented at the 1973 Fifth Annual ACM Symposium on the Theory of Computing.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
JPY 14299
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. G. V. Bochman. Semantics evaluated from left to right. Technical report, Departement d’Informatique, Univ. de Montreal, 1973.

    Google Scholar 

  2. D. Crowe. Generating parsers for affix grammars. Comm. Assoc. Computing Mach., 15:728–734, 1972.

    MATH  MathSciNet  Google Scholar 

  3. K. Culik. Attributed grammars and languages. Technical report, Departement d’Informatique, Univ. de Montreal, 1969.

    Google Scholar 

  4. D. Gries. Compiler Construction for Digital Computers. Wiley, New York, 1971.

    MATH  Google Scholar 

  5. M. A. Harrison and I. M. Havel. Strict deterministic grammars. J. Comput. System Sci., 7:237–277, 1973.

    MATH  MathSciNet  Google Scholar 

  6. J. E. Hopcroft and J. D. Ullman. Formal Languages and Their Relation to Automata. Addison–Wesley, Reading, 1969.

    MATH  Google Scholar 

  7. E. T. Irons. A syntax directed compiler for ALGOL 60. Comm. Assoc. Comput. Mach., 4:51–55, 1961.

    MATH  Google Scholar 

  8. D. E. Knuth. On the translation of languages from left to right. Information and Control, 8:607–639, 1965.

    Article  MathSciNet  Google Scholar 

  9. D. E. Knuth. The Art of Computer Programming: Fundamental Algorithms, volume 1. Addison–Wesley, Reading, 1968.

    MATH  Google Scholar 

  10. D. E. Knuth. Semantics of context free languages. Math. Systems Theory, 2:127–145, 1968.

    Article  MATH  MathSciNet  Google Scholar 

  11. C. H. A. Koster. Affix grammars. In ALGOL 68 Implementation. North-Holland, Amsterdam, 1971.

    Google Scholar 

  12. P. M. Lewis and R. E. Stearns. Syntax directed transduction. J. Assoc. Comput. Mach., 15:465–488, 1968.

    MATH  Google Scholar 

  13. D. J. Rosenkrantz and R. E. Stearns. Properties of deterministic top-down grammars. Information and Control, 17:226–256, 1970.

    Article  MATH  MathSciNet  Google Scholar 

  14. R. E. Stearns and P. M. Lewis. Property grammars and table machines. Information and Control, 14:524–549, 1969.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. General Electric Company, Research and Development Center, Schenectady, NY, 12345, USA

    P. M. Lewis, D. J. Rosenkrantz & R. E. Stearns

Authors
  1. P. M. Lewis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D. J. Rosenkrantz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. E. Stearns
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University at Albany—SUNY, 1400 Washington Avenue, Albany, NY, 12222, USA

    S. S. Ravi

  2. Bradley Dept. Electrical and Computer Engineering, Virginia Tech, 302 Whittemore (0111), Blacksburg, VA, 24061, USA

    Sandeep K. Shukla

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer Science + Business Media B.V.

About this chapter

Cite this chapter

Lewis, P.M., Rosenkrantz, D.J., Stearns, R.E. (2009). Attributed Translations. In: Ravi, S.S., Shukla, S.K. (eds) Fundamental Problems in Computing. Springer, Dordrecht. https://doi.org/10.1007/978-1-4020-9688-4_2

Download citation

  • DOI: https://doi.org/10.1007/978-1-4020-9688-4_2

  • Publisher Name: Springer, Dordrecht

  • Print ISBN: 978-1-4020-9687-7

  • Online ISBN: 978-1-4020-9688-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics