Search results for keyword `incr'

[15]

Henk Alblas. Incremental simple multi-pass attribute evaluation. In Procs. NGI/SION Symp. 1986, pages 319-342, 1986. See also: memorandum INF-86-27, Onderafdeling der Informatica, Tech. Hogeschool Twente (August 1986).

[21]

Henk Alblas. Optimal incremental simple multi-pass attribute evaluation. Information Processing Letters, 32(6):289-295, October 1989.

[22]

Henk Alblas. Concurrent incremental attribute evaluation. In Pierre Deransart and Martin Jourdan, editors, Attribute Grammars and their Applications (WAGA), volume 461 of Lecture Notes in Computer Science, pages 343-358. Springer-Verlag, New York-Heidelberg-Berlin, September 1990. Paris.

[24]

Henk Alblas. Incremental attribute evaluation. In Henk Alblas and Borivoj Melichar, editors, Attribute Grammars, Applications and Systems, volume 545 of Lecture Notes in Computer Science, pages 215-233. Springer-Verlag, New York-Heidelberg-Berlin, June 1991. Prague.

Transformations of attributed derivation trees are considered. A tree transformation may invalidate attribute instances, not only in the restructured part of the tree, but also elsewhere in the tree. To make the attribution of the tree correct again requires a reevaluator. For some evaluation strategies, reevaluators are defined that work optimally in the number of visits to tree nodes and the number of recomputations. To remove the restriction that every transformation of an attributed derivation tree should immediately be followed by a reevaluation of the tree, criteria are formulated that permit a delay in calling the reevaluator. These criteria allow a strategy of repeatedly applying alternate attribute-evaluation and tree-transformation phases. An attribute-evaluation phase consists of a tree walk in which all attributes receive their correct values. A tree-transformation phase consist of a tree walk in which as many tree transformations are performed as possible. The transformation phase is never interrupted to carry out reevaluation. Finally, the optimal-incremental strategy is applied to the case where there has been a delay in activating the reevaluator.

[29]

Bowen Alpern, Alan Carle, Barry Rosen, Peter Sweeney, and F. Kenneth Zadeck. Incremental evaluation of attributed graphs. research report RC 13205, IBM T.J. Watson Research Center, Yorktown Heights, NY, October 1987. Also published as Technical Report CS-87-29, Department of Comp. Sc., Brown University, Providence, RI.

[31]

Bowen Alpern, Roger Hoover, Barry Rosen, Peter Sweeney, and F. Kenneth Zadeck. Maintaining solutions to changing interdependent equations. Technical Report CS-88-13, Department of Comp. Sc., Brown University, Providence, RI, November 1988.

[32]

Bowen Alpern, Roger Hoover, Barry K. Rosen, Peter F. Sweeney, and F. Kenneth Zadeck. Keeping priorities straight: an investigation of incremental algorithms. Technical Report CS-88-13, Department of Comp. Sc., Brown University, Providence, RI, November 1988.

[48]

Isabelle Attali and Didier Parigot. Integrating Natural Semantics and Attribute Grammars: the Minotaur System. Rapport de recherche 2339, INRIA, 1994. (Gzipped PostScript, 19 pages, 128408 bytes)

This papers describes the principles and the functionalities of the Minotaur system. Minotaur is a generic interactive environment based on the integration of the Centaur system and the FNC-2 system, two systems widely used to specify syntax and semantics of programming languages and generate efficient semantic tools from these specifications. We show how Attribute Grammars techniques can be adequate for evaluation of a quite large subclass of Natural Semantics specifications, including specifications of an arithmetic calculator, a tree transformation, a type-checker for an Algol-like language, ... For this subclass of Natural Semantics specifications, the Minotaur system automatically generates an incremental and efficient (in time and memory) evaluator which gives to Natural Semantics an industrial strength implementation.

[82]

George M. Beshers and Roy H. Campbell. Maintained and constructor attributes. In ACM SIGPLAN '85 Symp. on Language Issues in Programming Environments, pages 34-42. ACM press, Seattle, WA, June 1985. Published as ACM SIGPLAN Notices, volume 20, number 7.

[130]

Alan Carle and Lori Pollock. A context-based incremental evaluator for hierachical attribute grammars. Journal of Programming Languages, 3, March 1995.

[131]

Alan Carle and Lori Pollock. Matching-based incremental evaluators for hierarchical attribute grammar dialects. ACM Transactions on Programming Languages and Systems, 17(2):394-429, March 1995.

[132]

Alan Carle and Lori Pollock. On the optimality of change propagation for incremental evaluation of hierarchical attribute grammars. ACM Transactions on Programming Languages and Systems, 18(1), 1996.

[134]

M. D. Carroll and Barbara G. Ryder. Incremental data flow analysis via dominator and attribute updates. In 15th ACM Symp. on Principles of Progr. Languages, pages 274-284. ACM press, San Diego, CA, January 1988.

[152]

Henning Christiansen. Structure sharing in incremental systems. Struct. Programm., 10(4):169-186, 1989.

[157]

Loïc Correnson, Etienne Duris, Didier Parigot, and Gilles Roussel. Attribute grammars and functional programming deforestation. In Fourth International Static Analysis Symposium -- Poster Session, Paris, France, September 1997. (Gzipped PostScript, 16 pages, 88632 bytes)

The functional programming community is paying increasing attention to static structure-based transformations. For example, generic control operators, such as fold, have been introduced in functional programming to increase the power and applicability of a particular kind of static transformation, called deforestation, which prevents the construction of useless intermediate data structures in function composition. This is achieved by making the structure of the data more explicit in program specifications. We argue that one of the original concepts of Attribute Grammars is precisely to make data structures explicit in program specifications. Furthermore, there exists a powerful static deforestation-like transformation in their context. In this paper, we present similarities between deforestation methods, on the one hand with the functional approach, and on the other hand with the Attribute Grammars approach. In order to gain a grasp of these similarities, we first make a simple comparison: purely-synthesized Attribute Grammars and first order folds. In this context, deforestation transformations are equivalent. This allows us to highlight the limitations of the fold formalism and to present how the hylomorphism approach generalizes it; hylomorphisms and attribute grammars are surprisingly alike. Finally, we show how the inherited attribute notion in Attribute Grammars solves some transformation problems in higher order functional programs.

[181]

Alan Demers, Thomas Reps, and Tim Teitelbaum. Incremental evaluation for attribute grammars with application to syntax-directed editors. In 8th ACM Symp. on Principles of Progr. Languages, pages 105-116. ACM press, Williamsburg, VA, January 1981.

[182]

Alan Demers, Anne Rogers, and F. Kenneth Zadeck. Attribute propagation by message passing. In ACM SIGPLAN '85 Symp. on Language Issues in Programming Environments, pages 43-59. ACM press, Seattle, Wa, June 1985. See also: report RC11109, IBM T.J. Watson Research Center, Yorktown Heights, NY (1985).Published as ACM SIGPLAN Notices, volume 20, number 6.

[222]

Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Attribute grammars and folds: Generic control operators. Rapport de recherche 2957, INRIA, August 1996. (Gzipped PostScript, 29 pages, 176512 bytes)

Generic control operators, such as fold, have been introduced in functional programming to increase the power and applicability of data-structure-based transformations. This is achieved by making the structure of the data more explicit in program specifications. We argue that this very important property is one of the original concepts of attribute grammars. In this paper, we informally show the similarities between the fold formalism and attribute grammar specifications. We also compare their respective method to eliminate the intermediate data structures introduced by function composition (notion of deforestation or fusion): the normalization algorithm for programs expressed with folds and the descriptional composition of attribute grammars. Rather than identify the best way to achieve deforestation, the main goal of this paper is merely to intuitively present two programming paradigms to each other's supporting community and provide an unbiased account of their similarities and differences, in the hope that this leads to fruitful cross-fertilization.

[225]

Etienne Duris, Didier Parigot, Gilles Roussel, and Martin Jourdan. Structure-directed genericity in functional programming and attribute grammars. Rapport de Recherche 3105, INRIA, February 1997. (Gzipped PostScript, 18 pages, 122262 bytes)

Generic control operators, such as fold, have been introduced in functional programming to increase the power and applicability of data-structure-based transformations. This is achieved by making the structure of the data more explicit in program specifications. We argue that this very important property is one of the original concepts of attribute grammars. In this paper, we present the similarities between the fold formalism and attribute grammars. In particular, we show the equivalence of their respective deforestation methods. Given these results and the fundamental role of deforestation in the concept of structure-directed genericity, first devised for attribute grammars with descriptional composition, we show how the fold operator with its fusion method allow to transport this concept in the area of functional programming.

[260]

Rodney Farrow, Thomas J. Marlowe, and Daniel M. Yellin. Composable attribute grammars: Support for modularity in translator design and implementation. In 19th ACM Symp. on Principles of Programming Languages, pages 223-234, Albuquerque, NM, January 1992. ACM press.

This paper introduces composable attribute grammars (CAGs), a formalism that extends classical attribute grammars to allow for the modular composition of translation specifications and of translators. CAGs bring to complex translator-writing systems the same benefits of modularity found in modern programming languages, including comprehensibility, reusability, and incremental meta-compilation. After introducing CAGs by way of an example, we provide a formal definition of CAGs and their semantics. We describe a subclass of CAGs, called separable CAGs, that have favorable implementation properties. We discuss the novel aspects of CAGs, compare them to other proposals for inserting modularity into attribute grammars, and relate our experience using CAGs in the Linguist translator-writing system. (27 Refs.)

[276]

An Feng, Tohru Kikuno, and Koji Torii. Incremental attribute evaluation for multiple subtree replacements in structure-oriented environments. In Pierre Deransart and Martin Jourdan, editors, Attribute Grammars and their Applications (WAGA), volume 461 of Lecture Notes in Computer Science, pages 192-206. Springer-Verlag, New York-Heidelberg-Berlin, September 1990. Paris.

[279]

Gilberto Filé. Classical and incremental attribute evaluation by means of recursive procedures. In Paul Franchi-Zannettacci, editor, 11th Coll. on Trees in Algebra and Programming (CAAP '86), volume 214 of Lecture Notes in Computer Science, pages 112-126. Springer-Verlag, New York-Heidelberg-Berlin, March 1986. Nice.

[281]

Gilberto Filé. Classical and incremental attribute evaluation by means of recursive procedures. Theoretical Computer Science, 53(1):25-65, January 1987.

[302]

R. A. Frost. Guarded attribute grammars. Software - Practice and Experience, 23(10):1139-1156, 1993.

Contrary to a widely-held belief it is possible to construct executable specifications of language processors that use a top-down parsing strategy and which have structures that directly reflect the structure of grammars containing left-recursive productions. A novel technique has been discovered by which the non-termination that would otherwise occur is avoided by 'guarding' top-down left-recursive language processors by non-left-recursive recognizers. The use of a top-down parsing strategy increases modularity and the use of left-recursive productions facilitates specification of semantic equations. A combination of the two is of significant practical value because it results in modular and expressively clear executable specifications of language processors. The new approach has been tested in an attribute grammar programming environment that has been used in a number of projects including the development of natural language interfaces, SQL processors and circuit design transformers within a VLSI design package.

[317]

Harald Ganzinger, Knut Ripken, and Reinhard Wilhelm. MUG1---an incremental compiler-compiler. In ACM 1976 Annual Conf., pages 415-418. Houston, TX, October 1976.

[334]

Harald Ganzinger. Increasing modularity and language-independency in automatically generated compilers. Science of Computer Programming, 3(3):223-278, December 1983. See also: Bericht TUM-I8306, Institut für Informatik, Tech. University München (July 1983).

[373]

Tibor Gyimóthy. Natural languages interface construction using attribute grammars. In Henk Alblas and Borivoj Melichar, editors, Attribute Grammars, Applications and Systems, volume 545 of Lecture Notes in Computer Science, pages 460-468. Springer-Verlag, New York-Heidelberg-Berlin, June 1991. Prague.

Natural language interfaces represent one of the most common applications of natural language processing. In the eighties, not only a considerable increase in natural language interface refinement has been achieved, but also methods for design and evaluation have been worked out. One might think that a natural language interface of the nineties would be properly described in terms of three parameters, viz. begin itemize item transportability item modifiability by the user item generality end itemize We have implemented a software package for plane geometry constructions called THALES footnote THALES is a product of Cogito Co., Ltd, Hungary supplied with a natural language interface. Our experience with THALES shows that none of these features is attainable in the near future. Rather, natural language interfaces based on well-defined subsets of languages and supplemented with possibly full semantics appear to be real candidates for applications in the following years.

[381]

G. Hedin. Incremental Semantic Analysis. Ph.D. thesis, Lund University, Lund, Sweden, 1992. LUTEDX/(TECS-1003)/1-276/(1992).

[383]

G. Hedin. An object-oriented notation for attribute grammars. In the 3rd European Conference on Object-Oriented Programming (ECOOP'89), BCS Workshop Series, pages 329-345, Nottingham, U.K., July 1989. Cambridge University Press. Also published in LU-CS-TR:89-42.

This paper presents an attribute grammar notation which is based on the object-oriented concepts of classification hierarchies, inheritance, and late binding. The notation allows compact and flexible language specification through the use of inheritance and equation overriding. Furthermore, demand attributes can be implemented efficiently by using a technique similar to the one used for virtual procedures in Simula. Such attributes are important especially in incremental langauge-based environments as they do not consume storage. The notation also makes it possible to define general attributes which can be accessed without knowledge of the particular langauge modelled by the grammar. This can be utilized for integration of grammar independent tools. The notation is based on a single-inheritance classification, and a discussion is given on the problems which would arise if the notation was augmented to multiple-inheritance.

[384]

Görel Hedin. Incremental static-semantics analysis for object-oriented languages using door attribute grammars. In Henk Alblas and Borivoj Melichar, editors, Attribute Grammars, Applications and Systems, volume 545 of Lecture Notes in Computer Science, pages 374-379. Springer-Verlag, New York-Heidelberg-Berlin, June 1991. Prague.

[390]

Jüri Heleviki and Merik B. Méristé. Problems in incremental construction of language processors. In O. M. Tammepuu, editor, Procs. of the Soviet-French Symposium Informatika '89, pages 70-75, Tallinn, May 1989.

[410]

Roger Hoover and Tim Teitelbaum. Efficient incremental evaluation of aggregate values in attribute grammars. In ACM SIGPLAN '86 Symp. on Compiler Construction, pages 39-50. ACM press, Palo Alto, CA, June 1986. Published as ACM SIGPLAN Notices, volume 21, number 7.

[411]

Roger Hoover. Dynamically bypassing copy rule chains in attribute grammars. In 13th ACM Symp. on Principles of Progr. Languages, pages 14-25. ACM press, St Petersburg Beach, Fl, January 1986.

Attribute grammars require copy rules to transfer values between attribute instances distant in an attributed parse tree. We introduce copy bypass attribute propagation that dynamically replaces copy rules with nonlocal dependencies, resulting in faster incremental evaluation. An evaluation strategy is used that approximates a topological ordering of attribute instances. The result is an efficient incremental evaluator that allows multiple subtree replacement on any noncircular attribute grammar.

[412]

Roger Hoover. Incremental Graph Evaluation. Ph.D. thesis, Department of Comp. Sc., Cornell University, Ithaca, NY, May 1987.

[417]

S. E. Hudson and R. King. A generator of direct manipulation office systems. ACM Trans. on Office Inf. Sys., 4(2):132, 1986.

A system for generating direct manipulation office systems is described. In these systems, the user directly manipulates graphical representations of office entities instead of dealing with these entities abstractly through a command language or menu system. These systems employ a new semantic data model to describe office entities. New techniques based on attribute grammars and incremental attribute evaluation are used to implement this data model in an efficient manner. In addition, the system provides a means of generating sophisticated graphics-based user interfaces that are integrated with the underlying semantic model. Finally, the generated systems contain a general user reversal and recovery (or undo) mechanism that allows them to be much more tolerant of human errors.

[421]

Scott E. Hudson. Incremental attribute evaluation: an algorithm for lazy evaluation in graphs. Technical Report TR 87-20, University of Arizona, Tucson, 1987.

[432]

Fahimeh Jalili. Design of Incremental Compilers. Ph.D. thesis, Department of Comp. Inf. Sc., Moore School of Elec. Eng. D2, University of Pennsylvania, Philadelphia, PA, 1982.

[434]

Fahimeh Jalili. A general incremental evaluator for attribute grammars. Science of Computer Programming, 5(1):83-96, February 1985.

[446]

Xiaoping Jia and Jiahua Qian. Incremental evaluation of attributed grammars for incremental programming environments. In IEEE COMPSAC '85, pages 342-349. Chicago, Il, October 1985.

[453]

Gregory F. Johnson and Charles N. Fischer. A meta-language and system for nonlocal incremental attribute evaluation in language-based editors. In 12th ACM Symp. on Principles of Progr. Languages, pages 141-151. ACM press, New-Orleans, LA, January 1985.

[454]

Gregory F. Johnson. An Approach to Incremental Semantics. Ph.D. thesis, Department of Comp. Sc., University of Wisconsin-Madison, 1983.

[460]

Larry G. Jones and Janos Simon. Hierarchical VLSI design systems based on attribute grammars. In 13th ACM Symp. on Principles of Progr. Languages, pages 58-69. ACM press, St Petersburg Beach, FL, January 1986.

[464]

Larry G. Jones. Incremental VLSI Design Systems Based on Circular Attribute Grammars. Ph.D. thesis, Comp. Sc. Department, Pennsylvania State University, 1986.

[465]

Larry G. Jones. Efficient evaluation of circular attribute grammars. ACM Trans. Progr. Languages and Systems, 12(3):429-462, July 1990.

[472]

Martin Jourdan and Didier Parigot. Internals and Externals of the FNC-2 Attribute Grammar System. In Henk Alblas and Borivoj Melichar, editors, Attribute Evaluation Methods, volume 545 of Lect. Notes in Comp. Sci., pages 485-504, New York-Heidelberg-Berlin, June 1991. Springer-Verlag. Prague. (Gzipped PostScript, 64 pages, 253337 bytes)

FNC-2 is a modern attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. This paper provides the reader with a brief tour inside FNC-2, presenting the most important features of its ``engine'': efficient sequential exhaustive, parallel exhaustive and sequential incremental evaluation of strongly non-circular AGs. These methods are based on the visit-sequence paradigm; the first one makes use of extensive space optimizations. Then we describe the external features of the system--attribute coupled grammar view of an AG, specially-designed AG-description language, with provisions for true modularity, and complete environment--that make it really usable for developing large-scale applications. Experience with the system is briefly reported.

[475]

Martin Jourdan, Didier Parigot, Catherine Julié, Olivier Durin, and Carole Le Bellec. Design, implementation and evaluation of the FNC-2 attribute grammar system. In Conf. on Programming Languages Design and Implementation, pages 209-222, White Plains, NY, June 1990. Published as sl ACM SIGPLAN Notices, 25(6). (Gzipped PostScript, 14 pages, 80244 bytes)

FNC-2 is a new attribute grammar processing system aiming at expressive power, efficiency, ease of use and versatility. Its development at INRIA started in 1986, and a first running prototype is available since early 1989. Its most important features are: efficient exhaustive and incremental visit-sequence-based evaluation of strongly (absolutely) non-circular AGs; extensive space optimizations; a specially-designed AG-description language, with provisions for true modularity; portability and versatility of the generated evaluators; complete environment for application development. This paper briefly describes the design and implementation of FNC-2 and its peripherals. Then preliminary experience with the system is reported.

[484]

Martin Jourdan. A Survey of Parallel Attribute Evaluation Methods. In Alblas and Melichar [9], pages 234-255. Prague. (Gzipped PostScript, 15 pages, 71416 bytes)

Exploiting parallelism in attribute evaluation is of potentially high interest because of both its applications (e.g. in speeding up heavily-used programs such as compilers) and its feasibility (i.e. most practical attribute grammars exhibit much parallelism). In this paper we review and compare the various methods that have appeared in the literature for both exhaustive and incremental attribute evaluation on both tightly-coupled (shared-memory) and loosely-coupled (distributed) architectures. We pay particular attention to a simple but effective method for constructing efficient visit-sequence-based evaluators that run on tightly-coupled multi-processor machines by giving an account of how we implemented this method in practice and reporting the results of preliminary but realistic experiments; these results are highly encouraging.

[494]

G. E. Kaiser and D. Garlan. MELD: A declarative language for writing methods. Technical report, Carnegie-Mellon University, SEI, Pittsburgh, PA, June 1986.

Object-oriented programs are written as collections of messages. When an object receives a message, the system attempts to find a method with the same name as given in the message. The system queries the class that defines the object. If the class provides a corresponding method, the method is performed. The method may return a value to the sender of the message. It may have side-effects on the local memory of the object. The method may send messages to additional objects as part of it computation. This notion of encapsulating operations, in the form of methods, within the definition of an object is common to essentially all object-oriented programming languages. Messages and methods are currently written in what is fundamentally a procedural style. A messagge is a procedure call with several parameters, where one parameter is distinguished as the object to which the message is sent. A method is a procedure: it may return a value, have side-effects, and invoke other procedures by sending messages. We believe that the object-oriented framework lends itself quite easily to the description of programs in a declarative language. In this paper, we propose a declarative language for writing messages and methods. Our notation retains all the important features of object-oriented programming, but adds a higher level of abstraction to the description of object behavior. Our language, called MELD, is an extension of attribute grammars. Its implementation takes advantage of algorithms developed for incremental attribute grammar evaluation in the context of language-based programming environments.

[495]

Gail E. Kaiser and Simon M. Kaplan. Parallel and distributed incremental attribute evaluation. Technical Report CUCS-412-88, Department of Comp. Sc., Columbia University, New York, September 1988.

[496]

Gail E. Kaiser and Simon M. Kaplan. Parallel and distributed incremental attribute evaluation algorithms for multi-user software development environments. In ACM Transactions on Software Engineering and Methodology, volume 2 of 1, pages 47-92. ACM press, January 1993.

The problem of change propagation in multiuser software development environments distributed across a local-area network is addressed. The program is modeled as an attributed parse tree segmented among multiple user processes and changes are modeled as subtree replacements requested asynchronously by inidividual users. Change propagation is then implemented using decentralised incremental evaluation of an attribute grammar that defines the static semantic properties of the programming language. Building up to our primary result, we first present algorithms that support parallel evaluation on a centralised tree in response to single edits using a single diting cursor and multiple dits with multiple editing cursors. Then we present our algorithm for parallel evaluation on a decentralized tree. We also present a protocol to guarantee reliability of the evaluation algorithm as components of the decentralized tree become unavailable due to failures and return to availability.

[499]

Gail E. Kaiser. Semantics of Structure Editing Environments. Ph.D. thesis, Department of Comp. Sc., Carnegie-Mellon University, 1985.

This thesis addresses the processing of semantics by structure editor-based programming environments. This processing is peformed incrementally while the user writes and tests her programs. The semantics processing involves the manipulation of two kinds of properties, static and dynamic. Static properties can be determined by inspection of the program while dynamic properties reflect the interaction between the user and the programming environment. The implementor of a programming environment describes the semantics processing in terms of these properties. For example, symbol resolution, type checking, and code generation involve static properties while interpretation, run-time support and language-oriented debugging involve dynamic properties. Recent research in structure editing environments has focused on the generation of programming environments from descriptions. Several mechanisms have been proposed for writing the semantics description, and the most successful of these have been action routines and attribute grammars. However, action routines are written as a collection of imperative subroutines and it has proved difficult for an implementor need not be concerned with subtle interactions because all interactions among attribute grammar rules are handled automatically. Unfortunately, attribute grammars have been successfully applied only to the description of static properties, and have hitherto seemed unsuited to the description of dynamic properties. This thesis describes a very large extension to attribute grammars that solves this problem. The extended paradigm is called action equations. Action equations are written in a declarative notation that retains the flavor of attribute grammars but adds an easy means to express dynamic properties as well as static properties. The extensions to attribute grammars include attaching particular attribute grammar-style rules to events that represent uer commands; supporting propagation of events as well as supporting propagation of change with respect to attribute values; and limited support for non-applicative mechanisms, allowing attributes to be treated as variables and permitting modification in addition to replacement for changing the values of attributes. Together, these extensions are sufficient to support dynamic properties.

[503]

Simon M. Kaplan and Steven K. Goering. Priority controlled incremental attribute evaluation in attributed graph grammars. In J. Díaz and F. Orejas, editors, TAPSOFT '89, Vol. 1: Coll. on Trees in Algebra and Programming (CAAP '89), volume 351 of Lecture Notes in Computer Science, pages 306-320. Springer-Verlag, New York-Heidelberg-Berlin, 89. Barcelona.

[504]

Simon M. Kaplan and Gail E. Kaiser. Incremental attribute evaluation in distributed language-based environments. In 5th ACM Symp. on Principles of Distributed Computing, pages 121-130. ACM press, Calgary, August 1986. See also: report UIUCDCS-R-86-1294, University of Illinois at Urbana-Champaign (September 1986).

[506]

Simon M. Kaplan. Incremental attribute evaluation on graphs. Technical Report UIUC-DCS-86-1309, University of Illinois at Urbana-Champaign, December 1986. revised version.

[507]

Simon M. Kaplan. Incremental attribute evaluation on node-label controlled graphs. Technical Report UIUCDCS-R-87-1309, Department of Comp. Sc., University of Illinois at Urbana-Champaign, May 1987.

[548]

Jürgen Knopp and Scott E. Hudson. Attributierte transitionsnetze und ihre anwendungen in programmierumgebungen incremental attribute evaluation: a flexible algorithm for lazy update. ACM Trans. Progr. Languages and Systems, 13(3):315-341, July 1987. Bericht TUM-INFO-10-87-I14-350.

[590]

Matthijs Kuiper and João Saraiva. Lrc A generator for incremental language-oriented tools. In Kai Koskimies, editor, Compiler Construction CC'98, volume 1383 of Lect. Notes in Comp. Sci., pages 298-301, portugal, April 1998. Springer-Verlag. tool demonstration.

[598]

R. P. A. Lacroix. Semantics-directed editing in an incremental processing environment. Master's thesis, Worcester Polytechnic Inst., December 1983.

[618]

Theodore W. Leung. Compiling object-oriented queries. Technical Report CS-94-05, Department of Computer Science, Brown University, February 1994.

The effectiveness of database query optimization is dependent on the optimizer's ability to make efficient use of physical resources in a computer system. The optimizer decides how to use those resources in the plan generation step. We describe an approach to plan generation where physical level rewriting produces performance increases which cannot be obtained via source level transformations. Example optimizations serve as a demonstration of a new rule language based on list and tree pattern matching. A formalism similar to attribute grammars computes information needed by the plan generator. Many of the techniques presented are reminiscent of compiler optimizations. We conclude by describing the work that will be completed in the thesis.

[628]

Vincent Lextrait and Alain Zarli. Meta-generation of incremental and graphical structure-oriented editors. BIGRE, (70), September 1990.

[631]

Peter Lipps, Ulrich Möncke, Matthias Olk, and Reinhard Wilhelm. Attribute (re)evaluation in OPTRAN. Acta Informatica, 26:213-239, 1988. See also: ESPRIT PROSPECTRA Project Report S.1.3 - R.4.0, University des Saarlandes, Saarbrücken (1986).

[634]

Peter Lipps. Komplexe Attribute--Mechanismen zur Verwaltung und Berechnung in einem baumtransformierenden System. Diploma thesis, FB 10 -- Informatik, University des Saarlandes, Saarbrücken, 1986.

[636]

Yanhong A. Liu. CACHET:an interactive, incremental-attribution-based program transformation system for deriving incremental programs. Technical report, Cornell University, 1995.

[648]

Qi Lu and Jiahua Qian. Design, proof and analysis of new efficient algorithms for incremental attribute evaluation. In M. P. Chytil, L. Janiga, and V. Koubek, editors, Mathematical Foundations of Computer Science 1988, volume 324 of Lecture Notes in Computer Science, pages 483-491. Springer-Verlag, New York-Heidelberg-Berlin, August 1988. Carlsbad.

[649]

Qi Lu and Jiahua Qian. An efficient method for incremental attribute evaluation by using multi-dependency. In COMPSAC '88, pages 162-169. Chicago, IL, October 1988.

[654]

William Maddox. Incremental static semantic analysis. Technical Report CSD-97-948, University of California, Berkeley, January 14, 1998.

[686]

Borivoj Melichar. Attributed translation directed by LR parser and its implementation. In Proc. of the Bautzen Workshop on Compiler Compilers and Incremental Compilation. Akad. der Wissenschaften der DDR, 1986.

[695]

Josephine Micallef and Gail E. Kaiser. Support algorithms for incremental attribute evaluation of asynchronous subtree replacements. Technical Report CUCS-033-90, University of Columbia, 1990.

We attack the problem of incremental attribute evaluation algorithm for multiple asynchronous subtree replacements applicable to arbitrary noncircular attribute grammars. Our algorithm supports multiple independent editing cursors. Concurrent evaluations processes proceed independently as long as they cover disjoint regions of the derivation tree. Evaluation processes are merged when they overlap, to prevent unnecessary attribute evaluations. The algorithm ensures that when evaluation terminates, the tree is consistently attributed. Our results fill two open problems in the original algorithm for asynchronous subtree replacements reported by Kaplan and Kaiser.

[697]

Josephine Micallef and Gail E. Kaiser. Support algorithms for incremental attribute evaluation of asynchronous subtree replacements. In IEEE Transactions on Software Engineering, volume 19 of 3, pages 231-252. March 1993.

[699]

Josephine Micallef, Yael J. Cycowicz, and Gail E. Kaiser. Merging scheduling graphs during incremental attribute evaluation of asynchronous subtree replacements. Technical Report CUCS-450-89, Department of Comp. Sc., Columbia University, New York, July 1989.

[700]

Josephine Micallef. Incremental evaluation of ordered attribute grammars for asynchronous subtree replacements. Technical Report CUCS-380-88, Department of Comp. Sc., Columbia University, New York, July 1988.

[701]

Josephine Micallef. Incremental attribute evaluation with applications to multi-user language-based environments. Technical Report CUCS-444-89, Department of Comp. Sc., Columbia University, New York, April 1989.

[702]

Josephine Micallef. Incremental attribute evaluation for multi-user semantics-based editors. Ph.d. thesis, Computer Science, Columbia University, 1991.

This thesis addresses two fundamental problems associated with performing incremental attribute evaluation in multi-user editors based on the attribute grammar formalism: (1) multiple asynchronous modifications of the attributed derivation tree, and (2) segmentation of the tree into separate modular units. Solutions to these problems make it possible to construct semantics-based editors for use by teams of programmers developing or maintaining large software systems. Multi-user semantics-based editors improve software productivity by reducing communication costs and snafus. The objectives of an incremental attribute evaluation algorithm for multiple asynchronous changes are that (a) all attributes of the derivation tree have correct values when evaluation terminates, and (b) the cost of evaluating attributes necessary to reestablish a correctly attributed derivation tree is minimized. We present a family of algorithms that differ in how they balance the tradeoff between algorithm efficiency and expressiveness of the attribute grammar. This is important because multi-user editors seem a practical basis for many areas of computer-supported cooperative work, not just programming. Different application areas may have distinct definitions of efficiency, and may impose different requirements on the expressiveness of the attribute grammar. The characteristics of the application domain can then be used to select the most efficient strategy for each particular editor. To address the second problem, we define an extension of classical attribute grammars that allows the specification of interface consistency checking for programs composed of many modules. Classical attribute grammars can specify the static semantics of monolithic programs or modules, but not inter-module semantics; the latter was done in the past using @i[ad hoc] techniques. Extended attribute grammars support programming-in-the-large constructs found in real programming languages, including textual inclusion, multiple kinds of modular units and nested modular units. We discuss attribute evaluation in the context of programming-in-the-large, particularly the separation of concerns between the local evaluator for each modular unit and the global evaluator that propagates attribute flows across module boundaries. The result is a uniform approach to formal specification of both intra-module and inter-module static semantic properties, with the ability to use attribute evaluation algorithms to carry out a complete static semantic analysis of a multi-module program.

[724]

Arvind M. Murching and Y. N. Srikant. Incremental attribute evaluation through recursive procedures. Comput. Lang., 14(4):225-237, 1989.

[726]

Kannan Muthukkaruppan. Spine: A synthesizer for practical incremental evaluators. Technical Report UCB//CSD-94-81, California Berkeley, May 1994.

SPINE is a system for efficiently generating practical incremental evaluators based on recursive procedures for the Strongly Non-Circular class of attribute grammars. Several interactive language-based software development environments use incremental evaluation of attribute grammars for context-sensitive static semantic analysis. Ease of evaluator construction, effective consumption of space, applicability to a large class of AGs, ability to handle multiple site attribute tree transformations and close to optimal performance are the key advantages this system offers over other existing incremental AG systems. SPINE has been used innovatively in the Ensemble software environment to provide advanced incremental formatting of documents. As part of this work, an AG-description language, ASPEC, was developed to serve as the presentation (layout) specification tool for Ensemble documents. The ASPEC language provides several powerful default mechanisms that make presentation specifications very concise

[749]

Robert L. Nord and Frank Pfenning. The ergo attribute system. In Peter Henderson, editor, ACM SIGSOFT/SIGPLAN Symp. on Practical Software Development Environments, pages 110-120. ACM press, Boston, MA, November 1988. Joint issue with ACM SIGPLAN Notices 24, 2 (February 1989)Published as SIGSOFT Software Eng. Notes, volume 13, number 5.

The Ergo Attribute System was designed to satisfy the requirements for attributes in a language-generic program derivation environment. It consists of three components: an abstract data type of attributes that guarantees attribute consistency; a Common Lisp implementation which combines demand-driven and incremental attribute evaluation in a novel way while allowing for attribute persistence over many generations of a program; and an attribute-grammar compiler producing code based on this abstract data type from a high-level specification. Experience with three major applications (one being the attribute-grammar compiler itself) confirms that the overhead in storing and accessing attributes incurred by the implementation scheme is more than offset by the gains from the demand-driven, incremental, and persistent nature of attribution.

[754]

Matthias Olk. Generierung eines effizienten Attributschedulers für ein baumtransformierendes System. Diploma thesis, FB 10 -- Informatik, University des Saarlandes, Saarbrücken, 1986.

[795]

Didier Parigot. Mise en oe uvre des grammaires attribuées: transformation, évaluation incrémentale, optimisations. thèse de 3ème cycle, University de Paris-Sud, Orsay, September 1987.

[796]

Didier Parigot. Transformations, Évaluation Incrémentale et Optimisations des Grammaires Attribués: Le Système FNC-2. PhD thesis, Université de Paris-Sud, Orsay, 1988.

[803]

Stephen B. Peckham. Globally partitionable attribute grammars. In Pierre Deransart and Martin Jourdan, editors, Attribute Grammars and their Applications (WAGA), volume 461 of Lecture Notes in Computer Science, pages 327-342. Springer-Verlag, New York-Heidelberg-Berlin, September 1990. Paris.

[804]

Stephen B. Peckham. Incremental attribute evaluation and multiple subtree replacements. Technical Report TR90-1093, Department of Comp. Sc., Cornell University, Ithaca, NY, February 1990.

The standard model for incremental attribute evaluation allows single subtree replacements followed by attribute reevaluation to restore consistency to a derivation tree. This thesis advocates an extended model that allows multiple subtree replacements. A static (tree-walking) algorithm for performing incremental updating after such changes is developed. The algorithm cannot be used with all attribute grammars, but is restricted to grammars contained in the new class of ``globally partitionable attributer grammars'' (GPAGs). A test for determining whether an attribute grammar is GPAG is described. The multiple subtree replacement algorithm (GPAG-evaluate) in this thesis improves on two shortcomings of existing algorithms. First, many evaluators have a running time that depends linearly on the size of the derivation tree of on the number of concurrent subtree replacements. GPAG-evaluate has a running time of O(log n cdot |AFFECTED|), where n is the number of nodes in the derivation tree and AFFECTED is the set of attributes needing reevaluation. Second, experience with incremental, attribute grammar-based environments demonstrates that dynamic evaluators are noticeably slower than static evaluators because they require time-consuming data structure manipulations. Most existing algorithms for multiple subtree replacements are dynamic, but GPAG-evaluate is static. A second problem treated in this thesis is asynchronous subtree replacements, that is, allowing changes to be made while propagation continues after previous changes. A method for analyzing the efficiency of asynchronous subtree replacement algorithms is presented. An asynchronous evaluator (ASYNCH-evaluate) is described that, like GPAG-evaluate, guarantees that no attributes will be evaluated unnecessarily. Under some restrictions, ASYNCH-evaluate is as efficient as GPAG-evaluate. In particular, propagation in trees containing dynamically generated, nonlocal dependency edges can be supported. Both GPAG-evaluate and ASYNCH-evaluate must find lowest common ancestors of nodes in a tree where subtree replacements were made. A simple technique performs this operation in time O(n). To make the evaluators more efficient, this thesis describes an algorithm that uses self-adjusting binary trees to perform the necessary operations in amortized O(log n) time. These operations are not restricted to attributed derivation trees, but can be used for any application using trees.

[812]

M. Pennings, D. Swierstra, and H. Vogt. Using cached functions and constructors for incremental attribute evaluation. In M. Bruynooghe and M. Wirsing, editors, Proceedings of the 4th International Symposium of Programming Language Implementation and Logic Programming, Leuven, BE: PLILP '92, pages 130-144, Berlin, DE, 1992. Springer-Verlag.

A technique is presented for the efficient incremental evaluation of attribute grammars. Through its generality, the applied approach may be affective too in the evaluation of higher order attribute grammars. The authors' approach is an extension of a simpler algorithm for incremental evaluation, where functions, corresponding to visit sequences, are cached. Consequently, attributes are either found in the cache or they are recomputed, so there is no longer need to represent the attributed tree explicitly. One may share common subtrees, avoiding repeated attribute evaluation, thus solving a typical HAG problem. The authors propose the following change: instead of explicitly representing the tree and calling visit sequence functions to compute the attributes, the tree is represented through a set of visit functions corresponding to the successive visits. These functions are constructed using the visit sequences as building blocks. This technique has two major advantages. Firstly, a visit function characterizes precisely that part of the tree that would actually have been visited in the previous approach, thus increasing the number of cache hits. Secondly, copyrules may be removed during the construction phase. This results in shortcircuiting copychains and in minimizing the number of recomputed functions.

[813]

Maarten C. Pennings. Generating incremental attribute evaluators. Ph.D. thesis, Computer Science, Utrecht University, November 1994.

[818]

Mary Pfreundschuh-Wagner and Ray Ford. Using attribute grammars to control incremental, concurrent builds of modular systems. In Jürgen F. H. Winkler, editor, Intl. Workshop on Software Version and Configuration Control, pages 285-304, Stuttgart, January 1988. B. G. Teubner.

[830]

William W. Pugh. Incremental computation and the incremental evaluation of functional programs. Technical Report CORNELLCS//TR88-936, Cornell University, Computer Science Department, August 1988.

Incremental computation is generally thought of as the technique of efficiently updating the result of a computation when the input is changed. This idea is used in doing semantic checking in programming environments, document formatting in WYSIWYG editors and other applications. More generally, incremental computation is the technique of efficiently applying a function to a series of similar inputs. Much of the previous work on incremental computation has centered on incremental attribute grammar and incremental dependency graph evaluation schemes, but these techniques are only suitable for certain applications. This thesis examines an alternative method for providing incremental computation. Our results provide practical methods that can be used for applications such as theorem provers for which attribute grammars are unusable. Even for those problems for which attribute grammars are best suited, our methods perform almost as well as attribute grammars. We describe an incremental evaluator for functional programs that makes use of function caching. Function caching, or memoising, allows reuse of solutions to problems that were solved previously. We examine how function caching can be effectively used when solving problems that are similar to problems that were solved previously. In order for function caching to provide incremental evaluation, two similar problems must be solved by decomposing them into sub-problems in such a way that they share many common sub-problems. We formalize and quantify this idea with the notion of a stable decomposition, and we present data structures for representing sets and sequences that have stable decompositions. We solve several problems related to the efficient implementation of function caching. To perform function caching efficiently, one must be able to determine if two values are equal in constant time and perform updates applicatively. The data structures we present for sets and sequences support these features. This was previously an open problem for representations that also supported efficient updates. We also examine how to calculate hash keys and perform fast equality tests for S-expressions and how to determine what to purge from a function cache when it is full. We report benchmarks that show our function caching implementation produces significant speed-ups in complex programs such as incremental theorem provers.

[861]

Thomas Reps, Tim Teitelbaum, and Alan Demers. Incremental context-dependent analysis for language-based editors. ACM Trans. Progr. Languages and Systems, 5(3):449-477, July 1983.

[862]

Thomas Reps, Carla Marceau, and Tim Teitelbaum. Remote attribute updating for language-based editors. In 13th ACM Symp. on Principles of Progr. Languages, pages 1-13. ACM press, St Petersburg Beach, FL, January 1986.

A major drawback to the use of attribute grammars in language-based editors has been that attributes can only depend on neighboring attributes in a program's syntax tree. This paper concerns new attribute-grammar-based methods that, for a suitable class of grammars, overcome this fundamental limitation. The techniques presented allow the updating algorithm to skip over arbitrarily large sections of the tree than more straightforward updating methods visit node by node. These techniques are then extended to deal with aggregate values, so that the attribute updating procedure need only follow dependencies due to a changed component of an aggregate value. Although our methods work only for a restricted class of attribute grammars, satisfying the necessary restrictions should not place an undue burden on the writer of the grammar.

[863]

Thomas Reps. Optimal-time incremental semantic analysis for syntax-directed editors. In 9th ACM Symp. on Principles of Progr. Languages, pages 169-176. ACM press, Albuquerque, NM, January 1982.

Attribute grammars permit the specification of static semantics in an applicative and modular fashion, and thus are a good basis for syntax directed editors. Such editors represent programs as attributed trees, which are modified by operations such as sub-tree pruning and grafting. After each modification, a subset of attributes, AFFECTED, requires new values. Membership in AFFECTED is not known a priori; this paper presents an algorithm that identifies attributes in AFFECTED and computes their new values. The algorithm is time-optimal, its cost is proportional to the size of AFFECTED.

[865]

Thomas Reps. Generating language-based environments. Reprint of PhD thesis, report TR 82-514, Department of Comp. Sc., Cornell University, Ithaca, NY (August 1982)., MIT Press, Cambridge, MA, 1984.

This thesis concerns the design of interactive, language-based programming environments that use knowledge of a programming language to provide functions based on the structure and meaning of programs. The goal of the research is a system-constructor to enable editors for different languages to be created easily. The most challenging aspect of such a system is the design of the semantic component, because a language-based editor performs static semantic analysis when a program is altered in order to detect erroneous constructions or to prevent illegal modifications. For efficiency, this should be performed incrementally, re-using as much old information as possible; therefore, a major focus of my research concerns a model of editing for which it is possible to perform incremental semantic analysis efficiently. In this model, a program is represented as an attributed tree in which all attributes have consistent values; programs are modified by tree operations such as pruning, grafting, and deriving. After each modification, some of the attributes require new values; incremental semantic analysis is performed by updating attribute values to again make them all consistent. The thesis presents several algorithms for this process that are asymptotically optimal in time. The chief disadvantage of attribute grammars is that they use large amounts of storage. The thesis discusses three aspects of utilizing storage efficiently in such systems. One way to reduce the amount of storage used is to reduce the number of atttribute values retained at any stage of attribute evaluation. The thesis establishes two results concerning this idea: it presents one algorithm for evaluating an n-attribute tree that never saves more than O( sqrt n attribute values, and it presents a second algorithm that never saves more than O( log n) attribute values. A second method for reducing the amount of storage is to share the space used for storing attributes whose values are complex data structures; the thesis presents a very general method for such sharing that can be applied to attributes of many types. Finally, the thesis describes how, by restricting the class of attribute grammars, it is possible to reduce the amount of storage overhead required for updating trees in optimal time.

[866]

Thomas Reps. Incremental evaluation for attribute grammars with unrestricted movement between tree modifications. Acta Informatica, 25(2):155-178, 1988.

[892]

Christophe Roudet. Visualisation graphique incrémentale par évaluation d'attributs. Stage de DEA informatique de l'ESSI, UniversitéNICE, 1994. (Gzipped PostScript, 90 pages, 370190 bytes)

[899]

Barbara G. Ryder and M. D. Carroll. Incremental data flow analysis via attributes. report LCSR-TR-93, Department of Comp. Sc., Rutgers University, New Brunswick, NJ, June 1987.

[914]

Masataka Sassa. Incremental attribute evaluation and parsing based on ECLR-attributed grammars. report A-1988-9, Department of Comp. Sc., University of Helsinki, March 1988. Also published as: Technical Report ISE-TR-88-66, Institute of Information Sciences. An International Journal and Electronics, University of Tsukuba (March 1988).

[946]

Stephen K. Skedzeleski. Definition and Use of Attribute Reevaluation in Attributed Grammars. Ph.D. thesis, Comp. Sc. Department, University of Wisconsin-Madison, October 1978.

[962]

S. Doaitse Swierstra and Harald H. Vogt. Higher Order Attribute Grammars. In Alblas and Melichar [9], pages 256-296. Prague.

Higher Order Attribute Grammars (HAGs) are an extension of normal attribute grammars in the sense that the distinction between the domain of parse-trees and the domain of attributes has disappeared: parse trees may be computed in attributes and grafted to the parse tree at various places. As a result semantic functions may be described by attribute evaluation. We will present the basic definition for HAGs, and compare them with attribute coupled grammars, extended affix grammars and functional programming languages. We will indicate how multi-pass compilers and a compiler for supercombinators can be described this way. It will be shown that, especially in the case of incremental evaluation, the conventional execution model has to be generalised. Such a model, based on function caching, hash-consing and combinator construction will be discussed. This model encompasses many of the more ad-hoc optimisations one finds in standard implementations of normal attribute grammars.

[988]

Michael D. Tiemann. ICC: an incremental compiler compiler based on attribute evaluation. Technical Report PP-412-86, Microelectronic and Computer Technology Corporation, Austin, TX, December 1986.

[992]

Heiner Tittelbach. Effiziente Attributspeicherverwaltung für ein baumtransformierendes System. Diploma thesis, FB 10 -- Informatik, University des Saarlandes, Saarbrücken, 1986.

[1011]

E. A. van der Meulen. Incremental Rewriting. PhD thesis, University of Amsterdam, 1994.

[1022]

Harald H. Vogt, S. Doaitse Swierstra, and Matthijs F. Kuiper. On the efficient incremental evaluation of higher order attribute grammars. report RUU-CS-90-36, Utrecht University, December 1990.

[1026]

Scott A. Vorthmann. Syntax-directed editor support for incremental consistency maintenance. Technical Report GIT-CC-90-03, Georgia Institute of Technology. College of Computing.

Consistency maintenance is dependency-directed recompilation of a multi-component software system during development or maintenance. Incremental consistency maintenance requires an interactive setting, and a finer granularity of dependencies and processing than is possible with batch compilation technology. The technology of syntax-directed editors offers characteristics which are ideally suited to the task of incremental consistency maintenance. In particular, the use of attribute grammars to provide static semantic analysis has several specific advantages, including a fine granularity of dependencies and processing, and algorithms that update an attributed tree with a minimal amount of processing. However, several shortcomings of this approach have been identified. The described research addresses these shortcomings with extensions to the technology of syntax-directed editor generation. The principal extension is the addition of specific support for naming semantics in an SDE generator system. This support takes the form of a naming specification language (NSL), which extends the existing syntax and AG description language, and a kernel naming layer (KNL), which is incorporated into the editor kernel architecture. NSL supports the designation of name declaration and reference sites, the designation of productions that embody scopes, and specification of visibility of names between related scopes. NSL is highlighted by its powerful mechanisms for describing various visibility features. The KNL augments the syntax tree structure with additional edges from identifier usage sites to declaration sites. These edges provide efficient communication of semantic information (attributes) from declarations to references. An algorithm for coordinating incremental attribute evaluation on the augmented AG substrate is presented. A second extension to SDE technology is the design of a set of mechanisms for controlling incremental attribute evaluation. The intention is to eliminate redundant computation that occurs during attribute evaluation at each step in a series of editing modifications. The mechanisms described combine to provide a variety of techniques for both automatic and user- directed control of incremental evaluation. The central mechanism is a latched attribute, whose evaluation is enabled or disabled depending on the value of an associated boolean latch expression.

[1027]

Scott A. Vorthmann. Coordinated incremental attribute evaluation on a DR-threaded tree. In Pierre Deransart and Martin Jourdan, editors, Attribute Grammars and their Applications (WAGA), volume 461 of Lecture Notes in Computer Science, pages 207-221. Springer-Verlag, New York-Heidelberg-Berlin, September 1990. Paris.

[1031]

Mary Pfreundschuh Wagner and Ray Ford. Using attribute grammars to control incremental, concurrent builds of modular systems. In Proceedings of the International Workshop on Software Version and Configuration Control, pages 285-304, Grassau, Germany, January 1988.

[1034]

Janet A. Walz and Gregory F. Johnson. Incremental evaluation for a general class of circular attribute grammars. In ACM SIGPLAN '88 Conf. on Progr. Languages Design and Implementation, pages 209-221. ACM press, Atlanta, GA, July 1988. Published as ACM SIGPLAN Notices, volume 23, number 7.

[1035]

Janet A. Walz and Gregory F. Johnson. Inductive attribute grammars: A basis for incremental program execution. Acta Informatica, 32(2):117-144, 1995.

[1036]

Janet A. Walz. Extending Attribute Grammar and Type Inference Algorithms. Ph.D. thesis, Cornell University, February 1989.

Gated attribute grammars and error-tolerant unification expand upon the usual views of attribute grammars and unification. Normally, attribute grammars are constrained to be noncircular; gated attribute grammars allow fairly general circularities. Most unification algorithms do not behave well when given inconsistent input; the new unification paradigm proposed here not only tolerates inconsistencies but extracts information from them. The expanded views prove to be useful in interactive language-based programming environments. Generalized unification allows the environment to help the user find the sources of type errors in a program, while gated attribute grammars allow the environment to provide an interpreter for incremental reevaluation of programs after small changes to the code. The defining feature of gated attribute grammars is the appearance of a gate attribute (indicating where cycle evaluation should begin and end) within every cycle. Attributes are ordered by collapsing strongly connected components in the dependency graph and topologically sorting the result. The smaller dependency graph for each component (ignoring edges leading to the gate) can be recursively collapsed to provide further ordering. use of the evaluation order defined in this manner allows gated attribute grammars to do without the restrictions on functions within a component needed by the other varieties of circular attribute grammars. Initial and incremental evaluation algorithms are given, as well as a sample grammar allowing an editor for a small language to become an incremental interpreter. Counting unification defines unique solutions to sets of input equations that contain conflicting type information. These solutions are derived from the potential variable constraints implied by the input equations. For each type variable, each branch (a portion of a constraint) is assigned a weight indicating the number of times the input set implied such a constraint. When the input equations are derived from the static analysis of a program, the relative branch weights for a conflicting variable give the overall pattern of uses of that variable and can direct attention to parts of the program that disagree with the majority of uses. A number of error-tolerant unification algorithms are presented.

[1074]

Dashing Yeh and Uwe Kastens. Improvements of an incremental evaluation algorithm for ordered attributed grammars. ACM SIGPLAN Notices, 23(12):45-50, December 1988.

[1075]

Dashing Yeh. On incremental evaluation of ordered attributed grammars. BIT, 23:308-320, 1983.

[1082]

Bradley T. Vander Zanden. Incremental constraint satisfaction and its application to graphical interfaces. Technical Report CORNELLCS//TR88-941, Cornell University, Computer Science Department, October 1988.

Software that emphasizes pictures, rather than text, has become increasingly popular since the introduction of the Macintosh computer. Creating this software is a time-consuming task that can take months or years. Researchers have attempted to speed up this process by developing constraint-based tools that automate portions of the software development cycle. However, these tools are often limited in the types of applications they can generate, since 1) they lack powerful editing models that can manipulate complex data structures, such as lists, trees, and sets; and 2) in large applications, they cannot perform constraint satisfaction quickly enough to provide instantaneous feedback to the user. We present tools for overcoming each of these difficulties. First, we describe a new model, called constraint grammars, that integrates aspects of both attribute grammars and constraint-based, object systems to produce a powerful specification language for graphical interfaces. Constraint grammars integrate important concepts such as the part-whole hierarchy, almost-hierarchical structures, and multidirectional constraints. These features are augmented with a pattern-matching editing model that permits a designer to manipulate complex data structures. We then present techniques for incrementally resatisfying multidirectional, noncircular sets of constraints. It is shown that minimizing the number of re-solved constraints is NP-complete. We therefore describe an approach that attempts to minimize the amount of time spent updating the constraint solution. This technique divides constraint solving into two phases-a planning phase that linearly orders the constraints and an evaluation phase that solves the constraints using this linear order. Previous approaches have thrown away the linear order whenever the constraint system changes. However, this is unnecessary since only a local portion of the linear order is typically modified. We exploit this fact to develop an algorithm that incrementally updates this order. We the augment this algorithm with a heuristic that attempts to choose a linear order that minimizes the number of equations that the evaluation stage must solve. We present benchmarks that show that these algorithms can significantly reduce the number of equations examined by the planning phase and the number of equations solved by the evaluation phase.

[1083]

Alan K. Zaring. Parallel Evaluation in Attribute Grammar-based Systems. Ph.D. thesis, Department of Comp. Sc., Cornell University, August 1990.

Attributed context-free grammars provide a rigorous basis for the semantic analysis and translation of tree-structured objects and have been used to build a variety of systems. A number of programming language compiler, compiler generators, and language-based editor generators employing attribute grammars have been described in the literature. Many of these systems make use of l-ordered attribute grammars, attribute grammars for which particularly efficient methods for attributing derivation trees have been described. Derivation trees representing constructs of only moderate size may contain thousands of nodes and tens of thousands of attribute instances, and attribution of such trees on uniprocessor systems may require a significant amount of time. One possibility for reducing this time is to find techniques that exploit opportunities for parallelism in the attribution process and allow attribution to be performed on multiprocessor systems. Such techniques would permit attribute grammars to serve as a rigorous foundation for the development of parallel compilation systems and other parallel applications. We present several methods for the parallel attribution of trees derived from l-ordered attribute grammars. These methods take advantage of parallelism implicit in the attribution process and, thus, do not require any special considerations to be taken when constructing grammars. Methods appropriate for use on tightly - and loosely-coupled multiprocessor architectures and for use when complete and incremental tree attribution are required are presented. We present preliminary performance results obtained from implementations of some of the methods on a simple shared-memory multiprocessor simulator embedded within an attribute grammar-based editor generator system. The results suggest that the methods may provide useful reductions in attribution time in some cases.