Le JSON est-il un langage régulier?

Je me demandais si la spécification JSON définissait un langage régulier. Cela semble assez simple, mais je ne sais pas comment le prouver moi-même.

La raison pour laquelle je demande, c'est parce que je me demandais si l'on pouvait utiliser des expressions régulières pour analyser efficacement JSON.

Quelqu'un avec suffisamment de représentants pourrait-il créer les balises json et langage régulier pour moi?

fl.formal-languages regular-expressions regular-language jjnguy
la source

J'ai supprimé le tag [json] car il ne semble pas valoir le coup sur TCS SE.

Tsuyoshi Ito du

@Tsuy, ça sonne bien. Évidemment, je ne suis pas un utilisateur passionné du site, donc je suis sûr que vous savez mieux.

jjnguy

N'oubliez pas que les implémentations regex correspondent souvent à plus que des langages normaux. Par exemple, vous pouvez utiliser des lookaheads dans la plupart des implémentations, qui accepteront correctement

, résolvant le problème

mentionné ci-dessous.

a^{n} b^{n}

$a^nb^n$

[^{n} x]^{n}

$[^nx]^n$

Xodarap

Réponses:

Comme n'est pas un langage normal, JSON non plus, puisque est une entrée valide pour tout . De même, votre analyseur d'expressions régulières devrait rejeter correctement toute entrée où que vous ne pouvez pas faire avec des expressions régulières. $a^n b^n$ $[^n 5 ]^n$ $n$ $[^m 4 ]^n$ $m \ne n$

Par conséquent, JSON n'est pas régulier.

RegexFan
la source

Curieux, quelle est la notation exposant / parenthèse utilisée ici?

jchook

a^{n}

$a^n$

a

$a$

n

$n$

[^{n}

$[^n$

[

$[$

n

$n$

Non, ce n'est pas régulier. Puisqu'il permet l'incorporation arbitraire de délimiteurs équilibrés, il doit être au moins sans contexte.

Par exemple, considérons un tableau de tableaux de tableaux:

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

De toute évidence, vous ne pouvez pas analyser cela avec de vraies expressions régulières.

Marc Hamann
la source

Pour séparer les cheveux de façon obtus, les représentations JSON de tous les tableaux de tableaux de tableaux d'entiers sont régulières.

Charles Stewart

Continuez ensuite à ajouter des «tableaux de» récursivement jusqu'à ce que vous soyez satisfait. ;-)

Marc Hamann

Le JSON standard est sans contexte, mais la plupart des implémentations ne prennent en charge que des clés uniques. J'ai déplacé ma question sans réponse de stackoverflow vers: cstheory.stackexchange.com/questions/4668/…

Jakob

Notez que j'ai dit "au moins sans contexte".

Marc Hamann

En développant le commentaire de @ CharlesStewart, cela signifie-t-il que "JSON avec une profondeur maximale stricte EST un langage régulier"? Ou d'autres fonctionnalités de JSON empêchent-elles cela?

jchook