Является ли JSON обычным языком?

19

Мне было интересно, если спецификация JSON определяет обычный язык. Это кажется достаточно простым, но я не уверен, как это доказать самому.

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

Может ли кто-нибудь с достаточным количеством представителей, пожалуйста, создать теги и для меня?

jjnguy
источник
6
Я удалил тег [json], потому что он, кажется, не стоит тега на TCS SE.
Цуёси Ито
@ Цуй, звучит хорошо. Очевидно, я не заядлый пользователь сайта, поэтому я уверен, что вы знаете лучше.
Jjnguy
1
Помните, что реализации регулярных выражений часто соответствуют не только обычным языкам. Например, вы можете использовать lookaheads в большинстве реализаций, которые правильно примут , решая проблему [ n x ] n, упомянутую ниже. aNбN[NИкс]N
Xodarap

Ответы:

28

Поскольку не является обычным языком, также не является JSON, так как [ n 5 ] n является допустимым вводом для любого n . Аналогично, ваш синтаксический анализатор регулярных выражений должен был бы корректно отклонить любой ввод [ m 4 ] n, где m n, что вы не можете сделать с регулярными выражениями.anbn[n5]nn[m4]nmN

Следовательно, JSON не является регулярным.

RegexFan
источник
Любопытно, что здесь используется надстрочная / скобочная запись?
Jchook
1
aNaN[N[N
31

Нет, это не регулярно. Поскольку он допускает произвольное вложение сбалансированных разделителей, он должен быть как минимум не зависящим от контекста.

Например, рассмотрим массив массивов массивов:

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

Понятно, что вы не можете разобрать это с истинными регулярными выражениями.

Марк Хаманн
источник
8
Чтобы тупо разделить волоски, JSON-представления всех массивов массивов целых чисел являются правильными.
Чарльз Стюарт
16
Затем продолжайте добавлять «массивы» рекурсивно, пока вы не будете счастливы. ;-)
Марк Хаманн
1
Стандартный JSON не зависит от контекста, но большинство реализаций поддерживают только уникальные ключи. Я переместил свой оставшийся
Jakob
Обратите внимание, что я сказал «по крайней мере, без контекста».
Марк Хаманн
Продолжая комментарий @ CharlesStewart, означает ли это, что «JSON со строгой максимальной глубиной - это обычный язык»? Или другие функции JSON предотвращают это?
Jchook