Czy wyrażenia regularne są językiem programowania?

Czy w sensie akademickim wyrażenia regularne kwalifikują się jako język programowania?

Motywacją mojej ciekawości jest SO pytanie , na które właśnie spojrzałem, które zadało pytanie „czy regex do X?” i zastanawiałem się, co można powiedzieć w sensie ogólnym na temat możliwych rozwiązań, które je wykorzystują.

_{Pytam w zasadzie: „czy wyrażenia regularne Turing są kompletne”?}

Wyrażenia regularne są szczególnym rodzajem gramatyki formalnej używanej do analizowania ciągów znaków i innych informacji tekstowych, które w formalnej teorii języków są znane jako „języki regularne”. Nie są one językiem programowania jako takim. Są one raczej skrótem do kodowania, które w przeciwnym razie byłoby niezwykle żmudne do wdrożenia i nawet bardziej zagmatwane niż niekiedy tajemny Regex.

Języki programowania są zazwyczaj definiowane jako języki, które są ukończone przez Turinga . Takie języki muszą być zdolne do przetwarzania dowolnej funkcji obliczeniowej . Regex nie pasuje do tej kategorii.

Jeśli chcesz język, który wygląda jak Regex, spróbuj J.

Trudno jest odpowiedzieć na pytania typu „jest X Y ”, jeśli uczestnicy ruchu debata różnych definicji X i Y . Możliwe, że w przypadku niektórych definicji odpowiedź brzmi „tak”, a w przypadku niektórych definicji odpowiedź brzmi „nie”. Zwłaszcza jeśli odpowiedź zależy od szczegółów technicznych, w których różne definicje są różne. Również ta dyskusja zawiera pewne dezinformacje, więc prosimy o cierpliwość przy dłuższej odpowiedzi.

Co rozumiemy przez „ język programowania ”?

Prostą odpowiedzią może być „język używany do tworzenia programów”. Jasne, ale: jakie programy? Co powiesz na język, który może być użyty do tworzenia niektórych rodzajów programów, ale nie innych rodzajów programów? Oto dwa konkretne przykłady ilustrujące skrajne przypadki:

1) Wyimaginowany język o nazwie M działa w następujący sposób: Jeśli program zawiera pojedynczą literę „m”, tworzy grę Saper. Cała reszta to błąd składniowy.

Intuicyjnie nie to rozumiemy przez „język programowania”. Ale dział marketingu M może argumentować, że technicznie spełnia definicję, ponieważ można go użyć do stworzenia programu. Jasne, kompilator robi dla ciebie pewne krytyczne części, ale to właśnie robią kompilatory, prawda? Kompilator języka C tłumaczy również kilka prostych słów na dziesiątki instrukcji procesora. Kompilator M idzie jeszcze dalej i jeszcze bardziej upraszcza pracę.

2) Jeśli zainstalujesz oryginalną wersję słynnego Turbo Pascal, możesz pisać wiele rodzajów programów. Nie można jednak napisać gry, która działa w przeglądarce internetowej, ponieważ niezbędnego interfejsu API po prostu nie ma.

Więc co dokładnie sprawia, że ​​Turbo Pascal jest językiem programowania, ale M go nie ma? Krótko mówiąc, możesz zrobić więcej w Pascalu niż w M. Ale wyobraź sobie, że mamy M.NET, który tworzy grę Saper w przeglądarce internetowej. Więc teraz mamy coś, co Pascal może zrobić, a M.NET nie, ale mamy też coś, co M.NET może zrobić, a Pascal nie. Dlaczego powinniśmy uważać zalety Pascala za ważne, a zalety M.NET nie mają znaczenia?

Odpowiedź jest taka, że ​​możesz pisać wszelkiego rodzaju algorytmy w Pascal, ale nie możesz pisać algorytmów w M lub M.NET. Jasne, M kompiluje twoje polecenie „m”, a C kompiluje twoje polecenie „strcmp”. Ale możesz umieścić „strcmp” w większym kontekście, na przykład porównać dwa pliki wiersz po wierszu lub odczytać tysiące ciągów i posortować je alfabetycznie lub… cóż, miliony innych rzeczy. I właśnie ta umiejętność korzystania z danych poleceń w dowolnym algorytmie stanowi istotę języka programowania.

