An Automata-Based Approach to Pattern Matching

DOI: 10.4236/ica.2013.43036   PDF   HTML   XML   6,620 Downloads   7,804 Views  


Due to its importance in security, syntax analysis has found usage in many high-level programming languages. The Lisp language has its share of operations for evaluating regular expressions, but native parsing of Lisp code in this way is unsupported. Matching on lists requires a significantly more complicated model, with a different programmatic approach than that of string matching. This work presents a new automata-based approach centered on a set of functions and macros for identifying sequences of Lisp S-expressions using finite tree automata. The objective is to test that a given list is an element of a given tree language. We use a macro that takes a grammar and generates a function that reads off the leaves of a tree and tries to parse them as a string in a context-free language. The experimental results indicate that this approach is a viable tool for parsing Lisp lists and expressions in the abstract interpretation framework

Share and Cite:

A. Sever, "An Automata-Based Approach to Pattern Matching," Intelligent Control and Automation, Vol. 4 No. 3, 2013, pp. 309-312. doi: 10.4236/ica.2013.43036.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] M. Sipser, “Theory of Computation,” 3rd Edition, Course Technology, 2012.
[2] M. Bojańczyk and T. Colcombet, “Tree-Walking Automata Cannot Be Determinized,” Theoretical Computer Science, Vol. 350, No. 2-3, 2006, pp. 164-170. doi:10.1016/j.tcs.2005.10.031
[3] H. Comon, M. Dauchet, R. Gilleron, C. Loding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi, “Tree Automata Techniques and Applications,” 2007.
[4] H. Comon, M. Dauchet, R. Gilleron, C. Loding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi, “Tree Automata Techniques and Applications II,” 2007.
[5] C.-H. Chen, “A Neural Network Arhitecture for Syntax Analysis,” IEEE Transactions of Neural Networks, Vol. 10, No. 1, 1999, pp. 94-114. doi:10.1109/72.737497
[6] J. Power, “Notes on Formal Language Theory and Parsing,” National University of Ireland, Maynooth, Kildare, 2002.
[7] I. Bagrak and O. Shivers, “trx: Regular-Tree Expressions, Now in Scheme,” Scheme Workshop, September 2004.
[8] F. Yu, et al., “Symbolic String Verification,” SPIN’08 Proceedings of the 15th International Workshop on Model Checking Software, pp. 306-324.
[9] A. Bouajjani, B. Johnson, M. Nilsson and T. Touili, “Regular Model Checking,” Proceedings of the 12th International Conference on Computer Aided Verification, 2007, pp. 403-418.
[10] L. Segoufin and V. Vianu, “Validating Streaming XML Documents,” ACM, 2002, pp. 53-64.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.