Commenced in January 2007
Paper Count: 31103
Dynamic Attribute Dependencies in Relational Attribute Grammars
Abstract:Considering the theory of attribute grammars, we use logical formulas instead of traditional functional semantic rules. Following the decoration of a derivation tree, a suitable algorithm should maintain the consistency of the formulas together with the evaluation of the attributes. This may be a Prolog-like resolution, but this paper examines a somewhat different strategy, based on production specialization, local consistency and propagation: given a derivation tree, it is interactively decorated, i.e. incrementally checked and evaluated. The non-directed dependencies are dynamically directed during attribute evaluation.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1054835Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1175
 D.E. Knuth, "Semantics of context-free languages," Math. Systems Theory, vol. 2, no. 2, pp. 127-145, 1968. Correction in Math. Systems Theory, vol. 5, no. 1, pp. 95-96, 1971.
 A. V. Aho, M. Lam, R. Sethi & J.D. Ullman, "Compilers: principles, techniques, and tools," Addison Wesley, 2007.
 H. Alblas, and B. Melichar (eds), Attribute Grammars, Applications and Systems. Lecture Notes in Computer Science 545, Prague, Springer- Verlag, June 1991.
 P. Deransart, M. Jourdan, and B. Lorho, Attribute Grammars: Definitions, Systems and Bibliography. Lecture Notes in Computer Science, vol. 323, New York: Spinger-Verlag, 1988.
 P. Deransart, and M. Jourdan, Attribute Grammars and their Applications. Lecture Notes in Computer Science, vol. 461, Paris: Springer-Verlag, 1990.
 J. Engelfriet, Attribute grammars, Attribute evaluation methods. Methods and Tools for Complier Construction, Ed. B. Lorho, New York: Cambridge University Press, 1984, pp. 103-138.
 M. Jazayeri, W.F. Ogden, and W.C. Rounds, "The intrinsically exponential complexity of the circularity problem for attribute grammars," Communications of the ACM, vol. 18, no. 12, pp. 697-706, Dec. 1975.
 M. Jazayeri, "A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars," Journal of the ACM, vol. 28, no. 4, pp. 715-720, Oct. 1981.
 J.M. Dill, "A Counterexample for A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars," Journal of the ACM, vol. 36, no. 1, pp. 92-96, Jan. 1989.
 B. Courcelle, Attribute grammars: Definitions, analysis of dependencies, proof methods. Methods and Tools for Compiler Construction, New York: Cambridge University Press, 1984, pp. 81- 102.
 D. Parigot, G. Roussel, M. Jourdan, and E. Duris, Dynamic attribute grammars. Tech. Rep. 2881, INRIA, Rocquencourt, France, 1996.
 Y. Kikuchi, and T. Katayama, "On generalization of attribute grammars," Systems and computers in Japan, vol. 27, no 9, pp. 33-42, 1996.
 F. Neven, "Attribute grammars for unranked trees as a query language for structured documents," Journal of Computer and System Sciences, vol. 70, no. 2, pp. 221-257, March 2005.
 B. Courcelle, and P. Deransart, "Proofs of partial correctness for attribute grammars with application to recursive procedures and logic programming," Information and computation, vol. 78, no. 1, pp. 1-55, July 1988.
 P. Deransart, and J.A. Maluszynski, A grammatical View of Logic Programming. MIT Press, Nov. 1993.
 J. Paakki, "Attribute grammar paradigms-a high-level methodology in language implementation," ACM Computing Surveys (CSUR), vol. 27, no. 2, pp. 196-255, June 1995.
 L. Barford, and B.T. Vander Zanden, Attribute grammars in constraintbased graphics systems. Tech. Rep. TR87- 838: Department of Computer Science, Cornell University, Ithaca, New York, 1987.
 J. Steele, The Definition and Implementation of a programming Language Based on Constraint. PhD thesis: MIT Artificial Intelligence Laboratory, 1980.
 B.T. Vander Zanden, Incremental Constraint Satisfaction and its Application to Graphical Interfaces, Tech. Rep. TR88-941: Department of Computer Science, Cornell University, Ithaca, New York, October 1988.
 J. Maluszynski, Attribute Grammars and Logic Programs: A Comparison of Concepts. Eds. H. Albas and B. Melichar, Attribute Grammars, Applications and Systems, Lecture Notes in Computer Science 545, Springer-Verlag, 1991, pp. 330-357.
 D. Batory, "Feature Models, Grammars and Propositional Formulae," in Proc. of the 9th Software Product line Conference (SPLC 2005), Springer LNCS 3714, 2005, pp. 7-20.
 T. Isakowitz, Can we transform logic programs into attribute grammars? Stern School of Business, New York University, 1991, http://archive.nyu.edu/bitstream/2451/14362/1/IS-91-06.pdf.
 M. Ruffolo, and M. Manna, "A Logic-Based Approach to Semantic Information Extraction," in Proc. of the 8th International Conference on Enterprise Information Systems (ICEIS-06), 2007, pp. 70-84.
 R. Hoover, Incremental Graph Evaluation. PhD thesis: Department of Computer Science, Cornell University, Ithaca, New York, 1987.
 S.E. Hudson, "Incremental attribute evaluation: A flexible algorithm for lazy update," ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 13, no. 3, pp. 315-341, July 1991.
 T. Reps, T. Teitelbaum, and A. Demers, "Incremental context-dependent analysis for language based editors," ACM Transactions on Programming Languages and Systems, vol. 5, no.3, pp. 449-477, July 1983.
 P. Deransart, Validation des grammaires d-attributs. PhD thesis: Université de Bordeaux I, 1984.
 K. Barbar, and K. Musumbu, "Implementation of interpretation algorithm by means of attribute grammars," in Proc. of the 26th Southeastern Symposium on system Theory, IEEE Computer Society, 1994, pp. 87-93.
 M.M. Corsini, K. Musumbu, A. Rauzy, and B. Le Charlier, Efficient bottom-up abstract interpretation of logic programs by means of constraint solving over symbolic finite domains. Tech. Rep: Institute of Computer Science, University of Namur, Belgium, 1993.
 K. Marriott, H. Sondergaard, and N.D. Jones, "Denotational abstract interpretation of logic programs," ACM Transactions on Programming Languages and Systems, vol. 16, no. 3, pp. 607-648, May 1994.