Abstract
Pattern matching in trees is fundamental to a variety of programming language systems. However, progress has been slow in satisfying a pressing need for general purpose pattern matching algorithms that are efficient in both time and space. We offer asymptotic improvements in both time and space to Chase's bottom-up algorithm for pattern preprocessing. Our preprocessing algorithm has the additional advantage of being incremental with respect to pattern additions and deletions. We show how to modify our algorithm using a new decomposition method to obtain a space/time tradeoff. Finally, we trade a log factor in time for a linear space bottom-up pattern matching algorithm that handles a wide subclass of Hoffmann and O'Donnell's Simple Patterns.
1. Part of this work was done while Paige was a summer faculty at IBM T. J. watson Research Center. This work is also partly based on research supported by the Office of Naval Research under Contract No. N00014-87-0461
2. Research at Princeton University partially supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, grant NSF-STC88-09648, and the Office of Naval Research, contract N00014-87-K-0467
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, A., Hopcroft, J., and Ullman, J., Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
Borstler, J., Moncke, U., and Wilhelm, R., Table Compression for Tree Automata, Lehrstuhl fur Informatik III, Universitat des Saarlandes, 1987.
Burghardt, J., “A Tree Pattern Matching Algorithm with Reasonable Space Requirements,” in Proc. CAAP '88, ed. M. Daudet and M. Nivat, Lecture Notes in Computer Science, vol. 299, pp. 1–15, Springer-Verlag, 1988.
Cai, J. and Paige, R., “The RAPTS Transformational System — A Proposal For Demonstration,” in ESOP '90 Systems Exhibition, May 1990.
Chase, D., “An improvement to bottom-up tree pattern matching,” in Proc. Fourteenth Annual ACM Symposium on Principles of Programming Languages, pp. 168–177, January, 1987.
Donzeau-Gouge, V., Huet, G., Kahn, G., and Lang, B., “Programming environments based on structured Editors: the Mentor Experience,” in Interactive Programming Environments, ed. D. Barstow, H. Shrobe, and E. Sandewall, McGraw-Hill, 1984.
Givler, J. and Kieburtz, R., “Schema Recognition for Program Transformations,” in ACM Symposium on LISP and Functional Programming, pp. 74–85, Aug, 1984.
Guibas, L. and Sedgewick, R., “A dichromatic framework for balanced trees,” in Proc. 19th IEEE FOCS, pp. 157–184, 1978.
Hatcher, P. and Christopher, T., “High-Quality Code Generation Via Bottom-Up Tree Pattern Matching,” in Proceedings 13th ACM Symposium on Principles of Programming Languages, pp. 119–130, Jan, 1986.
Hoffmann, C. and O'Donnell, J., “Pattern Matching in Trees,” JACM, vol. 29, no. 1, pp. 68–95, Jan, 1982.
Hoffmann, C. and O'Donnell, M., “Programming with Equations,” ACM TOPLAS, vol. 4, no. 1, pp. 83–112, Jan., 1982.
Hudak, P., “Conception, Evolution, and Application of Functional Programming Languages,” ACM Computing Survey, vol. 21, no. 3, pp. 359–411, Sep. 1989.
Huet, G. and Lang, B., “Proving and Applying Program Transformations Expressed with Second-Order Patterns,” Acta Informatica, vol. 11, pp. 31–55, 1978.
Knuth, D. and Bendix, P., “Simple Word Problems in Universal Algebras,” in Computational Problems in Abstract Algebra, ed. Leech, J., pp. 263–297, Pergamon Press, 1970.
Kosaraju, S., “Efficient Tree Pattern Matching,” in Proc. FOCS '89, Oct., 1989.
Maluszynski, J. and Komorowski, H. J., “Unification-free execution of logic programs,” IEEE Proceedings of symposium on logic programming, Boston, 1985.
Pelegri-Llopart, E. and Graham, S., “Optimal Code Generation for Expression Trees: An Application of BURS Theory,” in Proceedings 15th ACM Symposium on Principles of Programming Languages, pp. 294–308, Jan, 1988.
Pfenning, F. and Elliott, C., “Higher-Order Abstract Syntax,” in Proceedings SIGPLAN '88 Conf. on Prog. Lang. Design and Implementation, pp. 199–208, June, 1988.
Purdom, P. and Brown, C., “Fast Many-to-one Matching Algorithm,” in Proc. RTA '85, ed. J.-P. Jouannaud, Lecture Notes in Computer Science, vol. 202, pp. 407–416, Springer-Verlag, 1985.
Sarnak, N. and Tarjan, R., “Planar Point Location Using Persistent Search Trees,” CACM, vol. 29, no. 7, pp. 669–679, July, 1986.
Sethi, R., Programming Languages: Concepts and Constructs, Addison-Wesley, 1989.
Standish, T., Kibler, D., and Neighbors, J., “The Irvine Program Transformation Catalogue,” Univ. of Cal. at Irvine, Dept. of Information and Computer Science, Jan, 1976.
Tarjan, R., Data Structures and Network Algorithms, SIAM, 1984.
Van Emde Boas, P., “Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space,” IPL, vol. 6, pp. 80–82, 1977.
Willard, D., “Log-Logarithmic Worst-Case Range Queries are Possible in Space O(N),” IPL, vol. 17, pp. 81–89, 1983.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cai, J., Paige, R., Tarjan, R. (1990). More efficient bottom-up tree pattern matching. In: Arnold, A. (eds) CAAP '90. CAAP 1990. Lecture Notes in Computer Science, vol 431. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52590-4_41
Download citation
DOI: https://doi.org/10.1007/3-540-52590-4_41
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-52590-5
Online ISBN: 978-3-540-47042-7
eBook Packages: Springer Book Archive