Регулярные выражения - это язык программирования?

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

Мотивация для моего любопытства - это такой вопрос, который я только что посмотрел и который спросил: «Может ли регулярное выражение сделать X?» и это заставило меня задуматься о том, что можно сказать в общем смысле о возможных решениях с их использованием.

_{Я в основном спрашиваю: "Являются ли регулярные выражения Тьюринга завершенными?}

Регулярные выражения - это особый вид формальной грамматики, используемый для анализа строк и другой текстовой информации, которые в теории формальных языков известны как «Регулярные языки». Они не являются языком программирования как таковым. Они являются скорее сокращением для кодирования, которое в противном случае было бы чрезвычайно утомительным для реализации и даже более запутанным, чем иногда загадочно выглядящий Regex.

Языки программирования обычно определяются как языки, завершенные по Тьюрингу . Такие языки должны быть способны обрабатывать любую вычислимую функцию . Regex не вписывается в эту категорию.

Если вам нужен язык, похожий на Regex, попробуйте J.

Трудно ответить на вопросы типа «является X Y », если участники используют дебаты различных определений X и Y . Возможно, для некоторых определений ответ - «да», а для некоторых определений - «нет». Особенно, если ответ зависит от технических деталей, где разные определения отличаются. Также это обсуждение содержит некоторую дезинформацию, поэтому наберитесь терпения и дайте более длинный ответ.

Что мы подразумеваем под « языком программирования »?

Простым ответом может быть «язык, используемый для создания программ». Конечно, но: что за программы? А как насчет языка, который можно использовать для создания некоторых видов программ, но не других видов программ? Вот два конкретных примера, иллюстрирующих крайние случаи:

1) Мнимый язык под названием M работает следующим образом: если программа содержит одну букву «m», она создает игру «Сапер». Все остальное - синтаксическая ошибка.

Интуитивно, это не то, что мы имеем в виду, говоря «язык программирования». Но отдел маркетинга M может утверждать, что он технически соответствует определению, поскольку его можно использовать для создания программы. Конечно, компилятор делает некоторые важные части для вас, но это то, что делают компиляторы, не так ли? Компилятор языка C также переводит некоторые простые слова в десятки инструкций процессора. Компилятор M просто идет дальше и делает вашу работу еще проще.

2) Если вы устанавливаете оригинальную версию знаменитого Turbo Pascal, вы можете написать много разных программ. Но вы не можете написать игру, которая запускается в веб-браузере, потому что необходимого API просто нет.

Так что именно делает Turbo Pascal языком программирования, но у M его нет? Проще говоря, в Pascal вы можете сделать больше, чем в M. Но представьте, что у нас есть M.NET, которая создает игру Minesweeper, работающую в веб-браузере. Итак, теперь у нас есть кое-что, что может сделать Паскаль, а M.NET - нет, но у нас также есть кое-что, что может сделать М.NET, а Паскаль - нет. Почему мы должны считать преимущества Паскаля важными, а преимущества M.NET - несущественными?

Ответ в том, что вы можете писать все виды алгоритмов на Паскале, но вы не можете писать алгоритмы на M или M.NET. Конечно, M компилирует вашу команду «m», а C компилирует вашу команду «strcmp». Но вы можете поместить "strcmp" в более широкий контекст, например, сравнить два файла построчно, или прочитать тысячи строк и отсортировать их по алфавиту, или ... ну, миллионы других вещей. И именно эта способность использовать данные команды в любом алгоритме составляет суть языка программирования.

Что такое алгоритм, и что более важно, что такое «любой алгоритм»? В информатике мы используем слова полного по Тьюрингу . Идея состоит в том, что существует набор компьютерных языков, где каждый из них может имитировать все из них. Одним из таких языков является машина Тьюринга, поэтому их так и называют. Паскаль есть, C есть, Java есть, Python есть, Lisp есть, Smalltalk есть, даже XSLT есть. Наши гипотетические M и M.NET не существуют. Вы можете узнать об этом больше в любом университете, предлагающем достойный курс информатики, но идея в том, что полный по Тьюрингу язык может делать все что угодночто может сделать другой язык, полный Тьюринга, если вы предоставите им минимально необходимый API. (Если вы дадите какой-нибудь API веб-браузера для Pascal, вы сможете создавать все виды игр в веб-браузере. Если вы дадите API веб-браузера для M, вы все равно сможете создавать только Сапер.) Мы можем метафорически сказать, что если вы удаляете все API из языка программирования, важная вещь - это то, что остается.

