Apakah ekspresi reguler merupakan bahasa pemrograman?

Dalam pengertian akademis, apakah ekspresi reguler memenuhi syarat sebagai bahasa pemrograman?

Motivasi untuk rasa ingin tahu saya adalah pertanyaan SO yang baru saja saya lihat yang bertanya "bisakah regex melakukan X?" dan itu membuat saya bertanya-tanya apa yang bisa dikatakan dalam arti umum tentang solusi yang mungkin menggunakannya.

_{Saya pada dasarnya bertanya, "Apakah ekspresi reguler Turing lengkap"?}

Ekspresi Reguler adalah jenis khusus tata bahasa formal yang digunakan untuk mengurai string dan informasi tekstual lainnya yang dikenal sebagai "Bahasa Reguler" dalam teori bahasa formal. Mereka bukan bahasa pemrograman seperti itu. Mereka lebih merupakan singkatan untuk pengkodean yang sebaliknya akan sangat membosankan untuk diimplementasikan dan bahkan lebih membingungkan daripada Regex yang terkadang terlihat misterius.

Bahasa Pemrograman biasanya didefinisikan sebagai bahasa yang Lengkap Turing . Bahasa tersebut harus dapat memproses fungsi yang dapat dihitung . Regex tidak masuk dalam kategori ini.

Jika Anda ingin bahasa yang mirip Regex, coba J.

Sulit untuk menjawab pertanyaan tipe "is X a Y ", jika peserta debat menggunakan definisi X dan Y yang berbeda . Bisa jadi untuk beberapa definisi, jawabannya adalah "ya", dan untuk beberapa definisi jawabannya adalah "tidak". Terutama jika jawabannya tergantung pada detail teknis di mana definisi yang berbeda berbeda. Diskusi ini juga mengandung beberapa informasi yang salah, jadi harap bersabar dengan jawaban yang lebih panjang.

Apa yang kita maksud dengan " bahasa pemrograman "?

Jawaban sederhana bisa berupa "bahasa yang digunakan untuk membuat program". Tentu, tapi: program apa? Bagaimana dengan bahasa yang dapat digunakan untuk membuat beberapa jenis program, tetapi bukan jenis program lainnya? Berikut adalah dua contoh spesifik untuk menggambarkan kasus-kasus ekstrem:

1) Bahasa imajiner yang disebut M bekerja seperti ini: Jika program ini berisi huruf tunggal "m", itu menciptakan permainan Minesweeper. Yang lainnya adalah kesalahan sintaksis.

Secara intuitif, ini bukan apa yang kita maksudkan dengan mengatakan "bahasa pemrograman". Tetapi departemen pemasaran M dapat berpendapat bahwa secara teknis memenuhi definisi, karena dapat digunakan untuk membuat program. Tentu, kompiler melakukan beberapa bagian penting untuk Anda, tetapi itulah yang dilakukan kompiler, bukan? Sebuah kompiler dari bahasa C juga menerjemahkan beberapa kata sederhana ke dalam lusinan instruksi prosesor. Kompiler M hanya melangkah lebih jauh dan membuat pekerjaan Anda lebih sederhana.

2) Jika Anda menginstal versi asli dari Turbo Pascal yang terkenal, Anda dapat menulis berbagai jenis program. Tetapi Anda tidak dapat menulis game yang berjalan di browser web, karena API yang diperlukan tidak ada di sana.

Jadi apa sebenarnya yang menjadikan Turbo Pascal sebagai bahasa pemrograman, tetapi M tidak memilikinya? Sederhananya, Anda dapat melakukan lebih banyak di Pascal daripada di M. Tapi bayangkan kita memiliki M.NET, yang membuat game Minesweeper berjalan di browser web. Jadi sekarang kami memiliki sesuatu yang bisa dilakukan Pascal dan M.NET tidak bisa, tetapi kami juga punya sesuatu yang bisa dilakukan M.NET dan Pascal tidak bisa. Mengapa kita harus menganggap keunggulan Pascal penting, dan keunggulan M.NET tidak relevan?

Jawabannya adalah Anda dapat menulis semua jenis algoritma dalam Pascal, tetapi Anda tidak dapat menulis algoritma dalam M atau M.NET. Tentu, M mengkompilasi perintah Anda "m", dan C mengkompilasi perintah Anda "strcmp". Tetapi Anda dapat menempatkan "strcmp" dalam konteks yang lebih besar, misalnya membandingkan dua file baris demi baris, atau membaca ribuan string dan mengurutkannya berdasarkan abjad, atau ... yah, jutaan hal lainnya. Dan justru kemampuan ini untuk menggunakan perintah yang diberikan dalam algoritma apa pun yang membuat esensi dari bahasa pemrograman.

