JSON é uma linguagem regular?

Eu queria saber se a especificação JSON definiu uma linguagem regular. Parece bastante simples, mas não tenho certeza de como provar isso sozinho.

A razão pela qual pergunto é porque estava pensando se alguém poderia usar expressões regulares para analisar efetivamente o JSON.

Alguém com representante suficiente pode criar as tags json e linguagem regular para mim?

fl.formal-languages regular-expressions regular-language jjnguy
fonte

Eu removi a tag [json] porque ela não parece valer uma tag no TCS SE.

Tsuyoshi Ito

@Tsuy, parece bom. Obviamente, eu não sou um usuário ávido do site, por isso tenho certeza que você sabe melhor.

Jjnguy

Lembre-se de que as implementações de regex frequentemente correspondem mais do que apenas idiomas comuns. Por exemplo, você pode usar lookaheads na maioria das implementações, que aceitarão

corretamente, resolvendo o

problema que outros mencionados abaixo.

a^{n} b^{n}

$a^nb^n$

[^{n} x]^{n}

$[^nx]^n$

Xodarap

Respostas:

Como não é uma linguagem regular, nem o JSON, pois é uma entrada válida para qualquer . Da mesma forma, seu analisador de expressões regulares teria que rejeitar adequadamente qualquer entrada que que você não pode fazer com expressões regulares. $a^n b^n$ $[^n 5 ]^n$ $n$ $[^m 4 ]^n$ $m \ne n$

Portanto, o JSON não é regular.

RegexFan
fonte

Curioso, qual é a notação sobrescrita / colchete usada aqui?

jchook 24/11

Não, não é regular. Como permite a incorporação arbitrária de delimitadores balanceados, deve ser pelo menos livre de contexto.

Por exemplo, considere uma matriz de matrizes de matrizes:

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

Claramente, você não poderia analisar isso com expressões regulares verdadeiras.

Marc Hamann
fonte

Para dividir os cabelos obtusamente, as representações JSON de todas as matrizes de matrizes de matrizes de números inteiros são regulares.

Charles Stewart

Continue adicionando "matrizes de" recursivamente até ficar feliz. ;-)

Marc Hamann

O JSON padrão é livre de contexto, mas a maioria das implementações suporta apenas chaves exclusivas. Mudei a minha pergunta sem resposta de stackoverflow para: cstheory.stackexchange.com/questions/4668/...

Jakob

Note que eu disse "pelo menos livre de contexto".

Marc Hamann 31/01

Expandindo o comentário de @ CharlesStewart, isso significa que "JSON com uma profundidade máxima estrita É uma linguagem comum"? Ou outros recursos do JSON impedem isso?

jchook 24/11