Jakie formalne klasy językowe to XML i JSON z unikalnymi kluczami?

Przeniosłem to pytanie z stackoverflow, gdzie id nie otrzymał odpowiedzi. Mieliśmy podobne pytanie, czy JSON jest regularny :

JSON i XML są często nazywane językami bezkontekstowymi - oba są określone głównie przez gramatykę formalną w EBNF. Jednak dotyczy to tylko JSON zdefiniowanego w RFC 4329, sekcja 2.2, który nie wymaga unikatowości kluczy obiektowych (wielu może nie wiedzieć, ale {"a": 1, "a": 2} jest prawidłowym JSON!). Ale jeśli potrzebujesz unikalnych kluczy w JSON lub unikalnych nazw atrybutów w XML, nie może to być wyrażone przez gramatyki bezkontekstowe. Ale jaka jest klasa językowa JSON z unikalnymi kluczami i dobrze sformułowanym XML (co implikuje unikalne nazwy atrybutów?).

Jeden z najlepszych artykułów, jakie znalazłem na ten temat (Murato i in., 2001: Taksonomia języków schematu XML z wykorzystaniem teorii języków formalnych ) wyraźnie wyklucza ograniczenia integralności, takie jak klucze / odwołania do kluczy i unikalność, które należy sprawdzić na dodatkowej warstwie. Poza tym podzbiór XML zdefiniowany przez schemat XML lub DTD jest pozbawiony kontekstu. Ale nie pełny zestaw wszystkich poprawnie sformatowanych dokumentów XML.

Myślę, że zagnieżdżony automat stosu (= język indeksowany) powinien być w stanie przeanalizować JSON z unikalnym ograniczeniem klucza. Dla XML można uprościć pytanie do języka S wszystkich rozdzielonych przecinkami list unikalnych liczb całkowitych. Czy ktoś wie więcej, najlepiej z cytatami?

PS: Prosty algorytm do decydowania o językach (oprócz części bezkontekstowej) oparty jest na dobrym algorytmie sortowania. Dlatego powinno być rozstrzygalne w „czasie liniowo-rytmicznym” z najgorszym przypadkiem O (n log n). Nie dowiedziałem się jeszcze, czy klasa złożoności jest na przykład „wrażliwa na kontekst” , czy „indeksowana”, ale prawdopodobnie coś pomiędzy kontekstem a kontekstem (?).

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

Używanie BNF z operatorem unikalnego powtarzania x := S^mówi, że an xjest instancją asymbolu S, opcjonalnie po niej występuje instancja bzbioru S - a, sama opcjonalnie po niej występuje instancja czbioru S - a - bi tak dalej. Jeśli |S|liczba jest możliwa Si jest skończona, 2 ^ |S|! - 1to liczba jest możliwa S^.

Mówienie w kategoriach mocy obliczeniowej opisywanego języka nie ma większego sensu , ponieważ dotyczy semantyki statycznej, w półmroku między składnią a semantyką zwykłą (dynamiczną). Moc ekspresyjna gramatyki jest rozszerzona, ponieważ ma ona formalny sposób wyrażania określonego rodzaju adaptacji wejściowej.

W szczególności zapewnia sposób akceptacji permutacji podzbioru określonego zestawu. Nie sądzę, aby istniała jakaś nazwa dla tej klasy języka. Z pewnością nie jest pozbawiony kontekstu, ale wymagania dotyczące kontekstu są co najmniej dość ściśle kontrolowane. Jeśli potrzebujesz terminu, po prostu wybierz jeden. Sugeruję poszanowanie kontekstu dla klasy języków, których nie można opisać gramatyką bezkontekstową bez dodatkowych osadzonych informacji o statycznych ograniczeniach semantycznych, które, mówiąc uczciwie, są niejasno składniowe w duchu.

Najbardziej użyteczną aplikacją tego konkretnego rozszerzenia jest prawdopodobnie jedynie możliwość wprowadzenia ograniczeń unikatowego klucza, ale umożliwia także opisanie tak interesujących zestawów x := [0-7]^, które pasują do dowolnej liczby ósemkowej 8 lub mniej powtarzających się cyfr. Jeśli chodzi o jego złożoność, ustalenie, czy element zestawu został zauważony, nie jest gorsze niż logarytmiczne, a częstotliwość sprawdzania jest liniowa pod względem liczby dopasowanych elementów, więc ^operator jest rzeczywiście rozstrzygalny w najgorszym przypadku w czasie liniowo-rytmicznym.