ABSTRACT 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
Cite this paper
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.
 M. Sipser, “Theory of Computation,” 3rd Edition, Course Technology, 2012.
 M. Bojańczyk and T. Colcombet, “Tree-Walking Automata Cannot Be Determinized,” Theoretical Computer Science, Vol. 350, No. 2-3, 2006, pp. 164-170.
 H. Comon, M. Dauchet, R. Gilleron, C. Loding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi, “Tree Automata Techniques and Applications,” 2007.
 H. Comon, M. Dauchet, R. Gilleron, C. Loding, F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi, “Tree Automata Techniques and Applications II,” 2007.
 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
 J. Power, “Notes on Formal Language Theory and Parsing,” National University of Ireland, Maynooth, Kildare, 2002.
 I. Bagrak and O. Shivers, “trx: Regular-Tree Expressions, Now in Scheme,” Scheme Workshop, September 2004.
 F. Yu, et al., “Symbolic String Verification,” SPIN’08 Proceedings of the 15th International Workshop on Model Checking Software, pp. 306-324.
 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.
 L. Segoufin and V. Vianu, “Validating Streaming XML Documents,” ACM, 2002, pp. 53-64.