@article{(Open Science Index):https://publications.waset.org/pdf/9947,
	  title     = {Pattern Matching Based on Regular Tree Grammars},
	  author    = {Riad S. Jabri},
	  country	= {},
	  institution	= {},
	  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.
},
	    journal   = {International Journal of Computer and Information Engineering},
	  volume    = {3},
	  number    = {4},
	  year      = {2009},
	  pages     = {1215 - 1224},
	  ee        = {https://publications.waset.org/pdf/9947},
	  url   	= {https://publications.waset.org/vol/28},
	  bibsource = {https://publications.waset.org/},
	  issn  	= {eISSN: 1307-6892},
	  publisher = {World Academy of Science, Engineering and Technology},
	  index 	= {Open Science Index 28, 2009},
	}