Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Incremental evaluation for attribute grammars with unrestricted movement between tree modifications

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

This paper concerns the design of editors that perform checks on a language's context-dependent constraints. Our particular concern is the design of an efficient, incremental analysis algorithm for systems based on the attribute-grammar model of editing. With previous incremental evaluation algorithms for arbitrary noncircular attribute grammars, the editing model required there to be a restriction on the operation that moves the editing cursor: moving the cursor was limited to just a single step in the tree — either to the parent node or to one of the child nodes of the current cursor location. This paper describes a new updating algorithm that can be used when an arbitrary movement of the cursor in the tree is permitted. After an operation that restructures the tree, the tree's attributes can be updated with a cost of 0 ((1+¦AFFECTED¦)·√m), where m is the size of the tree and AFFECTED is the subset of the tree's attributes that require new values, when the cost is amortized over a sequence of tree modifications. the editing cursor may be moved from its current location to any other node of the tree in a single, unit-cost operation. CR Categories and Subject Descriptors: D.2.3 [Software Engineering]: Coding — program editors; D.2.6 [Software Engineering]: Programming Environments; D.3.1 [Programming Languages]: Formal Definitions and Theory — semantics, syntax D.3.4 [Programming Languages]: Processors — translator writing systems and compiler generators F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages — denotational semantics.

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
$34.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Demers, A., Reps, T., Teitelbaum, T.: Incremental evaluation for attribute grammars with application to syntax-directed editors. In Conference Record of the Eighth ACM Symposium on Principles of Programming Languages, Williamsburg, Va., Jan. 26–28, 1981, pp. 105–116

  2. Demers, A., Rogers, A., Zadeck, F.K.: Attribute propagation by message passing. In: Conference Record of the ACM SIGPLAN 85 Symposium on Language Issues in Programming Environments, Seattle, WA, June 25–28, 1985. SIGPLAN Notices 20, 43–59 (1985)

  3. Hoover, R.: Dynamically bypassing copy rule chains in attribute grammars. In: Conference Record of the Thirteenth ACM Symposium on Principles of Programming Languages, St. Petersburg, FL, Jan. 13–15, 1986, pp. 14–25

  4. Johnson, G.F., Fischer, C.N.: A meta-language and system for nonlocal incremental attribute evaluation in language-based editors. In Conference Record of the Twelfth ACM Symposium on Principles of Programming Languages, New Orleans, La., Jan. 14–16, 1985, pp. 141–151

  5. Kastens, U.: Ordered attribute grammars. Acta Inf. 13, 229–256 (1980)

    Article  MathSciNet  Google Scholar 

  6. Knuth, D.E.: Semantics of context-free languages. Math. Syst. Theory 2, 127–145 (1968) (Correction, ibid. 5, 1 (Mar 1971, 95–96)

    Article  MathSciNet  Google Scholar 

  7. Reps, T.: Optimal-time incremental semantic analysis for syntax-directed editors. In: Conference Record of the Ninth ACM Symposium on Principles of Programming Languages, Albuquerque, N.M., Jan. 25–27, 1982, pp. 169–176

  8. Reps, T.: Generating language-based environments. Cambridge, MA: M.I.T. Press 1984

    MATH  Google Scholar 

  9. Reps, T., Teitelbaum, T., Demers, A.: Incremental context-dependent analysis for language-based editors. ACM Trans. Program. Lang. Syst. 5, 449–477 (1983)

    Article  Google Scholar 

  10. Reps, T., Marceau, C., Teitelbaum, T.: Remote attribute updating for language-based editors. In: Conference Record of the 13th ACM Symposium on Principles of Programming Languages, St. Petersburg, Fla., Jan. 13–15, 1986, pp.1–13

  11. Reps, T., Demers, A.: Sublinear-space evaluation algorithms for attribute grammars. ACM Trans. Program. Lang. Syst. 9, 408–440 (1987)

    Article  Google Scholar 

  12. Reps, T., Teitelbaum, T.: The Synthesizer Generator. In: Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, Pittsburgh, Penn., Apr. 23–25, 1984. Appeared as joint issue: SIGPLAN Notices (ACM) 19, 42–48 1984, and Soft. Eng. Notes (ACM) 9, 42–48 1984

  13. Reps, T., Teitelbaum, T.: The Synthesizer Generator reference manual. Tech. Rep. 84-619, Dept. of Computer Science, Cornell Univ., Ithaca, NY, 1985 (Second edition), 1987

    MATH  Google Scholar 

  14. Tarjan, R.E.: Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

    Book  Google Scholar 

  15. Tsakalidis, A.K.: Maintaining order in a generalized linked list. Acta Inf. 21, 101–112 (1984)

    Article  MathSciNet  Google Scholar 

  16. Yeh, D.: On incremental evaluation of ordered attributed grammars. BIT 23, 308–320 (1983)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Sciences Department, University of Wisconsin, 1210 W. Dayton St., 53706, Madison, WI, USA

    Thomas Reps

Authors
  1. Thomas Reps
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was supported in part by the National Science Foundation under grant DCR-8552602, by an IBM Faculty Development Award, and by grants from Digital Equipment Corporation, Siemens, and Xerox

Rights and permissions

Reprints and permissions

About this article

Cite this article

Reps, T. Incremental evaluation for attribute grammars with unrestricted movement between tree modifications. Acta Informatica 25, 155–178 (1988). https://doi.org/10.1007/BF00263583

Download citation

  • Received:

  • Published:

  • Issue Date:

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

Keywords

Search

Navigation