Распознающая сила «современных» регулярных выражений

Какой класс языков действительно распознают настоящие современные регулярные выражения?

Всякий раз, когда есть группа захвата неограниченной длины с обратной ссылкой (например, (. *) _ \ 1 ), регулярное выражение теперь соответствует нерегулярному языку. Но одного этого недостаточно, чтобы сопоставить что-то вроде S :: = '(' S ')' | ε - контекстно-свободный язык сопоставления пар пар скобок.

Рекурсивные регулярные выражения (которые для меня новы, но я уверен, что существуют в Perl и PCRE), похоже, распознают по крайней мере большинство CFL.

Имеет кто-нибудь делал или читал какие-либо исследования в этой области? Каковы ограничения этих «современных» регулярных выражений? Признают ли они строго больше или строго меньше, чем CFG, грамматик LL или LR? Или существуют оба языка, которые можно распознать с помощью регулярного выражения, но не CFG и наоборот?

Ссылки на соответствующие статьи были бы очень благодарны.

82
задан ЯegDwight 14 August 2012 в 20:31
поделиться