Apa sebenarnya algoritma itu, dan yang lebih penting, apa itu "algoritma apa saja"? Dalam ilmu komputer kita menggunakan kata-kata Turing-lengkap . Idenya adalah bahwa ada satu set bahasa komputer, di mana masing-masing dari mereka mampu mensimulasikan semuanya. Salah satu bahasa itu adalah mesin Turing, itulah sebabnya mereka disebut seperti itu. Pascal ada di sana, C ada di sana, Jawa ada di sana, Python ada di sana, Lisp ada di sana, Smalltalk ada di sana, bahkan XSLT ada di sana. M dan M.NET hipotetis kami tidak ada. Anda dapat mempelajari ini lebih banyak di universitas mana saja yang menyediakan kursus ilmu komputer yang bagus, tetapi idenya adalah bahwa bahasa Turing-lengkap dapat melakukan apa sajabahwa bahasa Turing-complete lain dapat dilakukan, jika Anda memberi mereka API minimum yang diperlukan. (Jika Anda memberikan beberapa API peramban web ke Pascal, Anda dapat membuat semua jenis permainan di peramban web. Jika Anda memberikan API peramban web ke M, Anda masih hanya dapat membuat Minesweeper.) Kita dapat mengatakan secara metaforis bahwa jika Anda menghapus semua API dari bahasa pemrograman, yang penting adalah apa yang tersisa.

Apa yang kita maksud dengan " ekspresi reguler "?

Bahasa pemrograman yang berbeda menerapkannya sedikit berbeda. Tetapi ide awalnya adalah bahwa ekspresi reguler mengekspresikan apa yang disebut bahasa biasa . Perhatikan bahwa kita tidak berbicara tentang bahasa pemrograman di sini, tetapi tentang (pseudo-) bahasa manusia. Bayangkan bahwa Anda menemukan beberapa suku eksotis berbicara bahasa yang hanya terdiri dari kata "ba", "baba", "bababa" dan sebagainya. Anda bisa menggambarkan bahasa ini secara verbal sebagai "suku kata 'ba' yang diulang satu kali atau lebih" atau menggunakan ekspresi reguler sebagai "(ba) +".

Ekspresi reguler seharusnya menyatakan: "tidak ada", "surat ini", "ini, diikuti oleh itu", "ini atau itu", "ini, diulang satu atau lebih kali", dan "bukan ini". - Itulah definisi matematika . Yang lainnya hanyalah cara pintas yang nyaman dibangun dari komponen sebelumnya. Misalnya "ini, diulang dua atau tiga kali" dapat diterjemahkan sebagai "ini, diikuti oleh ini, diikuti oleh (ini atau tidak sama sekali)", tetapi bisa lebih mudah untuk menulis "ba {2,3}" daripada "baba (ba)? "

Dalam kehidupan nyata, implementasi khas "ekspresi reguler" menerapkan lebih dari ini. Misalnya, menggunakan definisi matematika, bahasa "aba", "aabaa", "aaabaaa" dan seterusnya - sejumlah "a", diikuti oleh "b", diikuti oleh jumlah yang sama "a" "s - bukan bahasa biasa. Namun, banyak "ekspresi reguler" yang digunakan saat ini dapat mendeteksinya, menggunakan konsep tambahan "hal yang sama yang kami temukan sebelumnya", ditulis sebagai "(a +) b \ 1". Menggunakan konsep tambahan ini, kita dapat melakukan beberapa hal keren, misalnya mendeteksi kata yang terdiri dari bilangan prima huruf. Namun, kami tidak dapat melakukan algoritma apa pun ... untuk penjelasan mengapa,

Jadi, kembali ke topik asli: apakah ekspresi reguler (didefinisikan sebagai: ekspresi yang menggambarkan bahasa reguler dalam hierarki Chomsky; atau sebagai: yang pertama, ditambah operasi \ 1) bahasa pemrograman (didefinisikan sebagai: Turing-complete)? Jawabannya adalah tidak . Tidak, Anda tidak dapat menerapkan algoritme apa pun dengan menggunakan ekspresi reguler, dan kemampuan untuk menerapkan algoritme apa pun yang dipahami oleh orang yang mempelajari ilmu komputer sebagai esensi bahasa pemrograman.

Tentu saja, siapa pun dapat mengubah jawabannya dengan menekankan definisi yang berbeda . Seperti yang saya tulis di awal, detail teknis penting di sini. Jika Anda salah, Anda mendapatkan jawaban yang salah.

