2014/05/22 by Martin Berglund, Frank Drewes, Brink van der Merwe
Computer Science · #cs.FL
paper · pdf · doi:10.4204/eptcs.151.7
published as EPTCS 151, 2014, pp. 109-123 · In Proceedings AFL 2014, arXiv:1405.5272
arxiv created 2014/05/22 · arxiv updated 2014/05/23
We develop a formal perspective on how regular expression matching works in Java, a popular representative of the category of regex-directed matching engines. In particular, we define an automata model which captures all the aspects needed to study such matching engines in a formal way. Based on this, we propose two types of static analysis, which take a regular expression and tell whether there exists a family of strings which makes Java-style matching run in exponential time.