Является ли "регулярное выражение" в современных языках программирования действительно "контекстно-зависимой грамматикой"?

Question

С годами сопоставление с образцом "regex" становится все более и более мощным, и я задаюсь вопросом: действительно ли это просто сопоставление по контексту и грамматике? Это вариация / расширение контекстно-свободного грамматического соответствия? Где это сейчас и почему бы нам просто не назвать это вместо старого, ограничительного «регулярного выражения»?

Answer 1

В частности, обратные ссылки на захват скобок делают регулярные выражения более сложными, чем регулярные, контекстно-свободные или контекстно-зависимые грамматики. Название просто исторически выросло (как много слов). См. Также этот раздел в Википедии и это объяснение с примером из Perl.

Answer 2

Как я это вижу:

• Обычные языки:
  • Подобрано по конечным автоматам. Только одна переменная может использоваться для представления текущего «местоположение» в грамматике для сопоставления: рекурсия не может быть реализована
• Контекстно-свободные языки:
  • Соответствует стековой машине. Текущее «местоположение» в грамматике представлено стеком в той или иной форме. Не может «вспомнить» ничего, что произошло до
• Контекстно-зависимые языки:
  • Большинство языков программирования
  • Все Большинство человеческих языков

Мне известны парсеры регулярных выражений, которые позволяют вам сравнивать то, с чем парсер уже сталкивался, достигая чего-то вроде контекстно-зависимой грамматики.

Тем не менее парсеры регулярных выражений, какими бы сложными они ни были, не допускают рекурсивного применения правил, что является определенным требованием для контекстно-свободных грамматик.

Термин regex , на мой взгляд, в основном относится к синтаксису , используемому для выражения этих регулярных грамматик (звездочек и вопросительных знаков).

Answer 3

В современных реализациях регулярных выражений есть функции, которые нарушают правила классического определения регулярных выражений .

Например Microsoft .NET Балансировочная группа (?<name1-name2> … ):

^(?:0(?<L>)|1(?<-L>))*(?(L)(?!))$

Это соответствует языку L ₀₁ = { ε , 01, 0011, 000111,…}. Но этот язык не является регулярным согласно Pumping Lemma .