Регулярные выражения не

36

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

Например, «регулярное выражение»

/^1?$|^(11+?)\1+$/

созданная известной личностью Perl Абигейл (и часть набора тестов Perl с 2002 года) описывает машину, которая принимает только составные унарные числа, но упражнение 4.5 (b) в третьем издании Питера Линца « Введение в формальные языки и автоматы » использует читателя насосное лемму доказать , что

Lзнак равно{aN:N яs NоT a пряме NUмбер}

это не обычный язык.

В тех случаях, когда различие важно, как мы должны называть строго более сильные выражения?

Грег Бэкон
источник

Ответы:

46

Ларри Уолл предложил использовать «регулярное выражение» для формализма, предложенного Клини, и «регулярное выражение» для выражений для широко используемых расширений. Это довольно широко соблюдаемое соглашение. Если вы хотите прояснить, что вы говорите о регулярных выражениях в смысле формальных языков, обычно нетрудно перевести их на разговоры о регулярных языках.

Сила регулярных выражений происходит от обратного отслеживания, и была проделана работа над автоматами для обычных языков с обратным отслеживанием. См., В частности, Becchi & Crowley, 2008, Расширение конечных автоматов для эффективного сопоставления Perl-совместимых регулярных выражений .

Чарльз Стюарт
источник
5
Я согласен, что-то вроде «Perl regex» («POSIX regex» и т. Д.) Против «обычного языка» должно быть достаточно ясным, чтобы предотвратить любую возможность неправильного толкования.
Юкка Суомела
В регулярных выражениях Perl гораздо больше дополнительных функций, чем просто возврат.
reinierpost
@reinierpost Верно, но я думаю, что возвращение назад является самым важным с точки зрения формальных языков. У регулярных выражений Perl есть такие функции, как выполнение произвольного кода Perl, но я думаю, что регулярные выражения следует интерпретировать свободно как охватывающие PCRE. PCRE содержат такие странности, как рекурсивные паттерны, но это темные искусства, уводящие вас далеко за пределы обычных языков. Я мог бы обновить свой ответ, чтобы покрыть их, хотя.
Чарльз Стюарт
18

Эти выражения были рассмотрены Ахо («Справочник по теоретической информатике», том А, глава 5) и Кампеану, Саломаа, Ю. («Формальное исследование практических регулярных выражений», Международный журнал основ компьютерных наук, 14: 1007 –1018, 2003), а также некоторые последующие документы.

Ахо называет более мощные выражения «rewbr» (регулярное выражение с обратными ссылками), Campeanu et al. используйте «расширенное регулярное выражение», а также «практическое регулярное выражение». Как представляется, «расширенное регулярное выражение» является термином, наиболее часто используемым в современной литературе.

Опираясь на термин «рациональное выражение» из французской школы и учитывая тот факт, что эти выражения используются в реальном мире, мне самому нравится «настоящее выражение».

Приложение: глава моей кандидатской диссертации посвящена этому классу формальных языков (соответствующая статья должна появиться на STACS 2011). При написании этой главы и статьи я экспериментировал с различными терминами. Наконец, я решил использовать расширенные регулярные выражения для модели с обратными ссылками и правильные регулярные выражения для хороших и нормальных регулярных выражений. Поскольку довольно неприятно менять терминологию в документе, который уже полностью (или в основном) написан, я думаю, что некоторые могут быть заинтересованы в опыте, который привел к моему выбору:

Во-первых, regex и rewbr на самом деле не скручивают язык, и их использование снова и снова в течение всей статьи стало действительно утомительным для написания и чтения, особенно при использовании любой из возможных форм множественного числа. Подобные PERL регулярные выражения также были довольно громоздкими. Конечно, я не являюсь носителем языка, поэтому YMMV.