Dan jika Anda tidak tertarik pada detail teknis, jawabannya bisa: Dapatkah Anda menggunakan ekspresi reguler (dan tidak ada yang lain) untuk membuat program? Tidak. Jadi mengapa menyebutnya bahasa pemrograman? (Namun, jawaban seperti ini telah diunduh dan dihapus di sini, itulah sebabnya saya menulis versi yang lebih panjang ini.)

EDIT: Juga, siapa pun dapat membuat perpustakaan yang menerapkan varian baru mereka "ekspresi reguler" dengan beberapa fitur baru yang ditambahkan. Pada suatu saat, fitur-fitur baru mungkin cukup untuk seluruh sistem menjadi Turing-lengkap. Contoh sepele akan menanamkan bahasa Turing-lengkap menggunakan beberapa sintaks baru; tetapi itu juga bisa terjadi kurang jelas. Mungkin itu sudah terjadi.

Di .Net, Regex tidak hanya dapat menangani berbagai bentuk kondisional, menggunakan kombinasi berbeda dari pergantian dan pencarian, tetapi juga dapat memanipulasi tumpukannya sendiri.

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

Sebagai contoh, ini adalah cuplikan kecil yang saya tulis untuk mengambil Tabel HTML. Tidak seperti mesin regex lainnya, ini mengontrol tumpukan koleksi tangkap (push, peek, dan pop), dan dapat menangani objek bersarang. Saya punya yang lebih kompleks, tapi agak eksklusif.

Saya pikir dalam contoh ini, Regex dapat dilihat memiliki semua persyaratan dasar bahasa pemrograman. Ini memiliki variabel, memori inline, kondisional, input dan output, yang dikompilasi menggunakan salah satu dari beberapa mesin kompilasi regex (.Net dalam hal ini).

Sebagai tanggapan terhadap squawking yang terlalu sering digunakan untuk (TIDAK PERNAH) Parse HTML dengan Regex, saya melanjutkan dan memposting tanggapan yang sudah diketik yang bisa saya posting: Parsing HTML

Contoh anoter (hanya demonstrasi) adalah sebagai berikut:

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

Sekali lagi, untuk HTML beo: Parsing HTML

Ini menunjukkan regex melakukan loop dan kondisional yang lebih sederhana (algoritma?). Satu-satunya hal yang hilang adalah perhitungan matematika aktual. Ini adalah Ekspresi Reguler yang lebih terperinci yang hanya menarik Sel TD lebih efisien daripada metode "(* *?)" Yang khas.

Tetapi bahkan sebagai penggemar Regex dan guru yang memproklamirkan diri, saya tidak akan pergi berkeliling memberi tahu siapa pun bahwa Regex adalah bahasa Pemrograman. Argumen saya sendiri terhadap diri saya adalah bahwa itu tidak bisa berdiri sendiri, itu harus dijalankan melalui mesin sendiri sambil didukung oleh mesin bahasa pemrograman lain.

Meskipun satu menemukan / mengganti dalam ekspresi reguler bukan bahasa pemrograman Turing-lengkap, seperti yang dijelaskan oleh jawaban sebelumnya, jika Anda mengizinkan untuk menggunakan tindakan berulang mengganti dengan ekspresi reguler, maka ya, Anda dapat menyandikan mesin Turing apa pun menggunakan ekspresi reguler:

Menemukan / Ganti berulang dengan ekspresi reguler adalah Bahasa Pemrograman Turing-complete

Sebagai konsekuensinya, Anda dapat menghitung fungsi yang dapat dihitung menggunakan pencarian yang sama dan mengganti ekspresi reguler javascript berulang-ulang.

Untuk membuktikan kelengkapan turing, cukup mengkodekan mesin Turing dalam pencarian / penggantian ekspresi reguler. Asumsikan bahwa kondisi editor adalah:

0000#12345:01-5:0#0000000

yang dapat dibaca sebagai rekaman simbol dengan pembaca di atasnya:

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

Untuk aturan yang membaca 0 di negara 5, menulis 1 dan mengubah negaranya menjadi 3 dan bergerak ke kiri, kami abstrak menggunakan notasi berikut:

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

Kami menyandikan notasi sebelumnya ke dalam ekspresi reguler pencarian:

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

dan ekspresi penggantinya (seperti javascript)

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

Oke, sekarang bagaimana cara menyandikan banyak aturan? Kami menggunakan penggabungan dengan oroperator |untuk pencarian ekspresi reguler, dan kami menggabungkan hasilnya dalam penggantian, penomoran angka grup dengan offset. Sebagai contoh, mari kita perhatikan seperangkat aturan.

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

Kami menyandikannya dalam pencarian dan mengganti ekspresi:

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

Cobalah di mesin javascript favorit Anda:

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)
}