Czym dokładnie jest algorytm, a co ważniejsze, czym jest „dowolny algorytm”? W informatyce używamy słów Turing-complete . Chodzi o to, że istnieje zestaw języków komputerowych, w których każdy z nich jest w stanie zasymulować wszystkie z nich. Jednym z tych języków jest maszyna Turinga, dlatego tak się je nazywa. Jest tam Pascal, jest C, jest Java, jest Python, jest Lisp, jest Smalltalk, jest nawet XSLT. Nasz hipotetyczny M i M.NET są nie istnieje. Możesz dowiedzieć się o tym więcej na dowolnym uniwersytecie, oferując porządny kurs informatyki, ale chodzi o to, że język kompletny Turinga może zrobić wszystkoco może zrobić inny język Turinga, pod warunkiem, że zapewnisz im minimum niezbędnego API. (Jeśli przekażesz Pascalowi interfejs API przeglądarki internetowej, możesz tworzyć wszelkiego rodzaju gry w przeglądarce internetowej. Jeśli przekażesz interfejs API przeglądarki internetowej M, nadal możesz utworzyć Saper). Możemy powiedzieć metaforycznie, że jeśli usuwasz wszystkie interfejsy API z języka programowania, ważne jest to, co pozostaje.

Co rozumiemy przez „ wyrażenia regularne ”?

Różne języki programowania wdrażają je nieco inaczej. Ale oryginalny pomysł polegał na tym, że wyrażenia regularne wyrażają tak zwane języki regularne . Zauważ, że nie mówimy tutaj o językach programowania, ale o (pseudo-) językach ludzkich. Wyobraź sobie, że znajdujesz jakieś egzotyczne plemię mówiące językiem składającym się wyłącznie ze słów „ba”, „baba”, „bababa” i tak dalej. Możesz opisać ten język werbalnie jako „sylabę„ ba ”powtarzaną jeden lub więcej razy” lub używając wyrażenia regularnego jako „(ba) +”.

Wyrażenia regularne powinny wyrażać: „nic”, „ta litera”, „to, po którym następuje”, „to lub tamto”, „to, powtarzane jeden lub więcej razy”, i „nie to”. - To jest definicja matematyczna . Wszystko inne to tylko wygodny skrót zbudowany z poprzednich komponentów. Na przykład „to, powtórzono dwa lub trzy razy” można przetłumaczyć jako „to, a następnie to, a następnie (to lub nic)”, ale wygodniej byłoby napisać „ba {2,3}” niż „baba (ba)? ”.

W prawdziwym życiu typowa implementacja „wyrażeń regularnych” implementuje więcej niż to. Na przykład, używając definicji matematycznej, języka „aba”, „aabaa”, „aaabaaa” itd. - dowolna liczba „a”, po których następuje „b”, a po nim ta sama liczba „a” „s - nie jest zwykłym językiem. Jednak wiele „wyrażeń regularnych” używanych dzisiaj może je wykryć, wykorzystując dodatkową koncepcję „tego samego, co znaleźliśmy wcześniej”, zapisaną jako „(a +) b \ 1”. Korzystając z tej dodatkowej koncepcji, możemy robić fajne rzeczy, na przykład wykrywać słowa składające się z pierwszej liczby liter. Mimo to nie możemy wykonać żadnego algorytmu ... dla wyjaśnienia, dlaczego,

