¿Qué clase de lenguaje formal son XML y JSON con claves únicas?

12

Me mudé a esta pregunta desde StackOverflow donde id obtuvo ninguna respuesta. Tuvimos una pregunta similar si JSON es regular :

JSON y XML son llamados frecuentemente para ser lenguajes libres de contexto; ambos se especifican principalmente por una gramática formal en EBNF. Sin embargo, esto solo es cierto para JSON como se define en RFC 4329, sección 2.2, que no requiere la unicidad de las claves de objeto (muchos pueden no saberlo, pero {"a": 1, "a": 2} es JSON válido). Pero si necesita claves únicas en JSON o nombres de atributos únicos en XML, esto no puede expresarse mediante gramáticas libres de contexto. Pero, ¿cuál es la clase de lenguaje de JSON con claves únicas y para XML bien formado (que implica nombres de atributo únicos?).

Uno de los mejores trabajos que encontré sobre este tema (Murato et al, 2001: Taxonomía de los lenguajes de esquema XML usando la teoría del lenguaje formal ) excluye explícitamente las restricciones de integridad, como las claves / keyrefs y la unicidad para verificar en una capa adicional. Además de esto, el subconjunto de XML definido por un Esquema XML o por un DTD no tiene contexto. Pero no el conjunto completo de todos los documentos XML bien formados.

Creo que un autómata de pila anidada (= lenguaje indexado) debería poder analizar JSON con una restricción de clave única. Para XML puede simplificar la pregunta al lenguaje S de todas las listas separadas por comas de enteros únicos. ¿Alguien sabe más, preferiblemente con citas?

PD: un algoritmo simple para decidir los idiomas (además de la parte sin contexto) se basa en un buen algoritmo de clasificación. Por lo tanto, debe ser decidible en "tiempo linealitmico" con O (n log n) en el peor de los casos. Todavía no he descubierto si la clase de complejidad es, por ejemplo, "ligeramente sensible al contexto" o "indexada", pero probablemente algo entre libre de contexto y sensible al contexto (?).

x := a+ ⇔ x := a | x a^a^a

fl.formal-languages Jakob
fuente
JSON con claves de objeto repetibles no tiene contexto (consulte la gramática JSON), pero ¿cómo expresa la restricción de clave única en una gramática o autómata común? O: a qué clase de complejidad pertenece un analizador XML, si puede detectar el conjunto de todos los documentos XML bien formados (bien formado implica nombres de atributos únicos por elemento).
Jakob
1
Usando los términos del generador del compilador aquí. La sintaxis respectiva de JSON y XML es, sin duda, sin contexto. Las propiedades como identificadores únicos o restricciones de tipo de valor son semánticas estáticas (algunas personas también llaman a esta sintaxis, pero rechazo esa nomenclatura por varias razones). Los generadores de analizadores generalmente le permiten enriquecer un analizador común con cosas como predicados sintácticos / semánticos que no necesitan estar libres de contexto. En teoría, se utilizan gramáticas atribuidas . No sé si tales características pueden expresarse naturalmente con gramáticas formales de cualquier poder.
Raphael
1
Qué partes de un lenguaje formal van más allá de la sintaxis, depende del punto de vista. Las estructuras anidadas simples como XML y JSON pueden ser analizadas por un autómata pushdown. Solo quiero saber qué potencia computable obtienes, si el autómata está enriquecido con un diccionario para buscar si un valor almacenado se ha leído antes, para garantizar la restricción de unicidad. Supongo que es una gramática indexada (¿un autómata de pila anidado?) Pero hay varios tipos de gramáticas indexadas.
Jakob
@Jakob, doblaría esta discusión (abreviada) en la pregunta para que quede claro exactamente lo que estás preguntando
Suresh Venkat
Un LBA debería ser suficiente ya que nunca tendrá que almacenar más identificadores de los que tiene caracteres en su texto. No sé lo suficiente sobre las clases entre CFL y CSL para ser de ayuda allí.
Raphael

Respuestas:

6

Al usar BNF con su operador de repetición única, x := S^dice que an xes una instancia ade símbolo S, opcionalmente seguida por una instancia bde conjunto S - a, opcionalmente seguida por una instancia cde conjunto S - a - b, y así sucesivamente. Si |S|es el número posible Sy es finito, entonces 2 ^ |S|! - 1es el número posible S^.

No es realmente significativo hablar en términos del poder computacional del lenguaje que se describe, ya que se trata de semántica estática, en el crepúsculo entre la sintaxis y la semántica ordinaria (dinámica). El poder expresivo de la gramática se extiende, ya que tiene un medio formal de expresar un tipo particular de adaptación de entrada.

Específicamente, proporciona un medio para aceptar una permutación de un subconjunto de un conjunto particular. No creo que exista ningún nombre para esta clase de lenguaje. Ciertamente no está libre de contexto, pero el requisito de contexto está al menos estrictamente controlado. Si necesita un término para ello, solo acuñe uno. Sugiero que se respete el contexto para la clase de lenguajes que no pueden describirse mediante una gramática libre de contexto sin información adicional incorporada sobre restricciones semánticas estáticas, que para ser justos son vagamente sintácticos en espíritu.

La aplicación más útil de esta extensión en particular es probablemente la capacidad de introducir restricciones de clave única, pero también le permite describir conjuntos tan interesantes como x := [0-7]^, que coinciden con cualquier número octal de 8 o menos dígitos no repetidos. En cuanto a la complejidad del mismo, determinar si se ha visto un elemento del conjunto no es peor que logarítmico, y la frecuencia de verificación es lineal en el número de elementos coincidentes, por lo que el ^operador es realmente decidible en el peor de los casos el tiempo linealítico.

Jon Purdy
fuente
Gracias por la respuesta y por la sugerencia de pensar en permutaciones de un subconjunto. Aunque el operador de repetición única no captura pares clave-valor con claves únicas, la complejidad debería ser la misma para estos casos. Sin embargo, si empiezo a aplicar el operador en estructuras arbitrarias, la clase S^donde Shay algunas CFL puede no tener contexto porque las CFL no están cerradas bajo la diferencia. Debería ser factible si Ses un lenguaje regular, pero desafortunadamente no puede decidir si un CFL determinado es regular. Tal vez plantearé otra pregunta ya que esto está más allá de las restricciones de JSON y XML.
Jakob