An Automata-Based Approach to Pattern Matching
- 1 Pfeiffer University, Misenheimer, USA
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
- 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. doi:10.1016/j.tcs.2005.10.031
- 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.