×

A new algorithm for linear regular tree pattern matching. (English) Zbl 0944.68096

Summary: We consider the problem of linear regular tree pattern matching and describe a new solution based on a bottom up technique. Current bottom up techniques preprocess the patterns and construct a finite state tree pattern matching automaton for the purpose. Though matching time is linear in the size of the subject tree, the size of the automaton can be exponential in the sum of the sizes of all patterns. We show here that the problem can be cast as a parsing problem for a context free language, and a solution that uses an extension of the LR parsing technique can be devised. Though the size of the resulting pushdown automaton can be exponential in the pattern size in the worst case, there are problem instances for which exponential gains in succinctness of representation are obtained. The technique has been successfully applied to the problem of generation of an instruction selector in a compiler back end.

MSC:

68Q45 Formal languages and automata
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.V. Aho, M. Ganapathi, Efficient tree pattern matching: an aid to code generation, in: Proc. 12th ACM Symp. on Priciples of Programming Languages, 1985, pp. 334-340.; A.V. Aho, M. Ganapathi, Efficient tree pattern matching: an aid to code generation, in: Proc. 12th ACM Symp. on Priciples of Programming Languages, 1985, pp. 334-340.
[2] Balachandran, A.; Dhamdhere, D. M.; Biswas, S., Efficient retargetable code generation using bottom up tree pattern matching, Comput. Lang., 3, 15, 127-140 (1990)
[3] D. Chase, An improvement to bottom up tree pattern matching, in: Proc. 14th Ann. ACM Symp. on Principles of Programming Languages, 1987, pp. 168-177.; D. Chase, An improvement to bottom up tree pattern matching, in: Proc. 14th Ann. ACM Symp. on Principles of Programming Languages, 1987, pp. 168-177.
[4] M. Dubiner, Z. Galil, E. Magen, Faster tree pattern matching, in: Proc. 31st IEEE FOCS ’90, 1990.; M. Dubiner, Z. Galil, E. Magen, Faster tree pattern matching, in: Proc. 31st IEEE FOCS ’90, 1990. · Zbl 0806.68055
[5] Ferdinand, C.; Seidl, H.; Wilhelm, R., Tree automata for code selection, Acta Inform., 31, 741-760 (1994) · Zbl 0820.68031
[6] A. Gantait, A new algorithm for tree pattern matching and its application to retargetable code generation, M.E. Project Report, Department of Computer Science and Automation, Indian Institute of Science, Bangalore, December 1996.; A. Gantait, A new algorithm for tree pattern matching and its application to retargetable code generation, M.E. Project Report, Department of Computer Science and Automation, Indian Institute of Science, Bangalore, December 1996.
[7] R.S. Glanville, S.L. Graham, A new method for compiler code generation, in: Proc. 5th Ann. ACM Symp. on Principles of Programming Languages, 1978, pp. 231-240.; R.S. Glanville, S.L. Graham, A new method for compiler code generation, in: Proc. 5th Ann. ACM Symp. on Principles of Programming Languages, 1978, pp. 231-240.
[8] P.Hatcher, T. Christopher, High-quality code generation via bottom-up tree pattern matching, in: Proc. 13th ACM Symp. on Principles of Programming Languages, 1986, pp. 119-130.; P.Hatcher, T. Christopher, High-quality code generation via bottom-up tree pattern matching, in: Proc. 13th ACM Symp. on Principles of Programming Languages, 1986, pp. 119-130.
[9] Hoffmann, C.; O’Donnell, M. J., Pattern matching in trees, J. ACM, 29, 1, 68-95 (1982) · Zbl 0477.68067
[10] Hopcroft, J.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley, Reading: Addison-Wesley, Reading MA · Zbl 0426.68001
[11] Maya Madhavan, Optimal regular tree pattern matching using pushdown automata, MSc(Engineering) Thesis, Dept. of Computer Science and Automation. Indian Institute of Science, Bangalore, 1998.; Maya Madhavan, Optimal regular tree pattern matching using pushdown automata, MSc(Engineering) Thesis, Dept. of Computer Science and Automation. Indian Institute of Science, Bangalore, 1998.
[12] E. Pelegri Llopart, S. Graham, Optimal code generation for expression trees: An application of BURS theory, in: Proc. 15th Annual ACM Symp. on Principles of Programming Languages, 1988, pp. 294-308.; E. Pelegri Llopart, S. Graham, Optimal code generation for expression trees: An application of BURS theory, in: Proc. 15th Annual ACM Symp. on Principles of Programming Languages, 1988, pp. 294-308.
[13] S. Ravi Kumar, Retargettable code generation using bottom up tree pattern matching, M.E Project Report, Department of Computer Science and Automation, Indian Institute of Science, Bangalore, 1992.; S. Ravi Kumar, Retargettable code generation using bottom up tree pattern matching, M.E Project Report, Department of Computer Science and Automation, Indian Institute of Science, Bangalore, 1992.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.