regex - 递归正则表达式复杂度

Question

对于仅支持+, ?, *, ., |, [..], [^..], ^, $,的正则表达式(..)，可以匹配递归：{<some-regex-name>}使用 lengthm和字符串 length n。

（正则表达式不支持正/负前瞻/后视）

匹配器的最佳复杂度是多少？

例子：

支架匹配：

brackets = (\({brackets}\))*
// brackets can match:
// ((()())())()

一些随机的“双重”递归：

a = \(({a}|{b})?\)
b = \[{a}(,{b})*\]
// a can match:
// (([(),[(),[()]][(())]]))

没有空格的 Json：

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,[{}]]}

我有一个想法如何以复杂的方式实现这一点，字符串的大小在O(m^2*n^3)哪里，正则表达式的大小在哪里。我还没有实现这个，所以也许我有一个错误nm