Bisakah format csv ditentukan oleh regex?

Seorang kolega dan saya baru-baru ini berdebat tentang apakah sebuah regex murni mampu sepenuhnya meng-enkapsulasi format csv, sedemikian rupa sehingga ia mampu mengurai semua file dengan char escape, quote char, dan char separator yang diberikan.

Regex tidak harus mampu mengubah karakter ini setelah pembuatan, tetapi harus tidak gagal pada setiap kasus tepi lainnya.

Saya berpendapat bahwa ini tidak mungkin dilakukan hanya dengan tokenizer. Satu-satunya regex yang mungkin dapat melakukan ini adalah gaya PCRE yang sangat kompleks yang bergerak melampaui sekadar tokenizing.

Saya mencari sesuatu di sepanjang baris:

... format csv adalah tata bahasa bebas konteks dan karenanya, tidak mungkin untuk menguraikan dengan regex saja ...

Atau saya salah? Apakah mungkin untuk mem-parsing csv hanya dengan regex POSIX?

Sebagai contoh, jika kedua escape char dan quote char adalah ", maka kedua baris ini adalah csv yang valid:

"""this is a test.""",""
"and he said,""What will be, will be."", to which I replied, ""Surely not!""","moving on to the next field here..."

Bagus dalam teori, buruk dalam praktik

Dengan CSV saya akan menganggap Anda maksud konvensi seperti yang dijelaskan dalam RFC 4180 .

Sementara mencocokkan data CSV dasar itu sepele:

"data", "more data"

Catatan: BTW, jauh lebih efisien untuk menggunakan fungsi .split ('/ n'). Split ('"') untuk data yang sangat sederhana dan terstruktur dengan baik seperti ini. Ekspresi Reguler berfungsi sebagai NDFSM (Non-Deterministic Finite) State Machine) yang membuang banyak waktu untuk mundur begitu Anda mulai menambahkan case edge seperti escape chars.

Misalnya, inilah string pencocokan ekspresi reguler paling komprehensif yang saya temukan:

re_valid = r"""
# Validate a CSV string having single, double or un-quoted values.
^                                   # Anchor to start of string.
\s*                                 # Allow whitespace before value.
(?:                                 # Group for value alternatives.
  '[^'\\]*(?:\\[\S\s][^'\\]*)*'     # Either Single quoted string,
| "[^"\\]*(?:\\[\S\s][^"\\]*)*"     # or Double quoted string,
| [^,'"\s\\]*(?:\s+[^,'"\s\\]+)*    # or Non-comma, non-quote stuff.
)                                   # End group of value alternatives.
\s*                                 # Allow whitespace after value.
(?:                                 # Zero or more additional values
  ,                                 # Values separated by a comma.
  \s*                               # Allow whitespace before value.
  (?:                               # Group for value alternatives.
    '[^'\\]*(?:\\[\S\s][^'\\]*)*'   # Either Single quoted string,
  | "[^"\\]*(?:\\[\S\s][^"\\]*)*"   # or Double quoted string,
  | [^,'"\s\\]*(?:\s+[^,'"\s\\]+)*  # or Non-comma, non-quote stuff.
  )                                 # End group of value alternatives.
  \s*                               # Allow whitespace after value.
)*                                  # Zero or more additional values
$                                   # Anchor to end of string.
"""

Ini secara wajar menangani nilai kuotasi tunggal dan ganda, tetapi tidak pada baris baru dalam nilai, lolos dari kutipan, dll.

Sumber: Stack Overflow - Bagaimana saya bisa mengurai string dengan JavaScript

Ini menjadi mimpi buruk begitu kasus tepi umum diperkenalkan seperti ...

"such as ""escaped""","data"
"values that contain /n newline chars",""
"escaped, commas, like",",these"
"un-delimited data like", this
"","empty values"
"empty trailing values",        // <- this is completely valid
                                // <- trailing newline, may or may not be included

Kasus tepi newline sebagai nilai saja sudah cukup untuk memecahkan 99,9999% dari parser berbasis RegEx yang ditemukan di alam liar. Satu-satunya alternatif 'masuk akal' adalah menggunakan pencocokan RegEx untuk karakter kontrol / non-kontrol dasar (yaitu terminal vs non-terminal) yang dipasangkan dengan mesin keadaan yang digunakan untuk analisis tingkat yang lebih tinggi.

Sumber: Pengalaman atau dikenal sebagai rasa sakit dan penderitaan yang luas.

Saya adalah penulis jquery-CSV , satu-satunya parser CSV yang berbasis javascript, sepenuhnya sesuai RFC, di dunia. Saya telah menghabiskan waktu berbulan-bulan menangani masalah ini, berbicara dengan banyak orang cerdas, dan mencoba satu ton jika implementasi yang berbeda termasuk 3 penulisan ulang penuh dari mesin parser inti.

