Какой класс языков действительно распознают настоящие современные регулярные выражения?
Всякий раз, когда есть группа захвата неограниченной длины с обратной ссылкой (например, (. *) _ \ 1
), регулярное выражение теперь соответствует нерегулярному языку. Но одного этого недостаточно, чтобы сопоставить что-то вроде S :: = '(' S ')' | ε
- контекстно-свободный язык сопоставления пар пар скобок.
Рекурсивные регулярные выражения (которые для меня новы, но я уверен, что существуют в Perl и PCRE), похоже, распознают по крайней мере большинство CFL.
Имеет кто-нибудь делал или читал какие-либо исследования в этой области? Каковы ограничения этих «современных» регулярных выражений? Признают ли они строго больше или строго меньше, чем CFG, грамматик LL или LR? Или существуют оба языка, которые можно распознать с помощью регулярного выражения, но не CFG и наоборот?
Ссылки на соответствующие статьи были бы очень благодарны.