Что мы подразумеваем под « регулярными выражениями »?

Различные языки программирования реализуют их немного по-разному. Но оригинальная идея состояла в том, что регулярные выражения выражают так называемые регулярные языки . Обратите внимание, что здесь мы говорим не о языках программирования, а о (псевдо) человеческих языках. Представьте, что вы обнаружите какое-то экзотическое племя, говорящее на языке, состоящем только из слов «ба», «баба», «бабаба» и так далее. Вы можете описать этот язык устно как «слог« ba », повторенный один или несколько раз» или используя регулярное выражение как «(ba) +».

Предполагается, что регулярные выражения выражают: «ничего», «это письмо», «это, затем то», «то или это», «это, повторяется один или несколько раз» и «не это». - Это математическое определение. Все остальное - это просто удобный ярлык, созданный из предыдущих компонентов. Например, «это, повторяется два или три раза» можно перевести как «это, затем следует, затем (это или ничего)», но было бы удобнее написать «ba {2,3}», чем «baba (ба)?».

В реальной жизни типичная реализация «регулярных выражений» реализует больше, чем это. Например, используя математическое определение, язык «aba», «aabaa», «aaabaaa» и т. Д. - любое число «a», за которым следует «b», за которым следует то же число «a» с - это не обычный язык. Однако многие «регулярные выражения», используемые сегодня, могут обнаружить это, используя дополнительную концепцию «того же, что мы нашли раньше», записанную как «(a +) b \ 1». Используя эту дополнительную концепцию, мы можем сделать несколько интересных вещей, например, обнаружить слова, состоящие из простого числа букв. Тем не менее, мы не можем сделать какой-либо алгоритм ... для объяснения, почему,

Итак, вернемся к исходной теме: являются ли регулярные выражения (определяемые как: выражения, описывающие обычные языки в иерархии Хомского, или как: первый плюс операция \ 1) языком программирования (определяемым как: полный по Тьюрингу)? Ответ - нет . Нет, вы не можете реализовать какой-либо алгоритм с использованием регулярных выражений, а возможность реализовать любой алгоритм - это то, что люди, изучающие информатику, обычно понимают как сущность языка программирования.

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

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

РЕДАКТИРОВАТЬ: Кроме того, любой может создать библиотеку, реализующую свой новый вариант «регулярных выражений» с некоторыми новыми функциями. В какой-то момент новых функций может быть достаточно для того, чтобы вся система стала завершенной по Тьюрингу. Тривиальным примером будет встраивание языка, полного по Тьюрингу, с использованием некоторого нового синтаксиса; но это также может произойти менее очевидно. Может быть, это уже случилось.

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

(?xm)
    (?>
        <(?<Tagname>table)[^>]*>
    )
(?(Tagname)
    (
        </(?(?!\k'Tagname')(?<-Tagname>))*\k'Tagname'>(?<-Tagname>)
    |
        (?>
            <(?<Tagname>[a-z][^\s>]*)[^>]*>
        )
    |
        [^<]+
    )+?
    (?(Tagname)(?!))
)

Это, например, небольшой фрагмент, который я написал для получения таблицы HTML. В отличие от других механизмов регулярных выражений, он управляет стеком коллекций захвата (push, peek и pop) и может обрабатывать вложенные объекты. У меня есть более сложный, но это своего рода собственность.

Я думаю, что в этом примере Regex можно рассматривать как имеющий все основные требования языка программирования. Он имеет переменные, встроенную память, условные выражения, ввод и вывод, он компилируется с использованием одного из нескольких механизмов компиляции регулярных выражений (в данном случае .Net).

