For a regex that support only +,?,*,.,|,[..],[^..],^,$,(..), a matcher that lets you match recursion: {<some-regex-name>} with length m, and a string of length n.
(the regex isn't supporting positive/negative look-ahead/behind)
What is the best complexity of the matcher?
Examples:
Bracket Matching:
brackets = (\({brackets}\))*
// brackets can match:
// ((()())())()
Some random "double" recursion:
a = \(({a}|{b})?\)
b = \[{a}(,{b})*\]
// a can match:
// (([(),[(),[()]][(())]]))
Json without whitespaces:
string = "([^\\"]|\\.)"
object = \{ ( {string}:{value}(,{string}:{value})* )? \}
number = [0-9]+(\.[0-9]*)?
list = \[({value}(,{value})*)?]
value = object|string|number|list|true|false
// value can match:
// {"key":false,"ab\"c":[false,12.3,[{}]]}
i have an idea how to implement this with complexity O(m^2*n^3) where n is the size of the string, and m is the size of the regex.
i haven't implement this yet, so maybe i have a mistake