tl; dr - Moral dari cerita ini, PCRE sendiri menyebalkan untuk menguraikan apa pun kecuali tata bahasa reguler yang paling sederhana dan ketat (yaitu Tipe-III). Meskipun, ini berguna untuk tokenizing terminal dan string non-terminal.

Regex dapat mem-parsing bahasa reguler apa pun, dan tidak dapat menguraikan hal-hal mewah seperti tata bahasa rekursif. Tapi CSV tampaknya cukup teratur, jadi dapat diuraikan dengan regex.

Mari kita bekerja dari definisi : diizinkan adalah urutan, bentuk pilihan alternatif ( |), dan pengulangan (bintang Kleene, the *).

• Nilai tanda kutip adalah reguler: [^,]*# sembarang char tetapi koma
• Nilai yang dikutip adalah biasa: "([^\"]|\\\\|\\")*"# urutan apa pun selain kutipan "atau lolos kutipan \"atau melarikan diri melarikan diri\\
  • Beberapa bentuk mungkin termasuk melarikan diri tanda kutip dengan tanda kutip, yang menambahkan varian ("")*"pada ekspresi di atas.
• Nilai yang diizinkan adalah reguler: <unquoted-value> |<quoted-value>
• Satu baris CSV biasa: <value> (,<value>)*
• Urutan garis yang dipisahkan oleh \njuga jelas teratur.

Saya tidak menguji setiap ekspresi ini dengan cermat, dan tidak pernah mendefinisikan kelompok tangkapan. Saya juga dipoles beberapa teknis, seperti varian karakter yang dapat digunakan sebagai pengganti ,, "atau garis pemisah: ini tidak melanggar keteraturan, Anda hanya mendapatkan beberapa bahasa yang sedikit berbeda.

Jika Anda dapat menemukan masalah dalam bukti ini, silakan komentar! :)

Tetapi meskipun demikian, penguraian praktis file CSV dengan ekspresi reguler murni mungkin bermasalah. Anda perlu tahu varian mana yang diumpankan ke parser, dan tidak ada standar untuk itu. Anda dapat mencoba beberapa parser terhadap setiap baris sampai berhasil, atau entah bagaimana memilah format komentar. Tetapi ini mungkin memerlukan sarana selain ekspresi reguler untuk melakukannya secara efisien, atau tidak sama sekali.

Jawaban sederhana - mungkin tidak.

Masalah pertama adalah kurangnya standar. Sementara seseorang dapat menggambarkan csv mereka dengan cara yang didefinisikan secara ketat, seseorang tidak dapat berharap untuk mendapatkan file csv yang didefinisikan secara ketat. "Jadilah konservatif dalam apa yang Anda lakukan, menjadi liberal dalam apa yang Anda terima dari orang lain" -Jon Postal

Dengan asumsi bahwa seseorang memang memiliki standar yang dapat diterima, ada pertanyaan tentang karakter pelarian dan jika ini harus seimbang.

Sebuah string dalam banyak format csv didefinisikan sebagai string value 1,string value 2. Namun, jika string itu mengandung koma, itu sekarang "string, value 1",string value 2. Jika itu berisi kutipan, itu menjadi "string, ""value 1""",string value 2.

Pada titik ini saya percaya itu tidak mungkin. Masalahnya adalah Anda perlu menentukan berapa banyak kutipan yang telah Anda baca dan apakah koma ada di dalam atau di luar mode nilai yang dikutip ganda. Menyeimbangkan kurung adalah masalah regex yang tidak mungkin. Beberapa mesin ekspresi reguler yang diperluas (PCRE) dapat mengatasinya, tetapi itu bukan ekspresi reguler saat itu.

Anda mungkin menemukan /programming/8629763/csv-parsing-with-a-context-free-grammar bermanfaat.

Diubah:

Saya telah melihat format untuk karakter pelarian dan belum menemukan yang perlu dihitung secara sewenang-wenang - jadi mungkin bukan itu masalahnya.

Namun, ada masalah apa yang menjadi karakter pelarian dan pembatas rekaman (untuk mulai dengan). http://www.csvreader.com/csv_format.php adalah bacaan yang bagus tentang berbagai format di alam bebas.

• Aturan untuk string yang dikutip (jika itu adalah string yang dikutip tunggal atau string yang dikutip ganda) berbeda.
  • 'This, is a value' vs. "This, is a value"
• Aturan untuk karakter pelarian
  • "This ""is a value""" vs. "This \"is a value\""
• Penanganan pembatas rekaman tertanam ({rd})
  • (embeded mentah) "This {rd}is a value"vs (lolos) "This \{rd}is a value"vs (diterjemahkan)"This {0x1C}is a value"

Kuncinya di sini adalah bahwa adalah mungkin untuk memiliki string yang akan selalu memiliki beberapa interpretasi yang valid.