В ответ на чрезмерно громкое кричание (НИКОГДА) парсинга HTML с помощью Regex я продолжил и опубликовал предварительно напечатанный ответ, который я могу опубликовать: парсинг HTML

Пример Anoter (просто демонстрация) следующий:

Function Regex("<(td>)((?:[^<]*(?(?!</\1)<))*)</\1")
    Group(0) = "<"
    Group(1) = "td>"
    Group(0) += Group(1)
    Group(2) = LoopMethod()
    Group(0) += Group(2)
    Group(0) += "</" & Group(1)
    Return Group()
End Function

Function LoopMethod()
    retGroup = ""
    Do
        tmpGroup = Everything that is NOT an Opening HTML Delimeter
        If the Text following tmpGroup Does NOT Equal "</" & Group(1) Then
            tmpGroup += "<"
            retGroup += tmpGroup
        Else
            Exit Do
        End If
    Loop
    Return retGroup
End Function

Опять же, для попугаев HTML: Разбор HTML

Это показывает более простое регулярное выражение, выполняющее циклы и условные выражения (алгоритмы?). Единственное, чего не хватает - это математических вычислений. Это более подробное регулярное выражение, которое просто использует TD-ячейку более эффективно, чем типичный метод (. *?).

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

Хотя один поиск / замена в регулярном выражении не является языком программирования, полным по Тьюрингу, как объяснялось в предыдущих ответах, если вы разрешаете использовать повторяющиеся действия по замене регулярными выражениями, тогда да, вы можете кодировать любую машину Тьюринга, используя регулярное выражение:

Повторный поиск / замена регулярными выражениями является языком программирования, полным по Тьюрингу

Как следствие, вы можете вычислить любую вычислимую функцию, используя один и тот же поиск, и заменять регулярное выражение javascript снова и снова.

Чтобы доказать полноту тьюринга, достаточно закодировать машину Тьюринга в поиске / замене регулярного выражения. Предположим, что состояние редактора:

0000#12345:01-5:0#0000000

который можно прочитать как ленту символов с читателем на нем:

[left symbols]#[set of states]:[set of symbols]-[current state]:[current symbol]#[right symbols]

Для правила, читающего 0 в состоянии 5, пишущего 1 и меняющего его состояние на 3 и перемещающего влево, мы абстрагируем его, используя следующую запись:

5:0 => 1, 3:[left]

Мы кодируем предыдущую запись в регулярное выражение поиска:

(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#

и его заменяющее выражение (подобное javascript)

#12345:01-$4:$1#$8

Хорошо, теперь, как закодировать много правил? Мы используем конкатенацию с orоператором |для поиска по регулярному выражению и объединяем результаты в замену, нумерацию номеров групп со смещениями. Например, давайте рассмотрим набор из четырех правил.

5:0 => 1, 3:left
3:0 => 1, 5:right
5:1 => 1, 5:right
3:1 => 1: 3:stop

Мы кодируем их в поиске и заменяем выражение:

Search:
(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#|#(1)(2)(3)(4)(5):(0)(1)-3:0#(\d)|#(1)(2)(3)(4)(5):(0)(1)-5:1#(\d)|#(1)(2)(3)(4)(5):(0)(1)-3:1#

Replace by:
$15$23#12345:01-$4$13$21$27:$1$16$24$31#$8

Попробуйте это в своем любимом движке JavaScript:

function turingstep(s) {
  return s.replace(/(\d)#(1)(2)(3)(4)(5):(0)(1)-5:0#|#(1)(2)(3)(4)(5):(0)(1)-3:0#(\d)|#(1)(2)(3)(4)(5):(0)(1)-5:1#(\d)|#(1)(2)(3)(4)(5):(0)(1)-3:1#/g,"$15$23#12345:01-$4$13$21$27:$1$16$24$31#$8");
}

var tape = "0000#12345:01-5:0#0000000"
for(var i = 0; i < 6; i++) {
  console.log(tape)
  tape = turingstep(tape)
}