Wracając do pierwotnego tematu: czy wyrażenia regularne (zdefiniowane albo jako: wyrażenia opisujące języki regularne w hierarchii Chomsky'ego, czy jako: poprzednie, plus operacja \ 1) są językiem programowania (zdefiniowanym jako: Turing-complete)? Odpowiedź brzmi nie . Nie, nie możesz zaimplementować żadnego algorytmu za pomocą wyrażeń regularnych, a możliwość zaimplementowania dowolnego algorytmu jest tym, co ludzie studiujący informatykę zazwyczaj rozumieją jako esencję języka programowania.

Oczywiście każdy może zmienić odpowiedź, nalegając na inną definicję . Jak napisałem na początku, szczegóły techniczne są tutaj ważne. Jeśli źle je zrozumiesz, otrzymasz złą odpowiedź.

A jeśli nie zainteresowani szczegółami technicznymi, odpowiedź może być: można używać wyrażeń regularnych (i nic innego), aby program? Nie. Dlaczego więc nazywać to językiem programowania? (Jednak taka odpowiedź została tutaj pobrana i usunięta, dlatego napisałem tę dłuższą wersję).

EDYCJA: Ponadto każdy może stworzyć bibliotekę implementującą swój nowy wariant „wyrażeń regularnych” z kilkoma dodanymi nowymi funkcjami. W pewnym momencie nowe funkcje mogą wystarczyć, aby cały system stał się kompletny w Turingu. Trywialnym przykładem byłoby osadzenie języka pełnego Turinga przy użyciu nowej składni; ale może się to zdarzyć mniej oczywiste. Może to już się stało.

W .Net Regex może nie tylko obsługiwać różne formy warunkowe, wykorzystując różne kombinacje naprzemienności i wyglądu, ale może także manipulować własnym stosem.

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

Jest to na przykład mały fragment, który napisałem w celu pobrania tabeli HTML. W przeciwieństwie do innych silników wyrażeń regularnych, kontroluje stos kolekcji przechwytywania (push, peek i pop) i może obsługiwać zagnieżdżone obiekty. Mam bardziej skomplikowany, ale jest trochę zastrzeżony.

Myślę, że w tym przykładzie Regex można uznać za mający wszystkie podstawowe wymagania dotyczące języka programowania. Ma zmienne, pamięć wbudowaną, warunki warunkowe, dane wejściowe i wyjściowe, kompiluje przy użyciu jednego z wielu silników kompilacji wyrażeń regularnych (w tym przypadku .Net).

W odpowiedzi na zbyt często piskliwe pisanie w celu (NIGDY) analizowania kodu HTML za pomocą Regex, poszedłem naprzód i opublikowałem wcześniej wpisaną odpowiedź, którą mogę opublikować: Analizowanie HTML

Przykład Anoter (tylko demonstracja) jest następujący:

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

Ponownie, dla papug HTML: Analiza HTML

To pokazuje prostsze wykonywanie pętli regularnych i warunkowych (algorytmy?). Brakuje tylko faktycznego obliczenia matematycznego. Jest to bardziej szczegółowe wyrażenie regularne, które po prostu wyciąga komórkę TD bardziej skutecznie niż typowa metoda „(. *?)”.

Ale nawet jako entuzjasta Regex i samozwańczy mistrz, nie chciałbym mówić nikomu, że Regex jest językiem programowania. Mój własny argument przeciwko mnie jest taki, że nie może być samodzielny, musi być uruchamiany przez własny silnik, a jednocześnie obsługiwany przez inny silnik języka programowania.

Chociaż jeden element znajdujący / zamieniający w wyrażeniu regularnym nie jest językiem programowania pełnego Turinga, jak wyjaśniono w poprzednich odpowiedziach, jeśli zezwolisz na stosowanie powtarzających się czynności zastępowania wyrażeniami regularnymi, to tak, możesz zakodować dowolną maszynę Turinga za pomocą wyrażenia regularnego:

Powtarzane wyszukiwanie / zamienianie na wyrażenia regularne jest kompletnym językiem programowania Turinga

W rezultacie możesz obliczyć dowolną funkcję obliczalną za pomocą tego samego wyszukiwania i wielokrotnie zastępować wyrażenia regularne javascript.

Aby udowodnić kompletność Turinga, wystarczy zakodować maszynę Turinga w wyszukiwaniu / zamianie wyrażeń regularnych. Załóżmy, że stan edytora to:

0000#12345:01-5:0#0000000

które można odczytać jako taśmę symboli z czytnikiem:

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

Dla reguły odczytującej 0 w stanie 5, piszącej 1 i zmieniającej jej stan na 3 i przechodzącej w lewo, wyodrębniamy ją za pomocą następującego zapisu:

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

Kodujemy poprzednią notację w wyszukiwanym wyrażeniu regularnym:

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

i jego wyrażenie zastępcze (podobne do javascript)

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

Ok, teraz jak zakodować wiele reguł? Używamy konkatenacji z oroperatorem |do wyszukiwania wyrażeń regularnych i łączymy wyniki w zastępowaniu, numerowaniu grup grup z przesunięciami. Rozważmy na przykład zestaw czterech reguł.

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

Kodujemy je w wyszukiwaniu i zastępujemy wyrażenie:

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

Wypróbuj w swoim ulubionym silniku 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)
}