Pattern Matching Based on Regular Tree Grammars

Authors: Riad S. Jabri

Abstract:

Pattern matching based on regular tree grammars have been widely used in many areas of computer science. In this paper, we propose a pattern matcher within the framework of code generation, based on a generic and a formalized approach. According to this approach, parsers for regular tree grammars are adapted to a general pattern matching solution, rather than adapting the pattern matching according to their parsing behavior. Hence, we first formalize the construction of the pattern matches respective to input trees drawn from a regular tree grammar in a form of the so-called match trees. Then, we adopt a recently developed generic parser and tightly couple its parsing behavior with such construction. In addition to its generality, the resulting pattern matcher is characterized by its soundness and efficient implementation. This is demonstrated by the proposed theory and by the derived algorithms for its implementation. A comparison with similar and well-known approaches, such as the ones based on tree automata and LR parsers, has shown that our pattern matcher can be applied to a broader class of grammars, and achieves better approximation of pattern matches in one pass. Furthermore, its use as a machine code selector is characterized by a minimized overhead, due to the balanced distribution of the cost computations into static ones, during parser generation time, and into dynamic ones, during parsing time.

Keywords: Bottom-up automata, Code selection, Pattern matching, Regular tree grammars, Match trees.

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

References:

[1] Shankar P., Ganttati A., Yuvraj A.R. and Madhaven M. (2000), A new algorithm for linear tree pattern matching, Theoretical Computer Science, 242, 125-142.
[2] Ferdenand C., Seidi H., and Wilhelm R. (1994), Tree automata for code selection. Acta nformatica , 31(80):741-760.
[3] Cleophas L., Hemerik K. and Zwaan C. (2006), Two related algorithms for root-to frontier tree pattern matching, International Journal of Foun-dation of Computer Science, 17(6),1235-1272.
[4] Borchardt B., Code selection by tree series transducers (2005), LNCS, 3317, 57-67.
[5] Glanville R. S.,. Graham S.L. (1978), A new method for compiler code generation, Proc.of the fifth Ann. ACM Symp. On Principles of Programming Languages, 231-240.
[6] Nymeyer A., Katoen J.P. (1997), Code generation based on formal BURS theory and heuristic search. Acta Infomatica , 34(8),597-635.
[7] Fraser C.W., Henry R.R. and Proebsting T.A. (1992), BURG-fast optimal instruction selection and tree parsing, ACM SIGPLAN Notices 27(4), 68-76.
[8] Llopart P. and Graham E. (1988), Optimal code generation for expression trees: An application of BURS theory. Proc. Of the Fifteen Ann. ACM symp. On Principles of Programming Languages , 294-308.
[9] Proebsting T.A. (1995), BURS automata generation, ACM Trans. On Prog. Lang. and Sys.3(17), 461-486.
[10] Hoffmanand C.M. and O'Donnell M.J. (1982), Pattern matching in trees, Journal of the ACM, 29(1),68-95
[11] Ahoand A.V. and Corasick M.J. (1975), Efficient string matching: an aid to bibliographic search, Communications of the ACM, 18, 333-340.
[12] Katoen J.-P., Nymeyer A. (2000), Pattern- matching algorithm based on terms rewriting systems, Theoretical Computer Science,238(1-20, 439¬464.
[13] Boulytchev D. (2007) Burs-based instruction set selection, LNCS, 4378,431-437.
[14] Bravenboer M. and Visser E. (2002), Rewriting strategies for Instruction selection, LNCS, 2378, 237-251.
[15] Visser E. ( 2001), Stratego: A language for program transformation based on rewriting strategies, LNCS, 2051 , 357-361.
[16] Rety P., Vuotto J. ( 2005), Tree automata for rewrite strategies, Journal of Symbolic Computation ,40 , 749-794.
[17] Ertl M.A., Casey K and Gregg D. (2006), Fast and flexible instruction selection with on —demand tree-parsing automata, In PLDI'06, Ottawa, Canada , 52-59.
[18] Madhaven M. et al. (2000), Techniques for Optimal Code Generation, ACM Transaction on Programming Languages and Systems , 22(6),972-1000.
[19] Aho A.V., Lam M., Sethi R. and Ullman J.D. (2007), Compilers Principles, Techniques, &Tools, Second edition, Addison Wesely.