Dynamic Attribute Dependencies in Relational Attribute Grammars
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:50384", author = "K. Barbar and M. Dehayni and A. Awada and M. Smaili", title = "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.", keywords = "Input/Output attribute grammars, local consistency,logical programming, propagation, relational attribute grammars.", volume = "4", number = "1", pages = "24-9", }