Во-вторых, как только кто-то хочет поговорить об обеих моделях, удобно использовать термины, которые являются вариацией регулярного выражения , поскольку это позволяет подчеркивать сходство или различия по мере необходимости (например, «регулярное выражение, будь оно правильным или расширенный "). Кроме того, это позволяет легко подчеркнуть особый случай «расширенных регулярных выражений без обратных ссылок», когда речь идет об особых случаях во всем классе, вместо сравнения различных моделей.

В-третьих, я предпочел использовать термин, который уже используется в литературе, вместо вновь придуманного термина, который оставил мне выбор между расширенными регулярными выражениями и практическими регулярными выражениями . Второй выбор подразумевал (по крайней мере, неявно), что правильные регулярные выражения как-то непрактичны, что кажется довольно странным (тем более, что в RE2 от Google не используются обратные ссылки, и он выглядит довольно практичным).

Конечно, этот выбор - только мой «личный локальный максимум», и в зависимости от его потребностей, другие варианты могут быть более подходящими.

Доминик Д. Фрейденбергер
источник
7
К сожалению, термин расширенное регулярное выражение уже используется POSIX, который различает базовое регулярное выражение (BRE) и расширенное регулярное выражение (ERE) , оба из которых являются расширенными регулярными выражениями в соответствии с вашим определением.
Йорг Миттаг
@ Jörg: На самом деле согласно этому ни расширенные, ни базовые регулярные выражения POSIX не являются более мощными, чем регулярные регулярные выражения. И чистый (не GNU) BRE кажется менее мощным, чем регулярные выражения (без оператора чередования).
sepp2k
См. «О расширенных регулярных выражениях» Карла и Нарендрана (2009) для получения более свежих результатов об этом «rewbr»: portal.acm.org/citation.cfm?id=1533235
Jakob
Дальнейшие недавние результаты по этому языковому классу: «О пересечении языков регулярных выражений с регулярными языками» Кампеану и Сантеана (TCS 410, 2009) «Тест на совпадение полиномиального времени для больших классов расширенных регулярных выражений» Рейденбаха и Шмида (CIAA 2010 ) и «Расширенные регулярные выражения: краткость и решимость» (я должен появиться на STACS 2011).
Доминик Д. Фрейденбергер,
6

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

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

Посмотрите, например, на http://search.cpan.org/~asavige/Acme-EyeDrops-1.62/lib/Acme/EyeDrops.pm

Артур МИЛКИОР
источник
У вас есть несколько указателей?
Андрас Саламон
5
@ András: Я думаю, что Артур говорит о ?{CODE}директиве Perl , которая позволяет шаблонным выражениям чередовать программный код в регулярных выражениях. Я понимаю, что PCRE обычно определяют как «декларативную» часть языка, а весь язык называют языком шаблонов. Согласно WP, Aho, 1990, «Алгоритмы поиска шаблонов в строках» показывают, что проблема членства для обычных языков с возвратом назад является NP-полной. В декларативных PCRE нет других сложных функций.
Чарльз Стюарт
Я добавил ссылку; Я не смотрел на исходный код, поэтому я не знаю, как он работает, и есть ли доказательства того, что компиляция действительно правильная.
Артур МИЛЬЧИОР
1
Извините, но согласно вашему аргументу, поскольку лямбда-исчисление является полным по Тьюрингу, не было смысла искать его имя. То же самое для всех других формализмов и языков полного вычисления по Тьюрингу. Более того, полнота по Тьюрингу не описывает, насколько выразителен язык, поэтому нет смысла идентифицировать языки только потому, что они полны по Тьюрингу. Мой пример с лямбда-исчислением был, конечно, крайним.
Blaisorblade
2

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

Михаэль Кадилхак
источник
1
Не очень часто используется, ИМХО.
Blaisorblade
Он / широко используется в теории весовых автоматов, см. En.wikipedia.org/wiki/Rational_language . Я видел это довольно много раз в области языков, а не групп.
Микаэль Кадилхак
1

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

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

Blaisorblade
источник
0

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

Рафаэль
источник
2
В принципе, я согласен с вашей аргументацией, но Campeanu, Santean и Yu уже использовали термин « шаблонные выражения» для обозначения аналогичного класса языков с «более чистым» определением (см. «Выражения шаблонов и автоматы шаблонов», IPL 92 (2004 г.). )
Доминик Д. Фрейденбергер,