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

Ответ 1

Недавно я написал довольно длинную статью на эту тему: Истинная сила регулярных выражений.

Подводя итог:

• Регулярные выражения с поддержкой рекурсивных ссылок подшаблонов могут соответствовать всем контекстно-свободным языкам (например, a^n b^n).
• Регулярные выражения с утверждениями поиска и подшаблонными ссылками могут соответствовать хотя бы некоторым контекстно-зависимым языкам (например, ww и a^n b^n c^n).
• Если утверждения имеют неограниченную ширину (как вы говорите), то все контекстно-зависимые грамматики могут быть сопоставлены. Я не знаю никакого регулярного выражения, хотя у него нет ограничений фиксированной ширины на lookbehind (и в то же время поддерживает ссылки подшаблонов).
• Регулярные выражения с обратными ссылками являются NP-полными, поэтому любая другая проблема NP может быть решена с использованием регулярных выражений (после применения преобразования с полиномиальным временем).

Некоторые примеры:

• Соответствие контекстно-свободному языку {a^n b^n, n>0}:

  /^(a(?1)?b)$/
  # or
  /^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x
  

• Соответствие контекстно-зависимому языку {a^n b^n c^n, n>0}:

  /^
      (?=(a(?-1)?b)c)
      a+(b(?-1)?c)
  $/x
  # or
  /^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x
  

Ответ 2

Современные двигатели регулярных выражений, безусловно, могут анализировать более широкий набор языков, чем обычные языки. Так что, ни один из четырех классических наборов Хомского точно не распознается регулярными выражениями. Регулярные языки четко распознаются регулярными выражениями. Существуют некоторые классические контекстно-свободные языки, которые не могут быть распознаны регулярными выражениями, такими как сбалансированный язык скобок a^n b^n, если доступны обратные ссылки с подсчетом. Однако регулярное выражение может анализировать язык ww, который является контекстно-зависимым.

Собственно, регулярные выражения в теории формального языка лишь слегка связаны с регулярными выражениями. Соответствующие регулярные выражения с неограниченной обратной связью NP-Complete в самом общем случае, поэтому все алгоритмы сопоставления шаблонов для достаточно сильных регулярных выражений экспоненциальны, по крайней мере, в общем случае. Однако в большинстве случаев для большинства входных данных они довольно быстрые. Известно, что сопоставление контекстно-свободных языков не более чем быстрее, чем n^3, поэтому в регулярных выражениях есть некоторые языки, которые не являются контекстными (например, ww), но не все контекстно-свободные языки могут анализироваться с помощью регулярных выражений, Тип 0 языков не разрешимы вообще, сырые регулярные выражения не попадают туда.

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

Ответ 3

Вы можете читать о регулярных выражениях в Введение в язык и лингвистику  Ральф У. Фасолд, Джефф Коннор-Линтон, стр .477

Иерархия Хомского:

Type0 >= Type1 >= Type2 >= Type3

Вычислительная лингвистика в основном включает грамматики типа 2 и 3

• Введите 3 грамматики:

-Include регулярные выражения и автоматы с конечным состоянием (ака, машины с конечным состоянием)

- Фокусная точка остальной части этого разговора

• Тип 2 грамматики:

- Обычно используется для парсеров естественного языка

- используется для моделирования синтаксической структуры во многих лингвистических теориях (часто дополняется другими механизмами)

-Мы сыграем ключевой ролик в следующем разговоре о разборе.

большинство XML, таких как Microsoft DGML (Directed Mark Markup Language), который имеет взаимосвязанные ссылки, являются образцами, которые Regex бесполезны.

и эти три ответа могут быть полезны:

1 - does-lookaround-affect-which-languages-can-be-matched-by-regular-expressions

2 - regular-expressions-arent

3 - where-do-most-regex-implementations-fall-on-the-complexity-scale