Apakah JSON Bahasa Biasa?

19

Saya bertanya-tanya apakah spesifikasi JSON mendefinisikan bahasa biasa. Tampaknya cukup sederhana, tetapi saya tidak yakin bagaimana membuktikannya sendiri.

Alasan saya bertanya, adalah karena saya bertanya-tanya apakah seseorang dapat menggunakan ekspresi reguler untuk mengurai JSON secara efektif.

Bisakah seseorang dengan cukup perwakilan tolong buat tag dan untuk saya?

jjnguy
sumber
6
Saya menghapus tag [json] karena sepertinya tidak layak untuk tag di TCS SE.
Tsuyoshi Ito
@ Tsuy, kedengarannya bagus. Jelas saya bukan pengguna berat situs ini, jadi saya yakin Anda lebih tahu.
jjnguy
1
Ingat bahwa implementasi regex sering cocok dengan lebih dari sekedar bahasa biasa. Misalnya Anda dapat menggunakan lookaheads di sebagian besar implementasi, yang akan menerima dengan benar, menyelesaikan masalah disebutkan di bawah ini. Sebuahnbn[nx]n
Xodarap

Jawaban:

28

Karena bukan bahasa biasa, JSON juga tidak, karena adalah input yang valid untuk sembarang . Demikian juga, parser ekspresi reguler Anda harus menolak dengan benar input apa pun mana yang tidak dapat Anda lakukan dengan ekspresi reguler.Sebuahnbn[n5]nn[m4]nmn

Karenanya, JSON tidak teratur.

RegexFan
sumber
Penasaran, apa notasi superskrip / braket yang digunakan di sini?
jchook
31

Tidak, ini tidak teratur. Karena memungkinkan penyisipan pembatas seimbang yang sewenang-wenang, setidaknya harus bebas konteks.

Sebagai contoh, pertimbangkan array array array:

[ [ [ 1, 2], [2, 3] ] , [ [ 3, 4], [ 4, 5] ] ] 

Jelas Anda tidak dapat menguraikannya dengan ekspresi reguler yang benar.

Marc Hamann
sumber
8
Untuk membagi rambut secara teratur, representasi JSON dari semua array array array integer adalah teratur.
Charles Stewart
16
Kemudian terus tambahkan "array" secara rekursif sampai Anda puas. ;-)
Marc Hamann
1
JSON standar bebas konteks, tetapi sebagian besar implementasi hanya mendukung kunci unik. Saya memindahkan pertanyaan saya yang belum terjawab dari stackoverflow ke: cstheory.stackexchange.com/questions/4668/…
Jakob
Perhatikan bahwa saya mengatakan "setidaknya bebas konteks".
Marc Hamann
Memperluas komentar @ CharlesStewart, apakah ini berarti bahwa "JSON dengan kedalaman maks yang ketat ADALAH bahasa biasa"? Atau apakah fitur lain dari JSON mencegah hal ini?
jchook