Le JSON est-il un langage régulier?

19

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 et pour moi?

jjnguy
la source
6
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
1
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 [ n x ] n mentionné ci-dessous. unenbn[nX]n
Xodarap

Réponses:

28

Comme n'est pas un langage normal, JSON non plus, puisque [ n 5 ] n est une entrée valide pour tout n . De même, votre analyseur d'expressions régulières devrait rejeter correctement toute entrée [ m 4 ] nm n que vous ne pouvez pas faire avec des expressions régulières.unenbn[n5]nn[m4]nmn

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

RegexFan
la source
Curieux, quelle est la notation exposant / parenthèse utilisée ici?
jchook
1
unenunen[n[n
31

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
8
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
16
Continuez ensuite à ajouter des «tableaux de» récursivement jusqu'à ce que vous soyez satisfait. ;-)
Marc Hamann
1
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