Dynamic Attribute Dependencies in Relational Attribute Grammars

Authors: K. Barbar, M. Dehayni, A. Awada, M. Smaili

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.

Keywords: Input/Output attribute grammars, local consistency, logical programming, propagation, relational attribute grammars.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1054835

References:

[1] 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.
[2] A. V. Aho, M. Lam, R. Sethi & J.D. Ullman, "Compilers: principles, techniques, and tools," Addison Wesley, 2007.
[3] H. Alblas, and B. Melichar (eds), Attribute Grammars, Applications and Systems. Lecture Notes in Computer Science 545, Prague, Springer- Verlag, June 1991.
[4] 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.
[5] P. Deransart, and M. Jourdan, Attribute Grammars and their Applications. Lecture Notes in Computer Science, vol. 461, Paris: Springer-Verlag, 1990.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] D. Parigot, G. Roussel, M. Jourdan, and E. Duris, Dynamic attribute grammars. Tech. Rep. 2881, INRIA, Rocquencourt, France, 1996.
[12] Y. Kikuchi, and T. Katayama, "On generalization of attribute grammars," Systems and computers in Japan, vol. 27, no 9, pp. 33-42, 1996.
[13] 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.
[14] 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.
[15] P. Deransart, and J.A. Maluszynski, A grammatical View of Logic Programming. MIT Press, Nov. 1993.
[16] 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.
[17] 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.
[18] J. Steele, The Definition and Implementation of a programming Language Based on Constraint. PhD thesis: MIT Artificial Intelligence Laboratory, 1980.
[19] 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.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] R. Hoover, Incremental Graph Evaluation. PhD thesis: Department of Computer Science, Cornell University, Ithaca, New York, 1987.
[25] 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.
[26] 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.
[27] P. Deransart, Validation des grammaires d-attributs. PhD thesis: Université de Bordeaux I, 1984.
[28] 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.
[29] 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.
[30] 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.