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

Question

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

Answer 1

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

Answer 2

То, как я это вижу:

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

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

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

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

Answer 3

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

Например, Microsoft & # 8217; s .NET Балансировочная группа < ? код> (& л; <код> имя1 <код> - <код> имя2 <код > > & # 8230;) :

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

Это действительно соответствует языку L & # 8320; & # 8321; = { & # 949; , 01, 0011, 000111, & # 8230; }. Но этот язык не является регулярным в соответствии с леммой прокачки .