¿Es JSON un lenguaje regular?

19

Me preguntaba si la especificación JSON definía un lenguaje regular. Parece bastante simple, pero no estoy seguro de cómo demostrarlo yo mismo.

La razón por la que pregunto es porque me preguntaba si uno podría usar expresiones regulares para analizar JSON de manera efectiva.

¿Podría alguien con suficiente representante crear las etiquetas y para mí?

jjnguy
fuente
66
Eliminé la etiqueta [json] porque no parece valer una etiqueta en TCS SE.
Tsuyoshi Ito
@ Tsuy, suena bien. Obviamente no soy un usuario ávido del sitio, así que estoy seguro de que lo sabes mejor.
jjnguy
1
Recuerde que las implementaciones de expresiones regulares con frecuencia coinciden con más que solo los idiomas normales. Por ejemplo, puede usar lookaheads en la mayoría de las implementaciones, que aceptarán correctamente, resolviendo el problema [ n x ] n que se mencionan a continuación. unnortesinorte[norteX]norte
Xodarap

Respuestas:

28

Como no es un lenguaje regular, tampoco lo es JSON, ya que [ n 5 ] n es una entrada válida para cualquier n . Del mismo modo, su analizador de expresiones regulares tendría que rechazar adecuadamente cualquier entrada [ m 4 ] n donde m n que no puede hacer con expresiones regulares.unnortesinorte[norte5 5]nortenorte[metro4 4]nortemetronorte

Por lo tanto, JSON no es regular.

RegexFan
fuente
Curioso, ¿cuál es la notación de superíndice / paréntesis utilizada aquí?
jchook
31

No, no es regular. Dado que permite la incorporación arbitraria de delimitadores equilibrados, debe estar al menos libre de contexto.

Por ejemplo, considere una matriz de matrices de matrices:

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

Claramente, no podrías analizar eso con verdaderas expresiones regulares.

Marc Hamann
fuente
8
Para obtener pelos divididos obtusamente, las representaciones JSON de todas las matrices de matrices de matrices de enteros son regulares.
Charles Stewart
16
Luego siga agregando "matrices de" recursivamente hasta que esté satisfecho. ;-)
Marc Hamann
1
JSON estándar no tiene contexto, pero la mayoría de las implementaciones solo admiten claves únicas. Moví
Jakob
Tenga en cuenta que dije "al menos sin contexto".
Marc Hamann el
Ampliando el comentario de @ CharlesStewart, ¿significa esto que "JSON con una profundidad máxima estricta ES un lenguaje regular"? ¿O otras características de JSON evitan esto?
jchook