Pertanyaan terkait (untuk kasus tepi) "apakah mungkin untuk memiliki string yang tidak valid yang diterima?"

Saya masih sangat meragukan bahwa ada ekspresi reguler yang dapat cocok dengan setiap CSV yang valid yang dibuat oleh beberapa aplikasi dan menolak setiap csv yang tidak dapat diuraikan.

Pertama-tama tentukan tata bahasa untuk CSV Anda (apakah pembatas bidang lolos atau dikodekan entah bagaimana jika muncul dalam teks?) Dan kemudian dapat ditentukan apakah itu dapat diuraikan dengan regex. Tata bahasa pertama: parser kedua: http://www.boyet.com/articles/csvparser.html Perlu dicatat bahwa metode ini menggunakan tokenizer - tapi saya tidak bisa membuat regex POSIX yang cocok dengan semua case tepi. Jika penggunaan format CSV Anda non-reguler dan bebas konteks ... maka jawaban Anda ada dalam pertanyaan Anda. Tinjauan bagus di sini: http://nikic.github.com/2012/06/15/The-true-power-of- regular-expressions.html

Regexp ini dapat mengidentifikasi CSV normal, seperti yang dijelaskan dalam RFC:

/("(?:[^"]|"")*"|[^,"\n\r]*)(,|\r?\n|\r)/

Penjelasan:

• ("(?:[^"]|"")*"|[^,"\n\r]*) - bidang CSV, dikutip atau tidak
  • "(?:[^"]|"")*" - bidang yang dikutip;
    • [^"]|""- masing-masing karakter tidak ", atau "lolos sebagai""
  • [^,"\n\r]* - bidang yang tidak dikutip, yang mungkin tidak mengandung , " \n \r
• (,|\r?\n|\r)- pemisah berikut, baik ,atau baris baru
  • \r?\n|\r - baris baru, salah satunya \r\n \n \r

Seluruh file CSV dapat dicocokkan dan divalidasi dengan menggunakan regexp ini berulang kali. Maka perlu untuk memperbaiki bidang yang dikutip, dan membaginya menjadi baris berdasarkan pemisah.

Berikut ini adalah kode untuk parser CSV dalam Javascript, berdasarkan pada regexp:

var csv_tokens_rx = /("(?:[^"]|"")*"|[^,"\n\r]*)(,|\r?\n|\r)/y;
var csv_unescape_quote_rx = /""/g;
function csv_parse(s) {
    if (s && s.slice(-1) != '\n')
        s += '\n';
    var ok;
    var rows = [];
    var row = [];
    csv_tokens_rx.lastIndex = 0;
    while (true) {
        ok = csv_tokens_rx.lastIndex == s.length;
        var m = s.match(csv_tokens_rx);
        if (!m)
            break;
        var v = m[1], d = m[2];
        if (v[0] == '"') {
            v = v.slice(1, -1);
            v = v.replace(csv_unescape_quote_rx, '"');
        }
        if (d == ',' || v)
            row.push(v);
        if (d != ',') {
            rows.push(row)
            row = [];
        }
    }
    return ok ? rows : null;
}

Apakah jawaban ini membantu menyelesaikan argumen Anda, apakah Anda harus memutuskan; Saya senang memiliki parser CSV kecil, sederhana dan benar.

Menurut pendapat saya suatu lexprogram kurang lebih merupakan ekspresi reguler yang besar, dan itu dapat mengubah format yang jauh lebih kompleks, seperti bahasa pemrograman C.

Dengan mengacu pada definisi RFC 4180 :

1. line break (CRLF) - Regexp lebih fleksibel, memungkinkan CRLF, LF atau CR.
2. Catatan terakhir dalam file mungkin atau mungkin tidak memiliki jeda baris akhir - Regexp karena memerlukan jeda baris terakhir, tetapi parser menyesuaikan untuk itu.
3. Mungkin ada baris tajuk opsional - Ini tidak memengaruhi parser.
4. Setiap baris harus berisi jumlah bidang yang sama di seluruh file -
   spasi tidak ditegakkan dianggap bagian dari bidang dan tidak boleh diabaikan - oke
   Bidang terakhir dalam catatan tidak boleh diikuti oleh koma - tidak ditegakkan
5. Setiap bidang mungkin atau mungkin tidak dilampirkan dalam tanda kutip ganda ... - oke
6. Bidang yang berisi penghentian baris (CRLF), tanda kutip ganda, dan koma harus dilampirkan dalam tanda kutip ganda - oke
7. tanda kutip ganda yang muncul di dalam bidang harus diloloskan dengan mendahului dengan tanda kutip ganda lainnya - oke

Regexp sendiri memenuhi sebagian besar persyaratan RFC 4180. Saya tidak setuju dengan yang lain, tetapi mudah untuk menyesuaikan parser untuk mengimplementasikannya.