Semantic routines and LR(k) parsers | Acta Informatica Skip to main content
Springer Nature Link
Log in

Semantic routines and LR(k) parsers

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

Most applications of parsing require that the parser call semantic action routines while processing the input. For LR(k) parsers it is well known that a semantic action routine can be called when the end of a production is recognized. Often, however, it is desirable to call routines at other times.

This paper presents fast algorithms that determine, for an LR(k) (or SLR(k)) grammar, which positions are suitable for calling routines. The algorithms are practical for use with LR(1) (SLR(1)) parser building programs, because the worst case running time is dominated by the time required to build the LR(1) (SLR(1)) parser. Applications of the algorithms to attribute grammars and automatic indentation are discussed.

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

Access this article

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

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aho, A.V., Ullman, J.D.: The theory of parsing, translation, and compiling, pp. 368–399. New York: Prentice-Hall 1972

    Google Scholar 

  2. De Remer, F.L.: Practical translation for LR(k) languages. Ph.D. Thesis, MIT, Cambridge, Massachusetts (1969)

    Google Scholar 

  3. Earley, J.: An efficient context-free parsing algorithm. CACM 13, 94–102 (1970)

    Google Scholar 

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

    Google Scholar 

  5. Lengauer, T., Tarjan, R.E.: A fast algorithm for finding dominators in a flow graph. TOPLAS 1, 121–141 (1979)

    Google Scholar 

  6. Lowry, E.S., Medlock, C.W.: Object code optimization. CACM 12, 13–22 (1969)

    Google Scholar 

  7. Pager, D.: The lane tracing algorithm for constructing LR(k) parsers and ways of enhancing its efficiency. Information Sci. 12, 19–42 (1977)

    Google Scholar 

  8. Pager, D.: A practical general method for constructing LR(k) parsers. Acta Informat. 7, 249–268 (1977)

    Google Scholar 

  9. Purdom, P.: The size of LALR(1) parsers. BIT 14, 326–337 (1974)

    Google Scholar 

  10. Purdom, P.W.: Automatic program indentation. BIT 18, 211–218 (1978)

    Google Scholar 

  11. Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 146–160 (1972)

    Google Scholar 

  12. Watt, D.A.: The parsing problem for affix grammars. Acta Informat. 8, 1–20 (1977)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Indiana University, 47405, Bloomington, Indiana, USA

    Paul Purdom & Cynthia A. Brown

Authors
  1. Paul Purdom
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Cynthia A. Brown
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Purdom, P., Brown, C.A. Semantic routines and LR(k) parsers. Acta Informatica 14, 299–315 (1980). https://doi.org/10.1007/BF00286489

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00286489

Keywords

Search

Navigation