Welche formalen Sprachklassen sind XML und JSON mit eindeutigen Schlüsseln?

Ich habe diese Frage aus dem Stackoverflow verschoben, wo id keine Antworten erhielt. Wir hatten eine ähnliche Frage, ob JSON regelmäßig ist :

JSON und XML werden häufig als kontextfreie Sprachen bezeichnet - beide werden hauptsächlich durch eine formale Grammatik in EBNF spezifiziert. Dies gilt jedoch nur für JSON gemäß RFC 4329, Abschnitt 2.2, für das keine Eindeutigkeit der Objektschlüssel erforderlich ist (viele wissen möglicherweise nicht, aber {"a": 1, "a": 2} ist gültiges JSON!). Wenn Sie jedoch eindeutige Schlüssel in JSON oder eindeutige Attributnamen in XML benötigen, kann dies nicht durch eine kontextfreie Grammatik ausgedrückt werden. Aber welches ist die Sprachklasse von JSON mit eindeutigen Schlüsseln und für wohlgeformtes XML (was impliziert eindeutige Attributnamen?).

Eine der besten Arbeiten, die ich zu diesem Thema gefunden habe (Murato et al., 2001: Taxonomie von XML-Schemasprachen unter Verwendung der formalen Sprachtheorie ), schließt Integritätsbeschränkungen wie Schlüssel / Schlüsselreferenzen und Eindeutigkeit, die auf einer zusätzlichen Ebene überprüft werden sollen, ausdrücklich aus. Außerdem ist die durch ein XML-Schema oder eine DTD definierte Teilmenge von XML kontextfrei. Aber nicht der vollständige Satz aller wohlgeformten XML-Dokumente.

Ich denke, ein verschachtelter Stapelautomat (= indizierte Sprache) sollte in der Lage sein, JSON mit einer eindeutigen Schlüsselbeschränkung zu analysieren. Für XML kann die Frage auf die Sprache S aller durch Kommas getrennten Listen eindeutiger Ganzzahlen vereinfacht werden. Weiß jemand mehr, vorzugsweise mit Zitaten?

PS: Ein einfacher Algorithmus zur Entscheidung der Sprachen (neben dem kontextfreien Teil) basiert auf einem guten Sortieralgorithmus. Daher sollte es in "linearithmischer Zeit" mit O (n log n) Worst Case entscheidbar sein. Ich habe noch nicht herausgefunden, ob die Komplexitätsklasse zum Beispiel "leicht kontextsensitiv" oder "indiziert" ist, aber wahrscheinlich etwas zwischen kontextfrei und kontextsensitiv (?).

x := a+ $\Leftrightarrow$ x := a | x a^a^a

Wenn Sie BNF mit Ihrem Operator für eindeutige Wiederholungen verwenden, bedeutet dies x := S^, dass a eine xInstanz aeines Symbols ist S, optional gefolgt von einer Instanz bvon set S - a, selbst optional gefolgt von einer Instanz cvon set S - a - busw. Wenn |S|die Anzahl der möglichen Sund endlich ist, dann 2 ^ |S|! - 1ist die Anzahl der möglichen S^.

Es ist nicht wirklich sinnvoll, über die Rechenleistung der beschriebenen Sprache zu sprechen , da es sich um statische Semantik im Zwielicht zwischen Syntax und gewöhnlicher (dynamischer) Semantik handelt. Die Ausdruckskraft der Grammatik wird erweitert, da sie ein formales Mittel zum Ausdrücken einer bestimmten Art der Eingabeanpassung bietet.

Insbesondere bietet es ein Mittel zum Akzeptieren einer Permutation einer Teilmenge einer bestimmten Menge. Ich glaube nicht, dass es einen Namen für diese Sprachklasse gibt. Es ist sicherlich nicht kontextfrei, aber die Kontextanforderungen werden zumindest ziemlich streng kontrolliert. Wenn Sie einen Begriff dafür benötigen, prägen Sie einfach einen. Ich schlage vor , Kontext-Achtung für die Klasse der Sprachen , die nicht durch eine kontextfreie Grammatik ohne zusätzliche eingebettete Informationen über statische semantische Einschränkungen beschrieben werden kann, die fair zu sein sind vage syntaktische im Geist.

Die nützlichste Anwendung dieser speziellen Erweiterung ist wahrscheinlich nur die Möglichkeit, Einschränkungen für eindeutige Schlüssel einzuführen. Sie können jedoch auch interessante Sätze beschreiben x := [0-7]^, die einer beliebigen Oktalzahl von 8 oder weniger nicht wiederholten Ziffern entsprechen. Was die Komplexität betrifft, ist die Bestimmung, ob ein Element der Menge gesehen wurde, nicht schlechter als logarithmisch, und die Häufigkeit der Überprüfung ist linear in der Anzahl der übereinstimmenden Elemente, so dass der ^Operator tatsächlich in der linearithmischen Zeit im ungünstigsten Fall entscheidbar ist.